# Complexity of computing matrix powers

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily calculate $A^n$ in $\mathcal{O}(M(n)\log(n))$ time. Is it possible to solve this problem in lesser time complexity?

Matrix entries can, in general, be from a semiring but you can assume additional structure if it helps.

Note: I understand that in general computing $A^m$ in $o(M(n)\log(m))$ time would give a $o(\log m)$ algorithm for exponentiation. But, a number of interesting problems reduce to the special case of matrix exponentiation where m=$\mathcal O(n)$, and I was not able to prove the same about this simpler problem.

-
what are the entries of the matrix? Integers? –  Kaveh Apr 9 '12 at 2:43
The entries can, in general, be from a semiring but you can assume additional structure if it helps. –  Shitikanth Apr 9 '12 at 3:10
I could not get a reduction from multiplation to squaring from the above proposed method (i.e. using $(A\pm B)^2$). However, using $\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2$ works. However, this only gives a $\Omega(M(n))$ on computing $A^n$. –  Shitikanth Apr 13 '12 at 18:25

If the matrix is diagonalizable then taking the $n$th power can be done in time $$O(D(n)+ n\log n)$$ where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then $$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.

-
Even if the matrix is diagonalizable, the best known algorithms for eigendecomposition take $O(n^3)$ time. Using the Coppersmith-Winograd algorithm, we already have a $O(n^{2.3727}\log(m))$ algorithm for computing $A^m$. –  Shitikanth Apr 9 '12 at 5:24
(1) The time bound you cite is not by Coppersmith-Winograd (as you probably know). (2) All algorithms of that form only work for rings; they do not work for general semirings (as you allow in your question). –  Ryan Williams Apr 14 '12 at 20:36

One good way out is Singular Value Decomposition SVD. Given an $n\times n$ real matrix $A$ of full rank , SVD splits it apart as $A=U\Sigma U^T$ where $\Sigma$ is a diagonal matrix, in time $O(n^3)$. By the properties of SVD, $A^m = U \Sigma^m U^T$, so only the diagonal matrix need be exponentiated, and this can be done in $O(n\log m)$ time. Performing the final multiplication $U \times \Sigma^m \times U^T$ takes $O(n^{2.3727})$, so we have altogether $O(n^3 + n \log m)$ operations.

Update after comment The point is that once the SVD is found, any power takes only $O(n^{2.3727}+n \log m)$ time to compute by your own C-W algorithm. But this isn't your question.If there were really an $o(M(n)\log(m))$ algorithm, it would convert immediately to an $o(\log n)$ algorithm for integers. I suspect that one such doesn't exist.

-
Since Coppersmith–Winograd algorithm finds the product of two matrices in $O(n^{2.3727})$ time, we already have a $O(n^{2.3727}\log(m))$ algorithm for computing $A^m$. I am interested in knowing if this can be improved upon without requiring a better matrix multiplication algorithm, especially for $m=O(n)$. –  Shitikanth Apr 9 '12 at 0:54
the SVD doesn't give $A = U \Sigma U^\top$ in general - the right hand side matrix is $V \ne U^\top$ –  Suresh Apr 9 '12 at 4:10
It's a bit misleading to have $n$ for the power as well, so I'll use $m$. If $n=1$ it should take $O(M(1)\log m$ time to find $A^m$, which is equivalent to multiplying integers –  PKG Apr 9 '12 at 16:10
@Shitikanth see ccrwest.org/gordon/jalg.pdf for a survey of fast-exponentiation algorithms. In general, it's not possible to use fewer than $\log m$ multiplications. –  Joe Apr 9 '12 at 18:33
This was unclear from your question, as stated. –  PKG Apr 10 '12 at 5:10