Question: A consequence of the repeated-squaring algorithm is that, when k is a power of two, we can compute the kth power of a matrix using only O(log k) matrix multiplications. (Start with A, compute A'=A*A to get A^2, then compute A"=A'*A' to get A^4, then A"'=A"*A" to get A^8, and so on until we get up to A^k.) For arbitrary k, how can we find the kth power of a matrix using only O(log k) matrix multiplications?
Answer: Regard k as a summation of distinct powers of 2:
k = 2^(k_0) + 2^(k_1) + 2^(k_2) + ... + 2^(k_j)Note that j is at most lg k. Now A^k is
A^k = A^(2^(k_0) + 2^(k_1) + 2^(k_2) + ... + 2^(k_j))
= A^(2^(k_0)) * A^(2^(k_1)) * A^(2^(k_2)) * ... * A^(2^(k_j))
This is a product of lg k matrices. We can compute all of
them in O(log k) matrix multiplications. (We'll pass them
all as we compute A^(2^(k_j)).) Then we can
multiply them together using another O(log k) matrix
multiplications. So the total number of matrix multiplications is O(log
k).