# Prove a bound on matrix multiplication?

Show that $O(\log n)$ matrix multiplications suffice for computing $X^n$. (Hint:Think about computing $X^8$.)

$X = \pmatrix{0 & 1 \\ 1 & 1}$

How would I go about doing this? I'm completely lost.

-
There are many ideas. One general one is the binary method for exponentiation. For matrices, if it can be done, diagonalization is awsomely efficient. –  André Nicolas Oct 8 '12 at 4:20

First calculate the binary expansion of the exponent $n$. So we find bits $a_0,a_1,a_2,\dots, a_k$ such that $$n=a_02^0+a_12^1+a_22^2+\cdots +a_k2^k.\tag{1}$$ Calculate $X^0=I$, $X^1$, $X^2$, $X^4$, and so on up to $X^{2^k}$ by repeated squaring. This works because $X^{2^{j+1}}=(X^{2^j})^2$.
Finally, find the product of all the $X^{2^i}$ with $a_i=1$. This product is $X^n$. That follows from the fact that $X^{s+t}=X^sX^t$.
The $k$ of Formula $(1)$ is of size about $\log_2 n$, so the repeated squarings use about $\log_2 n$ matrix multiplications. The multiplications at the end, for the $a_i=1$, take (at most) about $\log_2 n$ matrix multiplications.
Remark: The powers of the particular matrix mentioned in the problem are intimately connected with the Fibonacci numbers. So in particular the binary method for matrix exponentiation is useful for calculating $F_n$ for largish $n$. Because of the rapid growth of the Fibonacci numbers, it is best to use exact integer arithmetic.