Fibonacci Matrices
\[
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 .
\]
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.
\[
{\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 .
\]