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.

  • $\begingroup$ what are the entries of the matrix? Integers? $\endgroup$ – Kaveh Apr 9 '12 at 2:43
  • 1
    $\begingroup$ The entries can, in general, be from a semiring but you can assume additional structure if it helps. $\endgroup$ – Shitikanth Apr 9 '12 at 3:10
  • $\begingroup$ 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$. $\endgroup$ – 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.

  • 6
    $\begingroup$ 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$. $\endgroup$ – Shitikanth Apr 9 '12 at 5:24
  • 2
    $\begingroup$ (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). $\endgroup$ – 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.

  • $\begingroup$ 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)$. $\endgroup$ – Shitikanth Apr 9 '12 at 0:54
  • 1
    $\begingroup$ the SVD doesn't give $A = U \Sigma U^\top$ in general - the right hand side matrix is $V \ne U^\top$ $\endgroup$ – Suresh Apr 9 '12 at 4:10
  • 1
    $\begingroup$ 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 $\endgroup$ – PKG Apr 9 '12 at 16:10
  • 2
    $\begingroup$ @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. $\endgroup$ – Joe Apr 9 '12 at 18:33
  • 1
    $\begingroup$ This was unclear from your question, as stated. $\endgroup$ – PKG Apr 10 '12 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.