Matrix Diagonalization

The Fibonacci sequence is defined as: $$0,1,1,2,3,5,8,13....$$ we can write it has $$F_n=F_{n-1}+F_{n-2},\text{with}{F}_0=0,F_1=1$$

Lets make a recursive implementation:

import timeit

# Recursive Fibonacci function
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# Timing the Fibonacci function
n = 10  # Example Fibonacci number
execution_time = timeit.timeit(lambda: fibonacci(n), number=1)
print(f"Fibonacci({n}) = {fibonacci(n)}")
print(f"Execution time: {execution_time:.6f} seconds")

which is not much but if we choose n like 36 it takes

In this post I will show how we can do better using Linear Algebra

Matrix Representation of the Fibonacci Sequence

We can represent the Fibonacci recurrence relation using matrices. Consider the vector x(n) :

$$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]$$

The recurrence relation can be rewritten as:

$$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=\left[\begin{array}{c}{F}_{n-1}+F_{n-2}\\ F_{n-1}\end{array}\right]$$

we can express it by matrix multiplication:

$$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right]$$

Let's denote the matrix: $$A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$ hence $$\left[\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right]=A\left[\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right]$$ or $$x(n)=A\left[\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right]$$ we can rewrite it has:

$$x(n)=A\times x(n-1)$$

if we start with $$x(1)=\left[\begin{array}{c}1\\ 0\end{array}\right]$$

then $$x(2)=A\times x(1)$$ so on $$x(3)=A\times x(2)=A^2\times x(1)$$

$$...$$

$$x(n)=A^{n-1}\times x(1)$$

we can Diagonalize Matrix A in form of:

$$A=M\times D\times M^{-1}$$

where D is a Diagonal Matrix containing eigenvalues of A

now

$$A^2=M\times D\times M^{-1}\times M\times D\times M^{-1}$$

we see we can cancel out $M$ and $M^{-1}$

so

$$x(n)=M\times D^{n-1}\times M^{-1}\times x(1)$$

Lets do Diagonalization of A

import numpy as np

A = np.array([[1, 1],
              [1, 0]])
eigenvalues, eigenvectors = np.linalg.eig(A)
D = np.diag(eigenvalues)
M = eigenvectors
M_inv = np.linalg.inv(M)

D,M,M_inv

New Fibonacci Implementation

import timeit
import numpy as np

def fibonacci(n):

  D = np.array(np.array([[1.61803399,0],[0,-0.61803399]]))

  M = np.array([[ 0.85065081, -0.52573111],
        [ 0.52573111,  0.85065081]])

  M_inv = np.array([[ 0.85065081,  0.52573111],
        [-0.52573111,  0.85065081]])

  x1 = np.array([1,0])

  res = [email protected]_power(D,n-1)@M_inv@x1

  return int(res[0])

# Timing the Fibonacci function
n = 36  # Example Fibonacci number
execution_time = timeit.timeit(lambda: fibonacci(n), number=1)
print(f"Fibonacci({n}) = {fibonacci(n)}")
print(f"Execution time: {execution_time:.6f} seconds")