Eigen values, vectors and Fibonacci sequence

by Amit


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:

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:

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

The coefficient matric c
As derived earlier,  c=S^{-1} u_0. We already have S, S^{-1} turns out to be:

The first two Fibonacci numbers are 1,1, so we can take u_0 =\begin{bmatrix} 1 \\ 1 \end{bmatrix}. Hence:

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:

We can rewrite the above equation as follows:

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

Advertisements