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