Using matrices to calculate fibonacci?

Question

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?

Answer 1

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} $$