Matrix exponentiation

Compute a nonnegative integer power $A^n$ by repeated squaring. If $n=2k$, use $A^n=(A^k{)}^2$; if $n=2k+1$, use $A^n=A(A^k{)}^2$. This needs $O(\log n)$ matrix multiplications and permits fast evaluation of fixed-order linear recurrences via a companion matrix. It is distinct from computing the matrix exponential $e^A$.