Matrix powering in $O(\log n)$ time?

Problem Detail: 

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.

Asked By : Jack Hunt

Answered By : Massimo Cafaro

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4998