# Using matrices to calculate fibonacci?

I have been told a couple of times it possible to calculate the fibonacci sequence much quicker using matrices but I never understood/they never elaborated. Would somebody be able to show how this technique works?

Using the recursion $F_{n+2}=F_{n+1}+F_n$ and the initial $F_0=0$ and $F_1=1$, we get $$\begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{\large n} \begin{bmatrix} 1\\0 \end{bmatrix} =\begin{bmatrix} F_{n+1}\\F_n \end{bmatrix}$$ or $$F_n= \begin{bmatrix} 0&1 \end{bmatrix} \begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{\large n} \begin{bmatrix} 1\\0 \end{bmatrix}$$
We can use the Jordan decomposition $$\begin{bmatrix} 1&1\\1&0 \end{bmatrix} =\frac1{\sqrt5}\begin{bmatrix} -1/\phi&\phi\\1&1 \end{bmatrix} \begin{bmatrix} -1/\phi&0\\0&\phi \end{bmatrix} \begin{bmatrix} -1&\phi\\1&1/\phi \end{bmatrix}$$ to get that \begin{align} F_n &=\frac1{\sqrt5} \begin{bmatrix} 1&1 \end{bmatrix} \begin{bmatrix} -1/\phi&0\\0&\phi \end{bmatrix}^{\large n} \begin{bmatrix} -1\\1 \end{bmatrix}\\[6pt] &=\frac{\phi^n-(-1/\phi)^n}{\sqrt5} \end{align}
• You diagonalize the matrix so then, computing the $n$-th power is easy and you get it back in the right basis with two matrix multiplications. – xavierm02 May 10 '14 at 2:15
• You can also compute it using the binary algorithm for (matrix) powers: to find $M^7$, first find $M^2$, then $M^4=(M^2)^2$, and finally $M^7=M\cdot M^2\cdot M^4$, with a total of four (matrix) multiplications. (This can be translated directly into a recurrence for $F_{2n}$ and $F_{2n+1}$ in terms of $F_n$ and $F_{n+1}$.) This approach (which clearly should be better-known!) takes $O(\log n)$ multiplications to find $F_n$, similarly to the explicit formula, but has the strong advantage of using only integer operations rather than needing $\phi$ to high precision. – Steven Stadnicki May 10 '14 at 3:10
• Doesn’t diagonalizing the matrix and calculating the $n$-th powers of the eigenvalues amount to the same thing as using the (?) well-known closed formula for the Fibs? – Lubin May 10 '14 at 3:32