2
$\begingroup$

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.

  • 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.2012-10-08

1 Answers 1

3

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.