Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
add comment

1 Answer

I think you are expected to compute the power by using the Binary Method for Exponentiation.. The idea is of great usefulness in computation, so there are many variant executions. We give one which is simple to describe, but somewhat inefficient, because of the storage requirements. However, it is not hard to modify things so that little storage is required.

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.