patternModerate
Complexity of computing matrix powers
Viewed 0 times
matrixpowerscomplexitycomputing
Problem
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.
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.
Solution
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.
$$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.
Context
StackExchange Computer Science Q#1147, answer score: 12
Revisions (0)
No revisions yet.