Diagonalizability in Action
What does Fibonacci have to do with matrices and vectors?
Matrix form
We all know the Fibonacci sequence:
\[ 0,1,1,2,3,5,8,\cdots \]
Is there a closed form expression for the \(n^{th}\) term in the Fibonacci sequence? In simpler terms, is there a formula that will give us the \(n^{th}\) term? Let us try to use linear algebra to answer this question. \(F_{k}\) is the \(k^{th}\) term in the sequence. Then we have the following pair of equations:
\[ \begin{aligned} F_{k+2} & =1\cdot F_{k+1} +1\cdot F_{k}\\ F_{k+1} & =1\cdot F_{k+1} +0\cdot F_{k} \end{aligned} \]
This can be represented as the following matrix equation:
\[ \begin{bmatrix} F_{k+2}\\ F_{k+1} \end{bmatrix} =\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} F_{k+1}\\ F_{k} \end{bmatrix} \]
If we use the variables:
\[ \mathbf{A} =\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} ,\ \ \ \mathbf{u}_{k} =\begin{bmatrix} F_{k+1}\\ F_{k} \end{bmatrix} \]
We can restate the equation as:
\[ \mathbf{u}_{k+1} =\mathbf{Au}_{k} \]
First, we start with \(\mathbf{u}_{0}\):
\[ \mathbf{u}_{0} =\begin{bmatrix} 1\\ 0 \end{bmatrix} \]
Then, the next set of terms can be obtained by pre-multiplying this equation by \(\mathbf{A}\):
\[ \begin{aligned} \mathbf{u}_{1} & =\mathbf{Au}_{0}\\ & \\ & =\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} 1\\ 0 \end{bmatrix}\\ & \\ & =\begin{bmatrix} 1\\ 1 \end{bmatrix} \end{aligned} \]
And then \(\mathbf{u}_{2}\):
\[ \begin{aligned} \mathbf{u}_{2} & =\mathbf{Au}_{1}\\ & \\ & =\mathbf{A}^{2}\mathbf{u}_{0}\\ & \\ & =\begin{bmatrix} 2\\ 1 \end{bmatrix} \end{aligned} \]
Generalizing this, we have:
\[ \mathbf{u}_{k} =\mathbf{A}^{k}\mathbf{u}_{0} \]
Diagonalization
In the section on diagonalization, we have seen some useful properties of a diagonalizable matrix. If \(\mathbf{A}\) is diagonalizable, then \(\mathbf{A}^{k}\) can be computed quite easily. Is the matrix \(\mathbf{A}\) in our example diagonalizable? Let us find out. First, we need to get hold of the eigenvalues of \(\mathbf{A}\):
\[ \begin{aligned} \begin{vmatrix} 1-\lambda& 1\\ 1 & -\lambda \end{vmatrix} & =0\\ & \\ (1-\lambda)(-\lambda)-1 & =0\\ & \\ \lambda^{2} -\lambda-1 & =0\\ & \\ \lambda& =\cfrac{1\pm \sqrt{5}}{2} \end{aligned} \]
We see that the eigenvalues are:
\[ \lambda_{1} =\cfrac{1-\sqrt{5}}{2} ,\lambda_{2} =\cfrac{1+\sqrt{5}}{2} \]
Since, we have two distinct eigenvalues for a \(2\times 2\) matrix, the matrix should have \(2\) linearly independent eigenvectors, hence it is diagonalizable. Next we move to eigenvectors. If \(\lambda\) is one of the two eigenvalues, then:
\[ \begin{aligned} (\mathbf{A} -\lambda\mathbf{I} )\mathbf{v} & =0\\ & \\ \begin{bmatrix} 1-\lambda& 1\\ 1 & -\lambda \end{bmatrix}\begin{bmatrix} v_{1}\\ v_{2} \end{bmatrix} & =\begin{bmatrix} 0\\ 0 \end{bmatrix}\\ & \\ \cfrac{v_{1}}{v_{2}} & =\lambda \end{aligned} \]
From this, we get two linearly independent eigenvectors corresponding to \(\lambda_{1}\) and \(\lambda_{2}\) respectively:
\[ \begin{bmatrix} \lambda_{1}\\ 1 \end{bmatrix} ,\ \ \begin{bmatrix} \lambda_{2}\\ 1 \end{bmatrix} \]
We let:
\[ \mathbf{P} =\begin{bmatrix} \lambda_{1} & \lambda_{2}\\ 1 & 1 \end{bmatrix} ,\ \ \ \mathbf{D} =\begin{bmatrix} \lambda_{1} & 0\\ 0 & \lambda_{2} \end{bmatrix} \]
Then:
\[ \mathbf{A} =\mathbf{PDP}^{-1} \]
Using Gaussian elimination, we can compute \(\mathbf{P}^{-1}\) to be:
\[ \mathbf{P}^{-1} =\cfrac{1}{\lambda_{1} -\lambda_{2}}\begin{bmatrix} 1 & -\lambda_{2}\\ -1 & \lambda_{1} \end{bmatrix} \]
The Formula
The \(k^{th}\) term of the Fibonacci sequence is:
\[ \mathbf{u}_{k} =\mathbf{A}^{k}\mathbf{u}_{0} \]
This translates to:
\[ \begin{aligned} \mathbf{u}_{k} & =(\mathbf{PDP}^{-1} )^{k}\mathbf{u}_{0}\\ & \\ & =\mathbf{PD}^{k}\mathbf{P}^{-1}\mathbf{u}_{0} \end{aligned} \]
All the quantities on the RHS are known. Let us just plug them in:
\[ \begin{aligned} \mathbf{u}_{k} & =\mathbf{PD}^{k}\mathbf{P}^{-1}\mathbf{u}_{0}\\ & \\ & =\cfrac{1}{\lambda_{1} -\lambda_{2}}\begin{bmatrix} \lambda_{1} & \lambda_{2}\\ 1 & 1 \end{bmatrix}\begin{bmatrix} \lambda_{1}^{k} & 0\\ 0 & \lambda_{2}^{k} \end{bmatrix}\begin{bmatrix} 1 & -\lambda_{2}\\ -1 & \lambda_{1} \end{bmatrix}\begin{bmatrix} 1\\ 0 \end{bmatrix}\\ & \\ & =\cfrac{1}{\lambda_{1} -\lambda_{2}}\begin{bmatrix} \lambda_{1}^{k+1} -\lambda_{2}^{k+1}\\ \lambda_{1}^{k} -\lambda_{2}^{k} \end{bmatrix} \end{aligned} \]
Recall that \(\mathbf{u}_{k} =\begin{bmatrix} F_{k+1}\\ F_{k} \end{bmatrix}\). Therefore, we have:
\[ F_{k} =\cfrac{1}{\lambda_{1} -\lambda_{2}}\left( \lambda_{1}^{k} -\lambda_{2}^{k}\right) \]
Substituting for \(\lambda_{1}\) and \(\lambda_{2}\):
\[ \boxed{F_{k} =\cfrac{1}{\sqrt{5}}\left[\left(\cfrac{1+\sqrt{5}}{2}\right)^{k} -\left(\cfrac{1-\sqrt{5}}{2}\right)^{k}\right]} \]
Isn’t that a thing of beauty? Can you imagine that expression on the RHS being an integer for every value of \(k\), with a number like \(\sqrt{5}\) rearing its irrational face in the formula?
Summary
On the surface, the Fibonacci sequence seems to belong to a different world. Vectors and matrices may look like aliens to members of the sequence. And yet there is a hidden link that exists between the two. Diagonalization helps us uncover this link.