9
$\begingroup$

Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time?

I have been searching online, but have been unsuccessful thus far.

$\endgroup$
  • 1
    $\begingroup$ You mean you have a fixed size matrix? in fact if your matrix is of size $m$ you can't expect to find $O(log \ n)$ algorithm. $\endgroup$ – user742 Oct 10 '12 at 19:13
  • $\begingroup$ People usually refer to this problem as matrix powering. Matrix exponentiation means finding $e^X$ $\endgroup$ – Shitikanth Oct 10 '12 at 19:41
  • $\begingroup$ @Shitikanth Ok, thanks. I shall change that now. $\endgroup$ – Jack H Oct 10 '12 at 19:47
11
$\begingroup$

Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For people coming from the future, this is a terrible answer. It does work O(n^3 * log(n)) when there are O(n^3) algorithms instead. See the answer from Yuval below. As practical matter, this is normally done by SVD decomposition, then raising the N elements of the D matrix to the power, and the multiplying the matrix back out again. $\endgroup$ – Michael O Nov 29 '19 at 0:48
  • $\begingroup$ @Michael O, I think you really missed the point. You misunderstood what the OP was asking for, i.e., how to raise a matrix to the $n$-th power in $O(\lg n) steps$. The key is that the OP is only requiring that the number of steps done is $O(\lg n)$, not the overall complexity since this would require taking into account the matrix order as well. $\endgroup$ – Massimo Cafaro Nov 29 '19 at 8:44
  • $\begingroup$ It is obvious that the proposed divide and conquer approach has worst-case complexity $O(\lg n)$ only when the matrix order is $O(1)$, since in this case the corresponding recurrence equation is $T(n) = T(n/2) + O(1)$ (as an example, for a 3 x 3 matrix a matrix multiplication can be done using a constant number of scalar multiplications and additions). One possible application of the algorithm I gave, is to compute the $n$-th Fibonacci number, by tasing the matrix whose entries are $a_{11} = 1, a_{12} = 1, a_{21} = 1, a_{22} = 0$ to the $n$-th power. $\endgroup$ – Massimo Cafaro Nov 29 '19 at 8:45
  • $\begingroup$ Finally, note also that this was already sorted out and fully understood: just take a look at the comment to the question provided by @user742. $\endgroup$ – Massimo Cafaro Nov 29 '19 at 8:46
7
$\begingroup$

There are two other algorithms which may or may not be relevant. The first algorithm diagonalizes your matrix (which is usually possible), writing it as $M = PDP^{-1}$, where $M,D$ in general may be complex-valued. You then compute $M=PD^nP^{-1}$. Note it's very easy to raise a diagonal matrix to the $n$th power. If $M$ is not diagonalizable, you find its Jordan form and proceed as before (now you also have to calculate some binomial coefficients). This algorithm is probably not numerically stable.

Another algorithm uses the fact that $M$ satisfies its characteristic polynomial (or even its minimal polynomial). Suppose $P(M) = 0$ for some $P$, say the characteristic polynomial. Then we can compute $M^n$ over $\mathbb{R}[M]/(P(M))$, and then substitute $M$. That means that we calculate $M^n$ as a polynomial, using the fact that $P(M) = 0$, and only at the end substitute the values of $M$. We could even precompute all the necessary powers of $M$ and all the values of $M^k \pmod{P(M)}$ for $k < 2\deg P-1$, and then this algorithm could be faster than the algorithm is Massimo Cafaro's answer. It might be more numerically stable than the previous algorithm.

| cite | improve this answer | |
$\endgroup$

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.