# Fibonacci Matrices

*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**

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

*n*-th Fibonacci number

*F*

_{n}by finding the

*n-1*power of matrix

**F**and multiplying it on the right by the column vector

**y**

_{1}. 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:

*p = 0*, we get the ordinary Fibonacci numbers.

*p*-Fibonacci numbers can be generated with the generalized Fibonacci matrix

**Q**

_{p}-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

**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

**Q**

_{p}

^{n}as a coding matrix and its inverse

**Q**

_{p}

^{-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.

**Q**-matrix. Let us represent the initial message in the form of the following \( 2\times 2 \) matrix

**Q**

^{5}as the coding matrix, that is,

*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

The determinant of the code matrix

**E**is

*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