Mathematics | Programming and writing about it.

Eigen values, vectors and Fibonacci sequence

I came across application of using Eigen values and Eigen vectors to find the N’th Fibonacci number very easily in Prof. Gilbert Strang’s lecture series.

Fibonacci numbers

Fibonacci numbers are a sequence of numbers such that every term is a sum of the previous two terms: $F_{n+2} = F_{n} + F_{n+1}$ . The first few terms of this series are 0,1,1,2,3,5,8,13..

Linear Dynamical System

Consider a N-dimensional vector $\vec{X}$ . Assume that the variation of $\vec{X}$ with respect to time, when it varies in discrete steps may be represented as: $X_{t+1}=AX_{t}$ , where A is constant matrix Such a system is called a Linear Dynamical System. For example, $X_{n+1}=2X_n$ is a simple Linear Dynamical System.

Fibonacci Number sequence as a Linear Dynamical system

Let us now make an attempt to model the Fibonacci number sequence as a Linear Dynamical System. This is our first step towards this beautiful application of Eigen values and vectors.

Consider the following equations:

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

The second equation is written to enable us to write the above as a Linear dynamical system. Now, can we write the above equations as follows:
$\left[ \begin{array}{cc} F_{n+2} \\ F_{n+1} \\ \end{array} \right] = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} \right] \left [ \begin{array}{cc} F_{n+1} \\ F_{n} \\ \end{array} \right]$

which is of the form $U_{n+1}=AU_{n}$ , where A is the constant matrix as above.

The matrices S and $\Lambda$

The matrix S is said to be the Eigen vector matrix, i.e $S= [x_1 x_2 .. x_n]$ , considering $x_1, x_2, , x_n$ are the n Eigen vectors of the constant matrix A, defined above. The $\Lambda$ matrix is a diagonal matrix defined as follows:
$\begin{bmatrix} \lambda{_1} & 0 & 0 & .. & 0\\ 0 & \lambda_{2} & 0 & .. & 0\\ 0 & 0 & \lambda_{3} & .. & 0\\ . & . & . & . & 0 \\ 0 & .& . & . & \lambda_{n} \\ \end{bmatrix}$
where $\lambda_{1}, \lambda_{2}, \lambda_{3}, .. \lambda_{n}$ are the Eigen vectors of the same matrix.

From the basic equation of Eigen values and vectors $Ax= \lambda x$ , we can write the above as $AS=S\Lambda$ . From this equation, we can write : $A = S \Lambda S^{-1} , AA = (S\Lambda S^{-1}) (S\Lambda S^{-1}), AA = S\Lambda (S^{-1}S) \Lambda S^{-1} = S\Lambda ^{2}S^{-1}, A^2 = S\Lambda ^{2}S^{-1} , A^n = S\Lambda ^{n}S^{-1}$

This is an useful and important relationship. How? Earlier, we wrote: $U_{n+1} = AU_{n}$ , $U_{1} = AU_{0}$ , $U_{2} =AU_{1} = A(AU_{0}) = A^{2}U_0$ $U_n = A^{n}U_{0}$

Now, substitute $A^n$ by $S\Lambda ^{n}S^{-1}$ . $U_0$ can be written in a more simplified manner, by writing it as a combination of its Eigen vectors, $U_0=Sc$ where $c$ is a coefficient matrix, from which we can write $c=S^{-1}U_0$ . Thus we have:

$U_n = S\Lambda ^{n}S^{-1}Sc$

$U_n = S\Lambda ^{n}c$

So what does the last equation say? It says, the current state ( $n^{th}$ state) of our model is expressed as matrix obtained by the product of the Eigen vector matrix $S$ , the Eigen value matrix $\Lambda$ , raised to the power $k$ and the matrix $c$ .

Let us now make use of this equation to get the Nth Fibonacci number.

Eigen Values and Vectors of A

The Eigen values of A can be shown to be: $\lambda_{1}= \frac{1+\sqrt{5}}{2}$ and $\lambda_{2}= \frac{1-\sqrt{5}}{2}$ . The Eigen vectors of A turns out to be $x_1 = \frac{1+\sqrt(5)}{2}$ and $x_2 = \frac{1-\sqrt(5)}{2}$ .

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

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

The coefficient matric $c$
As derived earlier, $c=S^{-1} u_0$ . We already have $S$ , $S^{-1}$ turns out to be:
$\begin{bmatrix} \frac{1}{\sqrt{5} & \frac{\sqrt{5}-1}{2\sqrt{5}}} \\ -\frac{1}{\sqrt{5} & \frac{\sqrt{5}+ 1}{2\sqrt{5}}} \\ \end{bmatrix}$

The first two Fibonacci numbers are 1,1, so we can take $u_0 =\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ . Hence:
$c=\begin{bmatrix} \frac{5 + \sqrt{5}}{10} \\ \frac{5 - \sqrt{5}}{10} \\ \end{bmatrix}$

Finding the Nth Fibonacci Number

Now, let’s rewrite the earlier equation $U_n = S\Lambda ^{n}c$ , by substituting the values such that it matches our Fibonacci model:

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

We can rewrite the above equation as follows:

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

So, we have it! Just substitute the value of ‘n’ and we get the $F_{n+1}$ and $F_{n+2}$ Fibonacci numbers. For example, let n=0 and see the values of $F_1$ and $F_2$ , they should come out to be 1, 1 respectively. This piece of Python code prints the first ‘n’ Fibonacci numbers using the above formulae:

#!/usr/bin/python
# Print fibonacci numbers by forming it as a linear dynamical
# system
# Amit Saha (amitsaha.in@gmail.com)
# https://amitksaha.wordpress.com

import math
import numpy as np

# Eigen vectors of A
eig_vec1= (1.0 + math.sqrt(5))/2.0
eig_vec2= (1.0 - math.sqrt(5))/2.0

# coefficients
c_1 = ((5.0 + math.sqrt(5.0))/10.0)
c_2 = ((5.0 - math.sqrt(5.0))/10.0)

# matrices
mat1 = np.matrix([[eig_vec1],[1]])
mat2 = np.matrix([[eig_vec2],[1]])

# set n accordingly to get the first (n+1) fibonacci numbers
n=99
for n in range(0,n):
    sum_mat = (eig_vec1**n)*c_1*mat1 + (eig_vec2**n)*c_2*mat2
    print float(sum_mat[1])

Parting notes

A very interesting thing to note here is that the second term of the last equation, contains the term $\frac{1-\sqrt{5}}{2}$ . The absolute value of this term t is between 0 and 1, hence as ‘n’ increases its value goes closer and closer to 0 and almost vanishes. Thus, with large values of ‘n’, the value of the above expression can be assumed to be determined by the first term. This has an interesting implication, for which I shall direct you to this awesome post.

Also check Project Euler problem #2: http://projecteuler.net/problem=2

Programming and writing about it.

Category: Mathematics

February 2, 2010

Eigen values, vectors and Fibonacci sequence

March 22, 2009

The Music of Primes