Josiah's Math Notes

Linear Algebra

Solving a Dynamic System with Matrix Diagonalization: Fibonacci

The fibonacci sequence! By employing matrix diagonalization in finding the nth fibonacci number, we can derive Binet's formula.

The fibonacci sequences starts as follows:

0, 1, 1, 2, 3, 5, 8, 13, ...

Let's start. We begin with a difference equation.

$F_{n} = F_{n-1} + F_{n-2}$

Turn this single equation into a system of two equations and two unknowns.

$F_{n} = F_{n-1} + F_{n-2} \qquad\qquad F_{n-1} = F_{n-1}$

We can use matrices to represent this system as

$\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} F_{n-1} = F_{n-1} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}$

The equation of interest is

$\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}$

First, we must generalize the equation. Let $u_{n-1} = \begin{bmatrix} u_{n} \\ u_{n-1} \end{bmatrix}$ and $\textbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ .

The equation above becomes

$u_{n-1} = \textbf{A}u_{n-2} \quad\Rightarrow\quad u_{n} = \textbf{A}u_{n-1}$

Now we have to figure out the starting point. We will define the two fibonacci numbers, $F_{0}$ and $F_{1}$ , as 0 and 1 respectively.

Based on this

$u_{0} = \begin{bmatrix} F_{1} \\ F_{0} \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

$u_{1} = \textbf{A}u_{0} \qquad u_{2} = \textbf{A}u_{1} = \textbf{A}^{2}u_{0} \qquad \cdots \qquad u_{n} = \textbf{A}^{n}u_{0}$

We now have a general formula for the entire system. To determine its behavior as $n$ gets larger and larger, we must find the eigenvalues of $\textbf{A}$ and use diagonalization.

$\textbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

$\det(\textbf{A} - \lambda\textbf{I}) = \det\left(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} - \lambda\textbf{I} \right) = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix}$

$\lambda^{2} - \lambda - 1 = 0$

We can obtain the roots to this characteristic polynomial by either completing the square or using the quadratic formula.

$\lambda^{2} - \lambda - 1 + \frac{1}{4} = \frac{1}{4}$

$(\lambda - \frac{1}{2})^{2} - 1 = \frac{1}{4}$

$(\lambda - \frac{1}{2})^{2} = \frac{5}{4}$

$\lambda = \pm\sqrt{\frac{5}{4}} + \frac{1}{2} = \frac{1 \pm \sqrt{5}}{2}$

Therefore

$\lambda_{1} = \frac{1 + \sqrt{5}}{2} \qquad \lambda_{2} = \frac{1 - \sqrt{5}}{2}$

Wow! These two numbers are the golden ratio. When we calculate the eigenvectors, we will find that

$x_{1} = \begin{bmatrix} 1 + \sqrt{5} \\ 2 \end{bmatrix} \qquad x_{2} = \begin{bmatrix} 1 - \sqrt{5} \\ 2 \end{bmatrix}$

Now that we have all of this inforamtion, we know that the matrix of eigenvectors, $\textbf{S}$ , will be

$\textbf{S} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix}$

and the diagonal matrix of eigenvalues, $\Lambda$ , will be

$\Lambda = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}$

Before we diagonalize $\textbf{A}$ , we need to find the inverse of $\textbf{S}$ . That should be pretty simple to do.

$\textbf{S}^{-1} = \frac{1}{\det\textbf{S}}\begin{bmatrix} s_{22} & -s_{12} \\ -s_{21} & s_{11} \end{bmatrix} = \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 & \sqrt{5} - 1 \\ -2 & 1 + \sqrt{5} \end{bmatrix}$

Now if we diagonalize $\textbf{A}$ , it can be written as

$\textbf{A} = \textbf{S}\Lambda\textbf{S}^{-1}$

and the system now looks like this:

$u_{n} = \textbf{A}^{n}u_{0} = \textbf{S}\Lambda^{n}\textbf{S}^{-1}u_{0}$

$u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}^{n} \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 & \sqrt{5} - 1 \\ -2 & 1 + \sqrt{5} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

With this, we can work to simplify.

$u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} 1 + \sqrt{5} & 1 - \sqrt{5} \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \left(\frac{1 + \sqrt{5}}{2}\right)^{n} & 0 \\ 0 & \left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix} \frac{1}{4\sqrt{5}} \begin{bmatrix} 2 \\ -2 \end{bmatrix}$

$u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} (1 + \sqrt{5})\left(\frac{1 + \sqrt{5}}{2}\right)^{n} & (1 - \sqrt{5})\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} & 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix} \frac{1}{2\sqrt{5}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}$

$u_{n} = \begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix} = \frac{1}{2\sqrt{5}}\begin{bmatrix} (1 + \sqrt{5})\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \end{bmatrix} - \frac{1}{2\sqrt{5}}\begin{bmatrix} (1 - \sqrt{5})\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \\ 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n} \end{bmatrix}$

We are only interesting in the second row of the solution because it gives us the formula for the nth fibobacci number. It tells us

$F_{n} = \left(\frac{1}{2\sqrt{5}}\right) 2\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1}{2\sqrt{5}}\right) 2\left(\frac{1 - \sqrt{5}}{2}\right)^{n}$

$F_{n} = \left(\frac{1}{\sqrt{5}}\right) \left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1}{\sqrt{5}}\right) \left(\frac{1 - \sqrt{5}}{2}\right)^{n}$

$F_{n} = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}}{\sqrt{5}}$

And finally, we have arrived at Binet's formula.