Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Or just use $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}$. – Gamma Function May 10 '14 at 2:08

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

share|cite|improve this answer
To turn this into a «quicker way» one needs to be smart about computing the matrix powers, though. – Mariano Suárez-Alvarez May 10 '14 at 2: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 2:09
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.