Matrix exponentiation
= Matrix exponentiation
= Matrix powering
{synonym}
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$.