The Fibonacci Matrix

The Fibonacci Matrix#

The Fibonacci Sequence Defined#

The Fibonacci sequence which starts \(1, 1, 2, 3, 5, 8,..\) is governed by the rule that each value after the two initial \(1\)s is the sum of the two values before it. In mathematical notation:

\[ F_1=1, F_2=1, \text{and } F_n = F_{n-1} + F_{n-2} \text{ for all integers } n>2.\]

The sequence and be extended to calculate a \(0\)th value \(F_0\), a \(-1\)th value \(F_{-1}\), etc. One only need to reverse the recursive formula \(F_n = F_{n-1} + F_{n-2}\) by solving for \(F_{n-2}\), yielding \( F_{n-2} = F_{n} - F_{n-1}\). Then \(F_n\) can be calculated for \(n=0\) and negative \(n\):

\[\begin{split} \begin{align} F_0 &= F_2 - F_1 = 1-1 = 0 \\ F_{-1} &= F_1 - F_0 = 1-0 = 1 \\ F_{-2} &= F_0 - F_{-1} = 0-1 = -1, \text{etc.} \\ \end{align} \end{split}\]

So for our purposes, let’s regard Fibonacci numbers \(F_n\) as valid for all integer values of \(n\) positive, negative, and zero. Specifically, let’s remember \(F_0 = 0\) and \(F_{-1}=1\) because we’ll use those values soon.

The Fibonacci Sequence as a Linear Combination and the Fibonacci Matrix#

The formula \(F_n = F_{n-1} + F_{n-2}\) which appears in the Fibonacci definition shows that each value in the series can be expressed as a linear combination of previous values. We can take advantage of this structure to represent Fibonacci numbers in the notation of linear algebra. Each Fibonacci number is a linear combination of two other values, so let’s define a two-element Fibonacci vector:

\[\begin{split}\vec{F_n} = \left[ \begin{matrix} F_n \\ F_{n-1} \end{matrix} \right] \end{split}\]

Then the operation which transforms \(\vec{F_n}\) into \(\vec{F_{n+1}}\) is linear. It can be implemented by multiplying by the \(2 \times 2\) Fibonacci matrix:

\[\begin{split} \Phi = \left[\begin{matrix} 1 & 1\\ 1 & 0 \end{matrix}\right] \end{split}\]

One reason for denoting this matrix with the Greek letter \(\Phi\) is because \(\Phi\) is the counterpart to the Latin letter \(F\). Another reason is that, as we’ll see later, the matrix \(\Phi\) also mimics many of the properties of the golden ratio \(\phi\).

So now we have

\[\Phi \vec{F_n} = \vec{F_{n}}_{+1}\]

from sympy import *
PhiMat = Matrix([[1, 1], [1, 0]])
Fnp1, Fn, Fnm1= symbols('F_{n+1}, F_n, F_{n-1}')
Phi = MatrixSymbol(r'\Phi', 2, 2)
FnVec = Matrix(2, 1, [Fn, Fnm1])
Fnp1Vec = Matrix(2, 1, [Fnp1, Fn])
display(Eq(Phi, PhiMat, evaluate=False))
display(Eq(Phi * FnVec, PhiMat * FnVec, evaluate=False))

\[\begin{split}\displaystyle \Phi = \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\end{split}\]

\[\begin{split}\displaystyle \Phi \left[\begin{matrix}F_{n}\\F_{n-1}\end{matrix}\right] = \left[\begin{matrix}F_{n} + F_{n-1}\\F_{n}\end{matrix}\right]\end{split}\]

\(\Phi\) is invertible with

\[\begin{split} \Phi^{-1} = \left[\begin{matrix} 0 & -1\\ -1 & 1 \end{matrix}\right]\end{split}\]

Then we can use powers of \(\Phi\) to calculate any Fibonacci vector with

\[\Phi^{n} \vec{F_0} = \vec{F_n} \text{ for any integer } n.\]

And more generally

\[\Phi^{n} \vec{F_k} = \vec{F_{k}}_{+n} \text{ for any integers } n \text{ and } k.\]

display(Eq(Phi ** -1, PhiMat ** -1, evaluate=False))
F0 = Symbol(r'\vphantom{z}F_0')
F0vec = Matrix(2, 1, [0, 1])

#An example with n = 10
#F_10=55 and F_9=34
display(Eq(MatMul(Phi ** 10, F0), PhiMat  ** 10 * F0vec, evaluate=False)) 

#An example with n = -10
#F_-10=-55 and F_-11=89
display(Eq(MatMul(Phi ** -10, F0), PhiMat  ** -10 * F0vec, evaluate=False)) 

\[\begin{split}\displaystyle \Phi^{-1} = \left[\begin{matrix}0 & 1\\1 & -1\end{matrix}\right]\end{split}\]

\[\begin{split}\displaystyle \Phi^{10} \vphantom{z}F_0 = \left[\begin{matrix}55\\34\end{matrix}\right]\end{split}\]

\[\begin{split}\displaystyle \Phi^{-10} \vphantom{z}F_0 = \left[\begin{matrix}-55\\89\end{matrix}\right]\end{split}\]

At this point, it might not be obvious what’s inside the matrix \(\Phi^n\). But the values are easy to reveal because remember that \(\vec{F_1} = \left[\begin{matrix} F_1 \\ F_0 \end{matrix}\right] \) and \(\vec{F_0} = \left[\begin{matrix} F_0 \\ F_{-1} \end{matrix}\right]\) are the unit vectors \( \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \) and \( \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] \), respectively.

So the left column of \(\Phi^n\) is given by

\[\begin{split}\Phi^n \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = \Phi^n \vec{F_1} = \vec{F_{n}}_{+1} = \left[\begin{matrix} F_{n+1} \\ F_n \end{matrix}\right] \end{split}\]

and likewise the right column of \(\Phi^n\) is

\[\begin{split}\Phi^n \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = \Phi^n \vec{F_0} = \vec{F_{n}} = \left[\begin{matrix} F_{n} \\ F_{n-1} \end{matrix}\right] \end{split}\]

Therefore, we have

\[\begin{split}\Phi^n = \left[\begin{matrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{matrix}\right] \end{split}\]

Seeing that \(\Phi^n\) contains \(F_n\), it can be practical to dispense with the \(\vec{F_n}\) vector and regard \(\Phi^n\) as representative of \(F_n\).

#Phi^n with n=10 for example.
#F_11 = 89, F_10 = 55, F_9 = 34
display(Eq(Phi ** 10, PhiMat ** 10, evaluate=False))

\[\begin{split}\displaystyle \Phi^{10} = \left[\begin{matrix}89 & 55\\55 & 34\end{matrix}\right]\end{split}\]

The Lucas Matrix#

Recalling the definition of the Lucas sequence \(L_n = F_{n-1} + F_{n+1}\), which defines the Lucas numbers as a linear combination of Fibonacci numbers, it is possible to implement this definition with matrix algebra.

\[\begin{split} \Phi^{n-1} + \Phi^{n+1} = \left[\begin{matrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{matrix}\right] + \left[\begin{matrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{matrix}\right] = \left[\begin{matrix} L_{n+1} & L_{n} \\ L_{n} & L_{n-1} \end{matrix}\right] \end{split}\]

Let’s call the last matrix a Lucas matrix and denote it \(\Lambda_n\). I choose the letter Lambda \((\Lambda)\), the Greek counterpart to the letter \(L\).

We might choose to define a special matrix that converts the Fibonacci matrix \(\Phi^n\) to the Lucas matrix \(\Lambda_n\). Since the matrix converts one sequence to another I’ll denote it \(C\).

\[\begin{split} C = \Phi^{-1} + \Phi = \left[\begin{matrix} 1 & 2\\ 2 & -1 \end{matrix}\right] \end{split}\]

\(C = \Lambda_0\), but I regard the matrix as special enough to deserve its own label. The product of a Lucas matrix with a Fibonacci matrix is another Lucas matrix. All the matrices we’re analyzing are symmetric, so multiplication is commutative:

\[ \Phi^n \Lambda_k = C \Phi^n \Phi^k = C \Phi^{n+k} = \Lambda_{n+k}. \]

Then what is the product of two Lucas matrices? Knowing that the equation \(L_n = F_{n-1} + F_{n+1}\) defines the Lucas numbers, it is possible to show that \(5F_n = L_{n-1} + L_{n+1}\). This is a clue. In fact it turns out that \(C^2 = 5I\), where \(I\) denotes the \(2 \times 2\) identity matrix.

\[ \Lambda_{n}\Lambda_{k} = C^2 \Phi^n \Phi^k = C^2 \Phi^{n+k} = 5\Phi^{n+k}. \]

\(\Phi\) Mimics the Golden Ratio \(\phi\)#

The Fibonacci matrix \(\Phi\) mimics the properties of the golden ratio \(\phi\). Let’s recap the properties of the scalar \(\phi\) and its rational conjugate \(\pb\).

\[\begin{split}\begin{align} \phi &= \frac{1+\sqrt 5}{2} && \pb = \frac{1-\sqrt 5}{2}\end{align} \\[5pt] \end{split}\]

\[\begin{split}\begin{align} &\phi + \pb = 1 && \quad \phi - \pb = \sqrt 5 &&&& \phi \times \pb = -1 \end{align}\\[5pt]\end{split}\]

\[\begin{split}\begin{align} \phi^n &= \frac{L_n+F_n\sqrt 5}{2} && \pbn{n} = \frac{L_n-F_n\sqrt 5}{2} \\[5pt] L_n &= \phi^n + \pbn{n} && F_n = \frac{\phi^n - \pbn{n}}{\sqrt 5} \\[5pt] \sqrt 5 \cdot \phi^n &= \phi^{n-1} + \phi^{n+1} && \sqrt 5 \cdot \pbn{n} = -(\pbn{n-1} + \pbn{n+1}) \\ \end{align}\end{split}\]

\[\begin{align} \phi^n &= F_n \cdot \phi + F_{n-1} &&\pbn{n} = F_n \cdot \pb + F_{n-1} \end{align}\]

Recalling that \(C\) is a matrix square root of \(5I\), it is notable that \(\Phi = \frac{I+C}{2}\). Further, we may define \(\Pb = \frac{I-C}{2}\) and amazingly these two matrices mimic all the above listed properties of \(\phi\) and \(\pb\)!

\[\begin{split}\begin{align} \Phi &= \frac{I+C}{2} && \Pb = \frac{I-C}{2}\end{align} \\[5pt] \end{split}\]

\[\begin{split}\begin{align} &\Phi + \Pb = I && \quad \Phi - \Pb = C &&&& \Phi \times \Pb = -I \end{align}\\[5pt]\end{split}\]

\[\begin{split}\begin{align} \Phi^n &= \frac{L_n\cdot I+F_n\cdot C}{2} && \Pb^{n} = \frac{L_n \cdot I-F_n \cdot C}{2} \\[5pt] L_n\cdot I &= \Phi ^n + \Pb^{n} && F_n\cdot I = (\Phi^n - \Pb^n)C^{-1} \\[5pt] C \cdot \Phi^n &= \Phi^{n-1} + \Phi^{n+1} && C \cdot \Pb^{n} = -(\Pb^{n-1} + \Pb^{n+1}) \\ \end{align}\end{split}\]

\[\begin{align} \Phi^n &= F_n \cdot \Phi + F_{n-1}\cdot I &&\Pb^{n} = F_n \cdot \Pb + F_{n-1} \cdot I \end{align}\]

Earlier we saw that \(\Phi^n\) can represent \(F_n\); Now \(\Phi^n\) mimics \(\phi^n\). It always seems to take one form or the other upon observation; Perhaps we should call it Schrodinger’s matrix!

About Square Roots of \(5I\)#

Matrix \(C\) was constructed to convert Fibonacci numbers to Lucas numbers. The fact that \(C\) is a matrix square root of \(5I\) seemed to occur by happenstance. There are infinitely matrices which are square roots of \(5I\). Some examples:

\[\begin{split} \left[\begin{matrix} \sqrt 5 & 0\\ 0 & -\sqrt 5 \end{matrix}\right] \quad \left[\begin{matrix} 0 & 1\\ 5 & 0 \end{matrix}\right] \quad \left[\begin{matrix} 2 & 1\\ 1 & -2 \end{matrix}\right] \quad \left[\begin{matrix} \sqrt 8 & \sqrt 3\\ -\sqrt 3 & -\sqrt 8 \end{matrix}\right] \end{split}\]

The Fibonacci matrix \(\Phi\) and its relative \(\Pb\) are not the only matrices that mimic the properties of scalars \(\phi\) and \(\pb\). Let \(R\) denote an arbitrary \(2 \times 2\) matrix with the property that \(R^2 = 5I\). Define \(\Phi_R = \frac{I+R}{2}\) and \(\Pb_R = \frac{I-R}{2}\). Then \(\Phi_R\) and \(\Pb_R\) also will mimic \(\phi\) and \(\pb\) in exactly the same way.