The Fibonacci sequence by matrix similarity transform

P6.5.5The Fibonacci sequence by matrix similarity transform

(a) The matrix

\mathbf{F} = \left( \begin{array}{ll}1 & 1\\1 & 0\end{array} \right)

can be used to produce the Fibonacci sequence by repeated multiplication: the element $F^n_{11}$ of the matrix $\mathbf{F}^n$ is the $$(n+1)$$ th Fibonacci number (for $n=0,1,2\cdots$ ). Use NumPy's matrix objects to calculate the first 10 Fibonacci numbers.

(b) One can show that

\mathbf{F}^n = \mathbf{C}\mathbf{D}^n\mathbf{C}^{-1}, \quad\mathrm{where}\quad \mathbf{D} = \mathbf{C}^{-1}\mathbf{F}\mathbf{C}

is the diagonal matrix related to $\mathbf{F}$ through the similarity transformation associated with matrix $\mathbf{C}$ . Use this relationship to find the $$1100$$ th Fibonacci number.

Show solution

(a) Since this method of calculating the Fibonacci sequence is rather round-about anyway, we can tolerate the inefficiency of the most obvious implementation:

import numpy as np

F = np.matrix('1 1; 1 0')

for n in range(10):
    print((F**n)[0,0], end=' ')
print()

(b) The necessary matrix eigenvalue, eigenvector and inverse operations are provided by numpy.linalg. Note that the value for $$F_n$$ obtained will be approximate for all but the smallest values of $$n$$ because of the finite floating point precision of the calculations.

import numpy as np

F = np.matrix('1 1; 1 0')
(lam1, lam2), C = np.linalg.eig(F)
Ci = np.linalg.inv(C)

def fib(n):
    D = np.matrix( [[lam1**n, 0], [0, lam2**n]] )
    M = C * D * Ci
    return int(M[0,0])

n = 1100
print('F({:d}) = {:d}'.format(n, fib(n-1)))

The output is:

F(1100) = 3442859285241154346892196225573457671992103442062265067036882365866370
86258589521820944507296037626279970501040816716437642709859166330016558491460760
02833721609607394223286654158912580200000298063796245829929013387821468870508544