3

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?

user997112
  • 389

1 Answers1

5

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

robjohn
  • 345,667
  • 2
    To turn this into a «quicker way» one needs to be smart about computing the matrix powers, though. – Mariano Suárez-Álvarez May 10 '14 at 02:06
  • So you are saying to calculate f(7) I need to multiply the {(1,1),(1,0)} matrice by itself 7 times and then multiply the result with (1,0)? Sorry its been a while since I used matrices. – user997112 May 10 '14 at 02:09
  • 1
    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 02:15
  • No, you can diagonalize the matrix. – Gamma Function May 10 '14 at 02:15
  • 2
    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 03:10
  • 1
    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 03:32
  • @Lubin: yes, it does. I have just added that to my answer. – robjohn May 10 '14 at 04:37
  • @StevenStadnicki, you don't need to compute using high precision: since phi generates a quadratic extension of the rationals, you can compute there (and then this amounts more or less to the same thing as computing powers of matrix, but a different matrix) – Mariano Suárez-Álvarez May 10 '14 at 05:13