k'th power of a square matrix

Question

I want to compute k'th power of a square matrix (n x n). The method should be more efficient than the classic matrix multiplication, which is $n^3$. I searched for some ways to calculate and found that Strassen algorithm can do it in $n^{2.8}$. Is it the correct approach for my problem? I want my algorithm to have $o(kn^3)$ runtime.

Answer 1

Use the binary decomposition of $k$. The complexity of the calculation of $A^k$ is at most $\sim 2\log_2(k)n^3$. For $A^{25}$, calculate and store: $A^2,A^4,A^8,A^{16},A^{24},A^{25}$.

Answer 2

Why not using eigenvalue decomposition? If the matrix $A$ is diagonalizable then $A=P^{-1}DP$ and $A^k=P^{-1}D^kP$. If $A$ cannot be diagonalized, then you can use the Jordan form $A^k=P^{-1}J^kP$ where there is a closed form formula for $J^k$ (see https://en.wikipedia.org/wiki/Jordan_normal_form#Powers).