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
