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 are a sequence of numbers such that every term is a sum of the previous two terms: . The first few terms of this series are 0,1,1,2,3,5,8,13..
Linear Dynamical System
Consider a N-dimensional vector . Assume that the variation of with respect to time, when it varies in discrete steps may be represented as: , where A is constant matrix Such a system is called a Linear Dynamical System. For example, 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:
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 , where A is the constant matrix as above.
The matrices S and
The matrix S is said to be the Eigen vector matrix, i.e , considering are the n Eigen vectors of the constant matrix A, defined above. The matrix is a diagonal matrix defined as follows:
where are the Eigen vectors of the same matrix.
From the basic equation of Eigen values and vectors , we can write the above as . From this equation, we can write :
This is an useful and important relationship. How? Earlier, we wrote: , ,
Now, substitute by . can be written in a more simplified manner, by writing it as a combination of its Eigen vectors, where is a coefficient matrix, from which we can write . Thus we have:
So what does the last equation say? It says, the current state ( state) of our model is expressed as matrix obtained by the product of the Eigen vector matrix , the Eigen value matrix , raised to the power and the matrix .
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: and . The Eigen vectors of A turns out to be and .
The coefficient matric
As derived earlier, . We already have , turns out to be:
The first two Fibonacci numbers are 1,1, so we can take . Hence:
Finding the Nth Fibonacci Number
Now, let’s rewrite the earlier equation , 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 and Fibonacci numbers. For example, let n=0 and see the values of and , 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 (firstname.lastname@example.org) # 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],]) mat2 = np.matrix([[eig_vec2],]) # 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)
A very interesting thing to note here is that the second term of the last equation, contains the term . 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