Fibonacci Matrices

Leonardo Fibonacci
Fibonacci numbers are given with the following recurrence relation
\[ F_{n+1} = F_n + F_{n-1} , \qquad F_0 =0, \ F_1 = 1 , \qquad n= 0, \pm 1, \pm 2, \ldots . \]
Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by the influential ancient scholar Pingala (from India) on enumerating possible patterns of poetry formed from syllables of two lengths. The Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, known later by his nickname Fibonacci. His 1202 book Liber Abaci (meaning "The Book of Calculation") introduced the sequence (as well as Hindu-Arabic numbers) to Western European mathematicians, although the sequence had been described earlier in Indian mathematics. These numbers can be computed with the aid of the Fibonacci matrix
\[ {\bf Q} = \begin{bmatrix} 1& 1 \\ 0 & 1 \end{bmatrix} \qquad \Longrightarrow \qquad {\bf Q}^n = \begin{bmatrix} F_{n+1}& F_n \\ F_n & F_{n-1} \end{bmatrix} , \qquad n= 0, \pm 1, \pm 2, \ldots . \]
The determinant of the above power matrix satisfy so called ‘‘Cassini formula’’ in honor of the well-known 17th century astronomer Giovanni Domenico Cassini (1625--1712) who derived this formula:
\[ \det \,{\bf Q}^n = F_{n+1}\, F_{n-1} - F_n^2 = (-1)^n , \qquad n= 0, \pm 1, \pm 2, \ldots . \]

Giovanni Cassini
Cassini was an Italian (naturalised French) mathematician and engineer. He was born in Perinaldo, near Imperia, at that time in the County of Nice, part of the Savoyard state. Cassini is known for his work in the fields of astronomy and engineering. In 1669, Cassini moved to France and through a grant from Louis XIV of France helped to set up the Paris Observatory, which opened in 1671. Later, Cassini discovered four satellites of the planet Saturn and noted the division of the rings of Saturn; the Cassini Division was named after him. Giovanni Domenico Cassini was also the first of his family to begin work on the project of creating a topographic map of France.

The Fibonacci recurrence relation \( F_n = F_{n-1} + F_{n-2} \) can be expressed in matrix form:

\[ \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} , \qquad n = 2,3, \ldots . \]
Thus, if we set
\[ {\bf y}_n = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} \qquad\mbox{and} \qquad {\bf F} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} , \qquad n = 1,2,3, \ldots . \]
we find that
\[ {\bf y}_n = {\bf F}\,{\bf y}_{n-1} , \qquad n = 1,2,3, \ldots . \]
Applying the above recurrence repeatedly, we obtain
\[ {\bf y}_n = {\bf F}^{n-1} {\bf y}_{1} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}^{n-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} , \qquad n = 1,2,3, \ldots . \]
Thus, we can compute the n-th Fibonacci number Fn by finding the n-1 power of matrix F and multiplying it on the right by the column vector y1. We will learn later how to find any power of a matrix avoiding tedious job.

In 1977, the Russian mathematician A.P. Stakhov introduced so-called Fibonacci p-numbers:

\[ F_{p} (n) = F_{p} (n-1) + F_p (n-p-1) , \qquad \mbox{with} \quad n \ge p+2 , \]
subject to the initial conditions
\[ F_{p} (1) = F_{p} (2) = \cdots = F_p (p+1) . \]
When p = 0, we get the ordinary Fibonacci numbers.
The p-Fibonacci numbers can be generated with the generalized Fibonacci matrix
\[ {\bf Q}_p = \begin{bmatrix} 1&1&0&0&\cdots &0&0 \\ 0&0&1&0& \cdots &0&0 \\ 0&0&0&1& \cdots &0&0 \\ \vdots&\vdots&\vdots&\vdots& \ddots &\vdots&\vdots \\ 0&0&0&0& \cdots &1&0 \\ 0&0&0&0& \cdots &0&1 \\ 1&0&0&0& \cdots &0&0 \end{bmatrix} . \]
Note that the Qp-matrix is a square (p + 1)-by-(p + 1) matrix. It contains a \( p\times p \) identity matrix bordered by the last row of 0’s and the first column, which consists of 0’s bordered by 1’s. The integer powers of the generalized Fibonacci matrix satisfy the Cassini identity
\[ \det\,{\bf Q}_p^n = (-1)^{np} , \qquad\mbox{for} \quad p = 1,2,\ldots . \]
The generalized Fibonacci matrices allow us to develop the following application to coding theory. Let us represent an initial message in the form of the square matrix M of the size \( (p+1)\times (p+1) , \) where \( p=0,1,2,\ldots . \) Let us choose the \( (p+1)\times (p+1) \) generalized Fibonacci matrix Qpn as a coding matrix and its inverse Qp-n of the same size as a decoding matrix. We will name a transformation \( {\bf M} \times {\bf Q}_p^n = {\bf E} \) as Fibonacci coding and a transformation \( {\bf E} \times {\bf Q}_p^{-n} = {\bf M} \) as Fibonacci decoding. We will name the matrix E as code matrix.
Example: Let us consider now the simplest Fibonacci coding/decoding method based on application of the classical Fibonacci Q-matrix. Let us represent the initial message in the form of the following \( 2\times 2 \) matrix
\[ {\bf M} = (-1\begin{bmatrix} m_1 & m_2 \\ m_3 & m_4 \end{bmatrix} . \]
Let us assume that all elements of the matrix are positive integers, that is
\[ m_1 \ge 0; \quad m_2 \ge 1; \quad m_3 \ge 1; \quad m_4 \ge 1. \]
Let us assume now that we have selected the Fibonacci matrix Q5 as the coding matrix, that is,
\[ {\bf Q}^5 = \begin{bmatrix} 8 & 5 \\ 5 & 3 \end{bmatrix} \qquad \Longrightarrow \qquad {\bf Q}^{-5} = \begin{bmatrix} -3 & 5 \\ 5 & -8 \end{bmatrix} . \]
Then the Fibonacci coding of the message consists in its multiplication by the ‘‘direct’’ coding matrix
\[ {\bf M} \times {\bf Q}^5 = \begin{bmatrix} m_1 & m_2 \\ m_3 & m_4 \end{bmatrix} \begin{bmatrix} 8 & 5 \\ 5 & 3 \end{bmatrix} = \begin{bmatrix} 8\,m_1 + 5\,m_2 & 5\,m_1 + 3\,m_2 \\ 8\,m_3 + 5\,m_4 & 5\,m_3 + 3\,m_4 \end{bmatrix} = \begin{bmatrix} e_1 & e_2 \\ e_3 & e_4 \end{bmatrix} = {\bf E} . \]
Then the code message \( E = e_1 , e_2 , e_3 , e_4 \) is sent to a channel. The decoding of the code message E given with the inverse matrix is performed in the following manner. The code message E that is represented in the matrix form is multiplied by the inverse matrix
\[ {\bf E} \times {\bf Q}^{-5} = \begin{bmatrix} e_1 & e_2 \\ e_3 & e_4 \end{bmatrix} \begin{bmatrix} -3 & 5 \\ 5 & -8 \end{bmatrix} = \begin{bmatrix} m_1 & m_2 \\ m_3 & m_4 \end{bmatrix} = {\bf M} . \]

The determinant of the code matrix E is
\[ \det\,{\bf E} = \det\,{\bf M} \times (-1)^{pn} . \]
The coding/decoding method considered above gives interesting possibility to detect and correct ‘‘errors’’ in the code message E. The main idea of error detection and correction is based on the property of the matrix determinant given by above formula. This mathematical relation plays an important role of ‘‘checking relations’’ of the Fibonacci coding/decoding method.

The error correcting codes are used widely in modern computer systems and computer networks. The main idea of modern algebraic error correcting codes consists in the following. A n-bit redundant code combination consists of two groups of bits, k information bits and m checking bits formed from the information bits by modulo 2 addition of certain groups of information bits. A minimal code distance (Hamming’s distance), which determines a code ability to detect and correct errors of given multiplicity, is a principal parameter of redundant code.

Recurrences

We consider arbitrary difference equation with constant coefficients

\[ \det\,{\bf E} = \det\,{\bf M} \times (-1)^{pn} . \]
We express this relation in matrix form:
\[ {\bf y}_n = \begin{bmatrix} y_n \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} p&q \\ 1 & 0 \end{bmatrix} \,\begin{bmatrix} y_{n-1} \\ y_{n-2} \end{bmatrix} = {\bf A}\, {\bf y}_{n-1} . \]
Then
\[ {\bf y}_n = \begin{bmatrix} p&q \\ 1 & 0 \end{bmatrix}^{n-1} \,\begin{bmatrix} y_{1} \\ y_{0} \end{bmatrix} = {\bf A}^{n-1} {\bf y}_1 . \]