Introduction
After writing a post about one interesting way to arrive at a closed-form for the $n$th term of the Fibonacci sequence, a friend pointed out a few alternative ways to get there, one of which felt particularly natural. It requires some linear algebra, so I guess that in some sense, it could be considered “unnatural,” but I especially like it because the argument’s flow requires fewer arbitrary-seeming leaps. With that said, this post will be brief (as I’m a little busy at the moment), so if there’s anything that doesn’t make sense or is incorrect, please do reach out and let me know.
Fibonacci matrix
The Fibonacci sequence can be viewed through the lens of matrices. In particular, if we start with the matrix
we can see that the Fibonacci sequence can be materialized by repeatedly multiplying $A$ by itself.
To see this, first notice that if we are considering the Fibonacci sequence that starts with $F_0 = 0$ and $F_1 = 1$, then we note that
Suppose now that
for $n \geq 3$. Then
Thus, to get the $n$th element of the Fibonacci sequence, we need only get the upper left entry of $A^n$. If we had a fast way to obtain $A^n$ instead of actually carrying out iterated matrix multiplication, we could obtain the $n$th element without doing very much work.
Diagonalizing $A$
To do this, we will look to diagonalize $A$. This means that we will try to write
where $D$ is a diagonal matrix and $V$ is a matrix with eigenvectors of $A$ as columns (we have to actually find $D$ and $V$ that work). What’s nice about a diagonal representation is that
If $D$ is written as a matrix with $\lambda_1,\dots,\lambda_n$ on the diagonal, then $D^n$ is simply $D$ with the elements on the diagonal each taken to the $n$th power, like so:
Now that we’ve laid out our approach, it’s time to carry it out. (I will spare the algebra required to keep this post brief.)
Using $A$’s eigenvalues
The eigenvalues of $A$ (as you might expect if you read the earlier post about Fibonacci) are $\lambda_1,\lambda_2 = \frac{1 \pm \sqrt 5}{2}$, and the corresponding eigenvectors are $v_1, v_2 = \begin{bmatrix} \frac{1 \pm \sqrt 5}{2} \ 1 \end{bmatrix}$. Thus, we have
With these in hand, we see that $A$ is indeed diagonalizable, so that $A^n$ can be written as $VD^nV^{-1}$, and voila! with two matrix multiplications and exponentiating the diagonal entries of $D$, we can very quickly and efficiently come up with large Fibonacci numbers quickly.