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}, \quad \text{with} \quad F_0 = 0, \quad 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) :

$$ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} $$

The recurrence relation can be rewritten as:

$$ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}= \begin{bmatrix} F_{n-1} + F_{n-2} \\ F_{n-1} \end{bmatrix} $$

we can express it by matrix multiplication:

$$ \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} $$

Let's denote the matrix: $$ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$ hence $$ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}= A \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} $$ or $$ x(n)= A \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} $$ we can rewrite it has:

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

if we start with $$ x(1) = \begin{bmatrix} 1 \\ 0 \end{bmatrix} $$

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")