Companion matrices and Golden-Fibonacci sequences

Abstract

We assign a companion sequence to a given companion matrix. Given a companion matrix $\mathbf{C}$, we make use of the associated companion sequence to provide a simple closed-form expression for $\mathbf{C}^n$, the nth power of $\mathbf{C}$. We determine conditions under which a given companion matrix $\mathbf{C}$ is a primitive matrix. A systematic method for obtaining the limit values of a companion sequence is provided. A new class of primitive companion matrices is introduced for which the limit values of the related companion sequences are connected with the Golden ratio $\uptau =\frac{1+\sqrt{5}}{2}$. In fact, a new generalization of the well-known $\mathbf{Q}$-matrix and the ordinary Fibonacci numbers are presented in this paper. This generalized form of the Fibonacci numbers will be referred to as the Golden-Fibonacci sequence. We show that the limit values of a Golden-Fibonacci sequence are powers of the Golden ratio. We apply primitive companion matrices as encoder matrices and introduce a type of error-correcting codes to be called companion coding. We show that the error-correcting relations of companion coding are connected with the limit values of the related companion sequence.

1 Introduction

A type of applicable matrices in linear algebra is known as companion matrices [1, 2]. An $p \times p$ companion matrix is defined by

$$\begin{aligned} \mathbf{C}_p=Com(u_p,u_{p-1},\ldots ,u_2,u_1)= \left( \displaystyle \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 0 &{}1 &{}0 &{}\cdots &{}\cdots &{}0 \\ 0 &{}0 &{}1 &{}\ddots &{}\ddots &{}\vdots \\ \vdots &{}\ddots &{}\ddots &{}\ddots &{}\ddots &{}\vdots \\ \vdots &{}\ddots &{}\ddots &{}\ddots &{}\ddots &{}0 \\ 0 &{}\cdots &{}\cdots &{}0 &{}0 &{}1 \\ u_p &{}u_{p-1} &{}\cdots &{}\cdots &{}u_2 &{}u_1 \\ \end{array} \right) \end{aligned}$$

(1)

wherein $u_1,u_2,\ldots ,u_p$ are some integer numbers with $u_i\ge 0$, $1\le i \le p-1$, and $u_p>0$. In this paper, the (i, j)th entry of a companion matrix $\mathbf{C}_p$ is denoted by $c_p(i,j)$.

In linear algebra [2, 3], a matrix $\mathbf{A}$ with non-negatives entries is called primitive, denoted $\mathbf{A}^m>0$, if for some integer m all entries of $\mathbf{A}^m$ are positive integer numbers. In Sect. 3 we determine the values of $u_i$’s of a companion matrix $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots ,u_1)$ such that $\mathbf{C}_p$ is a primitive matrix.

The classical Fibonacci sequence is defined by $f_n=f_{n-1}+f_{n-2}$, for $n\ge 2$, with the initial values $f_0=0$ and $f_1=1$ [4]. The limit value of this Fibonacci sequence is called the Golden ratio and is defined by $\uptau :=\lim _{n \rightarrow \infty }\frac{f_{n+1}}{f_n}=\frac{1+\sqrt{5}}{2}$ [4]. The Golden ratio has various applications in mathematics for instance in coding and information theory [5,6,7].

One of the important matrices related to the extension of Fibonacci sequence is the Q-matrix [4]. By (1), the $\mathbf{Q}$-matrix is denoted by $\mathbf{C}_2=Com(1,1)$. It is well-known that the nth power of the Q-matrix can be obtained by Fibonacci numbers [4]. In this paper, we introduce a new Fibonacci sequence to be called Golden-Fibonacci sequence. A recursively constructed sequence of numbers is a Golden-Fibonacci sequence if its limit values are connected with the Golden ratio. We introduce an extended class of the Q-matrix and refer to them as the Golden primitive companion matrices (${\text {GPCM}}$). We prove that the sequence associated with a ${\text {GPCM}}$ is a Golden-Fibonacci sequence. We introduce a polynomial-based method to construct some types of ${\text {GPCM}}$. In addition, we provide a relation between the roots of the characteristic polynomial of a companion matrix $\mathbf{C}_p$ and the limit values of the assigned sequence to $\mathbf{C}_p$.

The $\mathbf{Q}$-matrix has been used in [5] to give a coding and decoding technique referred to as Fibonacci coding theory. Moreover, in [8, 9] the authors have used $\mathbf{C}_p=Com(1,1,\ldots ,1)$ as the encoder matrix in the Fibonacci coding system with two different sequence of numbers. Based on the $\mathbf{Q}$-matrix and the Fibonacci coding method a quantum cryptography, quantum key distribution protocol and quantum blind digital signature scheme with error detection are presented in [10,11,12], respectively. In this paper we apply a companion matrix as an encoder matrix and introduce a coding method, to be called companion coding, for encoding integer numbers. The companion coding is a type of error-correcting method in which the encoder matrix needs to be a primitive matrix. The introduced companion coding method is based on the fact that to any primitive companion matrix we can assign a recursive sequence of numbers whose limit values can be used to obtain some error-correcting relations which are useful in decoding a received message.

The rest of the paper is organized as follows. Companion matrices and their associated companion sequences are studied in Sect. 2. A new closed-form expression is given in Sect. 2 for the nth powers of $\mathbf{C}_p$ and $\mathbf{C}_p^{-1}$ by the aid of the associated companion sequences. Some limit values related to a given companion sequence are presented in Sect. 2. In Sect. 3 we classify companion matrices that are primitive. Construction of ${\text {GPCM}}$’s and Golden-Fibonacci sequences is considered in Sect. 4. In Sect. 5 the companion coding method based on companion matrices is introduced and some relations among the entries of an encoded matrix $\mathbf{E}$ are provided which are independent of massage matrices. A summary is given in Sect. 6.

2 A companion sequence for $\mathbf{C}_p$ and a closed-form expression for $\mathbf{C}_p^{n}$ and $\mathbf{C}_p^{-n}$

In this section, we assign a recursive sequence of numbers, called the companion sequence, to a given companion matrix $\mathbf{C}_p$ and use it to obtain a closed-form expression for $\mathbf{C}_p^n$. We also obtain a closed-form expression for $\mathbf{C}_p^{-n}$ which is applied in the decoding process. Moreover, we introduce a systematic method to obtain the limit values of a companion sequence.

2.1 The companion sequence and the structure of $\mathbf{C}_p^n$

In this part, we assign a sequence, called companion sequence, to a given matrix $\mathbf{C}_p$. The sequence is a generalization of the Fibonacci sequence. We represent $\mathbf{C}_p^n$ by the associated companion sequence. The matrix $\mathbf{C}_p^n$ is used as an encoder matrix in the companion coding method described in Sect. 5.

Definition 1

(The companion sequences) The nth term of the companion sequence of order p assigned to $\mathbf{C}_p$ is defined by

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c} k^{(p)}_n=u_1\, k^{(p)}_{n-p}+u_2\, k^{(p)}_{n-2p}+\cdots +u_p\,k^{(p)}_{n-p^2},&n\ge p^2, \end{array} \end{aligned}$$

(2)

wherein $u_i$, $1\le i \le p$, are any integer numbers satisfying $u_i\ge 0$ for $1\le i \le p-1$, and $u_p> 0$, and the $p^2$ initial terms of the sequence are defined by $k^{(p)}_{p(i-1)+j-1}=c_p(i,j)$ for $1\le i,j \le p$.

Example 1

The companion sequence of order $p=2$ with $u_1=u_2=1$, has the general term $k^{(2)}_n= k^{(2)}_{n-2}+ k^{(2)}_{n-4}$ with initial values defined by $\mathbf{C}_2=Com(1,1)$. The sequence $k^{(2)}_n$ generates the classical Fibonacci numbers.

Lemma 1

The determinant of a matrix $\mathbf{C}_p$ is $det(\mathbf{C}_p)=u_p\, {(-1)}^{p+1}$.

Proof

Consider the matrix $\mathbf{C}_p$ given by (1). Using the cofactor expansion along the first column of $\mathbf{C}_p$, we get $det(\mathbf{C}_p)=u_p\, {(-1)}^{p+1}\,det(\mathbf{I}_{p-1})=u_p\, {(-1)}^{p+1}$, where $\mathbf{I}_{p-1}$ is the identity matrix of order $p-1$. $\square$

Now we apply Definition 1 to get a closed-form expression for $\mathbf{C}_p^n$, and by $A^T$ we mean the transpose of A.

Theorem 1

The (i, j)th entry of the nth power of matrix $\mathbf{C}_p$, denoted $c^n_p(i,j)$, is:

$$\begin{aligned} \begin{array}{c@{\quad }c} c^n_p(i,j)=k^{(p)}_{p(n+i-2)+j-1},&1\le i,j \le p, \end{array} \end{aligned}$$

(3)

and hence the entries of $\mathbf{C}_p^n$ are a set of elements of the companion sequence defined by (2).

Proof

The proof is by induction on n. For $n=1$, by Definition 1, we have $\mathbf{C}_p^1=\mathbf{C}_p$. Assume that (3) holds for a positive integer $n\ge 1$. We determine the first column of $\mathbf{C}_p^{n+1}$; the other columns are determined by the same process. From $\mathbf{C}_p^{n+1}=\mathbf{C}_p\, \mathbf{C}_p^n$ and the first column of the matrix $\mathbf{C}_p^n$ that is given by (3), we see that we need to show that the following relation holds.

$$\begin{aligned}&( k^{(p)}_{pn} \quad k^{(p)}_{{p(n+1)}} \, \ldots \, k^{(p)}_{p(n+p-1)})^T \nonumber \\&\quad =Com(u_p,u_{p-1},\ldots ,u_1)~ ( k^{(p)}_{p(n-1)} \quad k^{(p)}_{pn} \, \ldots \, k^{(p)}_{p(n+p-2)})^T \end{aligned}$$

(4)

It can be checked that the ith entry, $1\le i\le p-1$, of the first column of $\mathbf{C}_p^{n+1}$, the left side of (4), is equal with the inner product of the ith row of $\mathbf{C}_p$ and the first column of $\mathbf{C}_p^n$. The inner product of the pth row of $\mathbf{C}_p$ and the first column of $\mathbf{C}_p^n$ is $u_1\, k^{(p)}_{p(n+p-2)} +u_2\, k^{(p)}_{p(n+p-3)} +\cdots +u_{p-1}\, k^{(p)}_{pn} +u_p\, k^{(p)}_{p(n-1)}\,$ which is equal with $k^{(p)}_{p(n+p-1)}$ according to relation (2). $\square$

2.2 The $C^{-1}_p$-sequence and the inverse matrix $\mathbf{C}^{-n}_p$

In this subsection, we introduce a sequence, called $C^{-1}_p$-sequence, and use it for a representation of the inverse matrix $\mathbf{C}^{-n}_p$. It can be verified that if $\mathbf{v}=( -\frac{u_{p-1}}{u_p} \, -\frac{u_{p-2}}{u_p} \, \ldots \, -\frac{u_1}{u_p} )$ and $\mathbf 0$ stands for the all-zero column vector of length $p-1$ then $\mathbf{C}^{-1}_p= \left( \displaystyle \begin{array}{c@{\quad }c} \mathbf{v} &{} 1/{u_p} \\ \mathbf{I}_{p-1} &{} \mathbf{0} \end{array} \right)$. Now, we define a sequence of numbers that will be used in calculating $\mathbf{C}^{-n}_p$.

Definition 2

(The$C^{-1}_p$-sequence) Consider a matrix $\mathbf{C}_p^{-1}$. The companion sequence asigned to $C^{-1}_p$, called $C^{-1}_p$-sequence and denoted $l^{(p)}_n$, is defined by

$$\begin{aligned} l^{(p)}_n:=\frac{1}{u_p}\, l^{(p)}_{n-p^2}-\frac{u_1}{u_p} \,l^{(p)}_{n-p(p-1)}-\cdots -\frac{u_{p-2}}{u_p}\, l^{(p)}_{n-2p}-\frac{u_{p-1}}{u_p}\, l^{(p)}_{n-p}, \end{aligned}$$

(5)

where the $p^2$ initial terms of the sequence are defined by $l^{(p)}_{p(p-i+1)-j}=c^{-1}_p(i,j)$ for $1\le i,j \le p$.

The inverse matrix $\mathbf{C}^{-n}_p$ is used in the decoding process. The next theorem gives the structure of this matrix. The proof of Theorem 2 is by induction on n and is precisely the same as the method used in the proof of Theorem 1, and hence we omit the details.

Theorem 2

The $(i,j)\hbox {th}$ entry of the $n\hbox {th}$ power of matrix $C^{-1}_p$, is $c^{-n}_p(i,j)=l^{(p)}_{p(n+p-i)-j}$ for $1\le i,j \le p$. Hence, the entries of $C^{-n}_p$ are elements of the $C^{-1}_p$-sequence given by (5).

2.3 Some limit values related to a companion sequence

In the decoding process of the companion coding method, we encounter with some limit values $\alpha _i$ which are related to the associated companion sequence. We define $\alpha _i$ by

$$\begin{aligned} \alpha _1:=\displaystyle {\lim _{n\rightarrow \infty }}\quad \frac{k^{(p)}_{pn}}{k^{(p)}_{pn+1}},~ \alpha _2:=\displaystyle {\lim _{n\rightarrow \infty }} \quad \frac{k^{(p)}_{pn+1}}{k^{(p)}_{pn+2}},~\ldots ,~ \alpha _p:=\displaystyle {\lim _{n\rightarrow \infty }} \quad \frac{k^{(p)}_{pn+p-1}}{k^{(p)}_{pn+p}}. \end{aligned}$$

(6)

In the rest, we give a systematic method for calculating $\alpha _i$, $1\le i \le p$. First note that if $u_1,u_2,\ldots ,u_p$ are some integer numbers with $u_i\ge 0$, $1\le i \le p-1$, and $u_p>0$, then it can be checked that the following polynomial f(z) has a unique positive real root $z \in (0,u_p^{\frac{p-1}{p}}]$.

$$\begin{aligned} f(z)=z^p+u_{p-1}\, z^{p-1}+ u_{p-2}\, u_p\, z^{p-2}+\cdots + u_{2}\, u_p^{p-3}\, z^2+u_{1}\, u_p^{p-2}\, z -u_p^{p-1}.\nonumber \\ \end{aligned}$$

(7)

Theorem 3

Consider a companion sequence $k^{(p)}_n$ given by (2). The limit values defined by (6) are as follows: $\alpha _p=\frac{1}{u_p}$ and the values of $\alpha _i$, for $1\le i \le p-1$, are:

$$\begin{aligned} \alpha _i = u_p \displaystyle {\left( \frac{z^{i-1}+u_{p-1}\, z^{i-2}+ u_{p-2}\, u_p\, z^{i-3}+\cdots + u_{p-i+2}\, u_p^{i-3}\, z+u_{p-i+1}\, u_p^{i-2}}{z^{i}+u_{p-1}\, z^{i-1}+ u_{p-2}\, u_p\, z^{i-2}+\cdots + u_{p-i+1}\, u_p^{i-2}\, z+u_{p-i}\, u_p^{i-1}}\right) }, \end{aligned}$$

(8)

where z is the unique positive real root of the polynomial f(z) defined by (7).

Proof

From equation $\mathbf{C}_p^n=\mathbf{C}_p^{n-1}\, \mathbf{C}_p$, we can conclude that another representation for the companion sequence $k^{(p)}_n$ given by (2) can be given by

$$\begin{aligned} k^{(p)}_n=\left\{ \begin{array}{l@{\quad }l} u_p\, k^{(p)}_{n-1} &{} \text{ if }~n=0~(\text{ mod } \,\,p)\\ \\ k^{(p)}_{n-p-1} +u_{p-i}\, k^{(p)}_{n-(i+1)} &{}\text{ if }~n=i~(\text{ mod }~p)~\text{ for }~1\le i \le p-1, \end{array} \right. \end{aligned}$$

(9)

where $k^{(p)}_0=0$, $k^{(p)}_1=1$ and $k^{(p)}_j=0$ for $2 \le j \le p$. By using (9), we can verify that the $\alpha _i$’s defined by (6), satisfy the following system of non-linear equations:

$$\begin{aligned} \alpha _1 \alpha _2 \ldots \alpha _i^2 \ldots \alpha _{p-1}+u_{p-i}\,\alpha _1 \alpha _2 \ldots \alpha _i = u_p, \quad 1\le i \le p-1. \end{aligned}$$

Now to complete the proof we just need to set $z=\alpha _1 \alpha _2 \cdots \alpha _{p-1}$ and apply the proof process used in the Appendix part in [9]. $\square$

Example 2

Consider the companion sequence $k^{(4)}_n= 5\, k^{(4)}_{n-4}+4\, k^{(4)}_{n-8}+ 3\, k^{(4)}_{n-12} +2\, k^{(4)}_{n-16}$. From relations given by (6) the related limit values are $\alpha _i=\lim _{n\rightarrow \infty } \frac{k^{(4)}_{4n+i-1}}{k^{(4)}_{4n+i}},$$1\le i \le 4$. By Theorem 3 we get

$$\begin{aligned} \left\{ \begin{array}{lll} \alpha _1=\displaystyle {u_4\,\left( \frac{1}{z+u_3}\right) }= \displaystyle {2\,\left( \frac{1}{z+3}\right) } =0.5978375830,\\ \alpha _2=\displaystyle {u_4 \, \left( \frac{z+u_3}{z^2+u_3\, z+u_2\, u_4}\right) }= 2\,\displaystyle {\left( {\frac{z+3}{{z}^{2}+3\,z+8}}\right) }= 0.7307963491,\\ \alpha _3= \displaystyle {u_4 \, \left( \frac{z^2+u_3\, z+u_2\, u_4}{z^3+u_3 \, z^2+u_2 \, u_4 \, z+u_1 \, u_4^2 }\right) }= 2\,\displaystyle {\left( {\frac{{z}^{2}+3\,z+8}{{z}^{3}+3\,{z}^{2}+8\,z+20}}\right) }= 0.7905520086,\end{array}\right. \end{aligned}$$

and $\alpha _4=\frac{1}{2}$. In the above relations, $z=0.3453902144$ is the unique positive real root of

$$\begin{aligned} f(z)=z^4+u_3 \, z^3+u_2 \, u_4 \, z^2+u_1 \, u_4^2 \, z -u_4^3 ={z}^{4}+3\,{z}^{3}+8\,{z}^{2}+20\,z-8. \end{aligned}$$

Consider a companion sequence $k^{(p)}_n$ whose initial values are defined by a companion matrix $\mathbf{C}_p$. In Definition 1 we assumed that the coefficients $u_i$, $1\le i \le p$, in $k^{(p)}_n$ are non-negative integer numbers which implies that some $u_i$’s can be zero. In the next section, we show $\mathbf{C}_p$ is a primitive companion matrix if and only if the non-zero coefficients of $k^{(p)}_n$ satisfy a special condition.

3 A connection between primitive and companion matrices

For a companion sequence $k^{(p)}_n=\sum _{i=1}^p\, u_i\, k^{(p)}_{n-ip}$ given by (2) we can define its limit values defined by (6) when there exists a positive integer r such that $k^{(p)}_n>0$ for $n\ge r$. Consider the companion matrix $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots ,u_1)$ which is related to $k^{(p)}_n$. By Theorem 1 the entries of $\mathbf{C}_p^m$ are a set of elements of the sequence $k^{(p)}_n$, for some $m>1$. Therefore, if there exists a positive integer m such that $\mathbf{C}_p^m>0$, then we conclude that its associated companion sequence satisfies $k^{(p)}_n>0$ for $n\ge {p(m+p-1)}$. For instance, in this section we prove that there is no positive integer m such that $\mathbf{C}_{2p}^m>0$ if $\mathbf{C}_{2p}=Com(u_{2p},0,u_{2p-2},0, \ldots ,u_2,0)$.

We said that a matrix $\mathbf{A}$ with non-negatives entries is called a primitive matrix if $\mathbf{A}^m>0$ for some $m\ge 1$. Now we want to see with what values of $u_i$’s a companion matrix $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots ,u_1)$ is a primitive matrix. To answer this, we need to introduce some basic concepts of graph theory. Given a non-negative $n\times n$ matrix $\mathbf{A}=(a_{i,j})$, we assign a weighted directed graph $\mathbf{G}$ to $\mathbf{A}$ with vertices $\{v_1,v_2,\ldots ,v_n\}$ such that if $a_{i,j}\ne 0$ then a directed edge connects vertex $v_i$ to $v_j$ with weight $a_{i,j}$ [13]. In graph theory, the matrix $\mathbf{A}$ is called the adjacency matrix of $\mathbf{G}$.

In the rest of this paper, by a graph $\mathbf{G}$, we mean a weighted directed graph $\mathbf{G}$. A cycle in a graph $\mathbf{G}$ is a directed path having the same initial and terminal vertex with no repeated vertex on it. The number of edges in a cycle is called the length of the cycle. A graph $\mathbf{G}$ is called strongly connected if and only if for every two vertices $v_i$ and $v_j$ there is a directed path from $v_i$ to $v_j$. A relation between a non-negative matrix $\mathbf{A}$ and its associated graph $\mathbf{G}$ is provided in the following theorem.

Theorem 4

([3]) A matrix $\mathbf{A}$ is primitive if and only if its associated graph $\mathbf{G}$ is strongly connected and has two cycles of relatively prime lengths.

We derive a corollary from Theorem 4 which is used in determination of companion matrices that are primitive. In Corollary 1, by $\gcd$ we mean greatest common divisor.

Corollary 1

Consider a companion matrix $\mathbf{C}_p=Com(u_p,\ldots ,u_1)$ for $u_i\ge 0$, $1\le i \le p-1$, and $u_p> 0$. Assume that among $u_i$’s, $1\le i \le p-1$, just the entries $u_{j_1},u_{j_2},\ldots , u_{j_t}$ are non-zero, and hence the other $u_i$’s are zero. Then $\mathbf{C}_p$ is a primitive matrix if and only if $\gcd (p,{j_1},{j_2},\ldots , {j_{t}})=1$.

Proof

The graph $\mathbf{G}$ associated with $\mathbf{C}_p$ is given below wherein we have edges with weights $u_i$ for $1\le i \le p$.

The graph $\mathbf{G}$ is strongly connected since we have $u_p>0$. Further, based on the assumption, among $u_i$’s, $1\le i \le p-1$, just the entries $u_{j_1},u_{j_2}, \ldots , u_{j_t}$, $t\le p-1$, are non-zero which results in that the graph $\mathbf{G}$ has only cycles of length $p, {j_1},\ldots , {j_{t-1}}$, and ${j_t}$.

If $\mathbf{C}_p$ is a primitive matrix it follows from Theorem 4 that the graph $\mathbf{G}$ has two cycles of relatively prime lengths implying that $\gcd (p,{j_1},{j_2},\ldots , {j_{t}})=1$. It is obvious that if $\gcd (p,{j_1},{j_2},\ldots , {j_{t}})=1$ then the graph $\mathbf{G}$ has at least two cycles of relatively prime lengths. Now it follows from Theorem 4 that $\mathbf{C}_p$ is a primitive matrix. $\square$

Example 3

Based on Corollary 1, if in a companion matrix $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots , u_1)$ there exists a non-zero entry $u_i$, $1\le i \le p-1$ such that $\gcd (p,i)=1$, then $\mathbf{C}_p$ is a primitive matrix. For instance, $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots , u_1)$ with $u_{p-1}\ne 0$ or $u_1\ne 0$, is a primitive matrix. Moreover, the companion matrix $\mathbf{C}_{2p}=Com(u_{2p},0,\ldots ,u_2,0)$ is not a primitive matrix since $\gcd (2p,2p-2,\ldots ,2)=2$.

In the next section, we introduce some types of primitive companion matrices which are connected with golden ratio.

4 Golden sequences and matrices

In this section, we introduce some recursive sequences and primitive companion matrices such that they are connected with the Golden ratio. In fact a new extension of the sequence of Fibonacci numbers and the Q-matrix are given in this section. We obtain a relation between the roots of the characteristic polynomial of a companion matrix $\mathbf{C}_p$ and the limit values of its associated companion sequence.

4.1 A generalization of the Q-matrix and the Fibonacci numbers

In this subsection, we introduce three special types of primitive companion matrices such that the limit values of their assigned companion sequences are connected with the Golden ratio.

Definition 3

A recursive sequence of numbers is called a Golden-Fibonacci sequence if its limit values is equal to $\uptau ^k$ for some integer number k where $\uptau =\frac{1+\sqrt{5}}{2}$.

In this paper, all limit values of the considered Golden-Fibonacci sequences are in the form of 1, $\uptau , \frac{1}{\displaystyle {\uptau }}, \uptau ^2$ and $\frac{1}{\displaystyle {\uptau ^2}}$. For instance, the companion sequence $k^{(2)}_n$ given in Example 1, is a Golden-Fibonacci sequence, since it can be checked that its limit values are 1 and $\frac{1}{\displaystyle {\uptau }}$.

Definition 4

The $2p\times 2p$ matrix $Com(1,1,0,1,0,1,\ldots ,0,1)$ is denoted by $\mathbf{EC} _{2p}$ and is referred to as the ${\text {GPCM}}$ of even size 2p.

Example 4

For $p=1$, the matrix $\mathbf{EC}_2$ is the $\mathbf{Q}$-matrix. Consider $\mathbf{EC}_6=Com(1,1,0,1,0,1)$ with $u_1=u_3=u_5=u_6=1$ and $u_2=u_4=0$. Therefore, the companion sequence assigned to $\mathbf{EC}_6$ is $k^{(6)}_n= k^{(6)}_{n-6}+ k^{(6)}_{n-18}+ k^{(6)}_{n-30} +k^{(6)}_{n-36}$, whose initial values are defined by $\mathbf{EC}_6$. Based on (8), the limit values of $\mathbf{EC}_6$ are

$$\begin{aligned}&\alpha _1=\frac{1}{z+1},\quad \alpha _2=\frac{z+1}{z^2+z}=\frac{1}{z},\quad \alpha _3=\frac{z^2+z}{z^3+z^2+1}, \quad \alpha _4=\frac{z^3+z^2+1}{z^4+z^3+z}=\frac{1}{z},\\&\quad \alpha _5=\frac{z^4+z^3+z}{z^5+z^4+z^2+1}, \alpha _6=\frac{1}{u_6}, \end{aligned}$$

where, based on (7), z is the positive real solution of $f(z)=z^6+z^5+z^3+z-1$. The polynomial f(z) has factorization $f(z)=(z^4+z^2+1)(z^2+z-1)$. Therefore, the only positive real root of f(z) is $z=\frac{1}{\displaystyle {\uptau }}$. It follows from $z^2+z-1=0$ that $z+1=\frac{1}{z}$ which results in $\begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} \alpha _1=\frac{1}{\displaystyle {\uptau }},&\alpha _2=\uptau ,&\alpha _3=\frac{1}{\displaystyle {\uptau }},&\alpha _4=\uptau ,&\alpha _5=\frac{1}{\displaystyle {\uptau }}, \end{array}$ and $\alpha _6=1$.

Now, by $\mathbf{EC} _{2p}$, we introduce a new extension of the sequence of Fibonacci numbers of even size.

Lemma 2

The companion sequence associated with $\mathbf{EC}_{2p}$ is a Golden-Fibonacci sequence.

Proof

From (2), the companion sequence asigned to $\mathbf{EC}_{2p}$ is:

$$\begin{aligned} k^{(2p)}_n= k^{(2p)}_{n-2p}+ k^{(2p)}_{n-3(2p)}+ k^{(2p)}_{n-5(2p)}+\cdots + k^{(2p)}_{n-(2p-3)(2p)}+ k^{(2p)}_{n-((2p-1)(2p))} +k^{(2p)}_{n-(2p)^2}. \end{aligned}$$

(10)

Now, we prove that the limit values of the companion sequence $k^{(2p)}_n$ given in (10) are:

$$\begin{aligned} \alpha _i=\begin{array}{c@{\quad }c@{\quad }c@{\quad }c} \displaystyle {\lim _{n\rightarrow \infty }}\, \frac{k^{(2p)}_{2pn+i-1}}{k^{(2p)}_{2pn+i}} =\begin{array}{c@{\quad }c@{\quad }c} \left\{ \begin{array}{l@{\quad }l} \uptau &{}i=0~(\text{ mod } \,\,2),\\ \\ \frac{1}{\displaystyle {\uptau }} &{}i=1~(\text{ mod }~2), \end{array} \right. \end{array}&\,&1\le i \le 2p-1,&\alpha _{2p}=1. \end{array} \end{aligned}$$

From Definition 4 we have $(u_{2p},u_{2p-1},u_{2p-2},u_{2p-3},\ldots , u_2, u_1)=(1,1,0,1,\ldots , 0, 1)$. Hence by (8) the limit values of $k^{(2p)}_n$ are:

$$\begin{aligned} \alpha _i = \displaystyle {\frac{z^{i-1}+ z^{i-2}+ z^{i-4}+\cdots + u_{2p-i+2}\, z+u_{2p-i+1}}{z^{i}+z^{i-1}+ z^{i-3}+\cdots + u_{2p-i+1}\, z+u_{2p-i}}} \, , 1\le i \le 2p-1, \end{aligned}$$

wherein, based on (7), z is the positive real solution of the following polynomial f(z):

$$\begin{aligned}&f(z)=z^{2p}+ z^{2p-1}+ z^{2p-3}+z^{2p-5}+\cdots +z^3+ z -1\\&\quad = (z^{2p-2}+z^{2p-4}+\cdots +z^2+1)(z^2+z-1). \end{aligned}$$

The equation $\sum _{i=0}^{p-1}\,z^{2i}=0$ has no positive real solution. Therefore, the unique positive real root of f(z) is $z=\frac{1}{\displaystyle {\uptau }}$. If $i=2l$, for some positive integer l, then $\alpha _{2l}=\frac{1}{z}=\uptau$. For $i=2l-1$ we get

$$\begin{aligned} \alpha _{2l-1}= \displaystyle {\frac{z^{2l-2}+ z^{2l-3}+ z^{2l-5}+\cdots + z^3+z}{z^{2l-1}+ z^{2l-2}+ z^{2l-4}+\cdots + z^2+1}}. \end{aligned}$$

We have $z^2+z-1=0$, which implies that $z+1=\frac{1}{z}$. First we prove that $z^{2l-2}+ z^{2l-3}+ z^{2l-5}+\cdots + z^3+z=1$; to do this, first note that: $z^{2l-2}+ z^{2l-3}+ z^{2l-5}=z^{2l-3}(z+1)+ z^{2l-5}=z^{2l-6}.$ By iteratively applying this method, we get $z^{2l-2}+ z^{2l-3}+ z^{2l-5}+\cdots + z^3+z=1.$ By the same method, we can show that $z^{2l-1}+ z^{2l-2}+ z^{2l-4}+\cdots + z^2+1=\frac{1}{z}$, which results in that $\alpha _{2l-1}=\frac{1}{\displaystyle {\uptau }}$. Also, from Theorem 3 we get $\alpha _{2p}=\frac{1}{u_{2p}}=1$. $\square$

Next we define a set of odd-size Golden primitive companion matrices.

Definition 5

The ${\text {GPCM}}$ of odd size $2p+1$ is defined by $\mathbf{OC} _{2p+1}:=Com(1,1,0,1,0,\ldots ,1,0,2,0)$.

Example 5

For $p=1$, we get $\mathbf{OC} _3=Com(1,2,0)$. We have $\mathbf{OC}_5=Com(1,1,0,2,0)$ which results in $u_1=0$, $u_2=2$, $u_3=0$ and $u_4=u_5=1$. Hence the companion sequence assigned to $\mathbf{OC} _5$ is $k^{(5)}_n= 2\, k^{(5)}_{n-10}+ k^{(5)}_{n-20} +k^{(5)}_{n-25}$. Similar to Example 4, we can get $\begin{array}{c@{\quad }c@{\quad }c@{\quad }c} \alpha _1=\frac{1}{\displaystyle {\uptau }},&\alpha _2=\uptau ,&\alpha _3=\frac{1}{\displaystyle {\uptau ^2}},&\alpha _4=\uptau , \end{array}$ and $\alpha _5=1$.

By using $\mathbf{OC} _{2p+1}$, we propose an extension of the classical Fibonacci sequence of odd size.

Lemma 3

The companion sequence assigned to $\mathbf{OC} _{2p+1}$ is a Golden-Fibonacci sequence.

Proof

From (2) the companion sequence connected with $\mathbf{OC} _{2p+1}$ is:

$$\begin{aligned} k^{(2p+1)}_n= 2\, k^{(2p+1)}_{n-2(2p+1)}+ k^{(2p+1)}_{n-4(2p+1)}+\cdots + k^{(2p+1)}_{n-(2p-2)(2p+1)}+ k^{(2p+1)}_{n-((2p)(2p+1))} +k^{(2p+1)}_{n-(2p+1)^2}.\nonumber \\ \end{aligned}$$

(11)

Similar to the proof of Lemma 2, one can show that the limit values of $k^{(2p+1)}_n$ given in (11) are:

$$\begin{aligned} \begin{array}{c@{\quad }c} \alpha _i= \left\{ \begin{array}{l@{\quad }l} \uptau &{}i=0~(\text{ mod } \,\,2),\\ \frac{1}{\displaystyle {\uptau }} &{}i=1~(\text{ mod }~2), \end{array} \right. ,&1\le i \le 2p-2, \end{array} \end{aligned}$$

and also $\alpha _{2p-1}=\frac{1}{\displaystyle {\uptau ^2}}$, $\alpha _{2p}=\uptau$ and $\alpha _{2p+1}=1$. $\square$

Next we introduce a set of Golden primitive companion matrices of general size.

Definition 6

The ${\text {GPCM}}$ of arbitrary size p, $p\ge 4$, is defined by $\mathbf{GC} _{p}:=Com(1,2,1,\ldots ,1,0)$.

Example 6

For $p=4$, we have $\mathbf{GC}_4=Com(1,2,1,0)$ with $u_1=0$, $u_2=1$, $u_3=2$ and $u_4=1$. Therefore, the companion sequence assigned to $\mathbf{GC}_4$ is $k^{(4)}_n= k^{(4)}_{n-8}+ 2\, k^{(4)}_{n-12} +k^{(4)}_{n-16}$, with initial values defined by $\mathbf{GC} _4$. From (8) the limit values of $\mathbf{GC} _4$ are $\begin{array}{c@{\quad }c@{\quad }c} \alpha _1=\frac{1}{z+2},&\alpha _2=\frac{z+2}{z^2+2z+1},&\alpha _3=\frac{z^2+2z+1}{z^3+2z^2+z}=\frac{1}{z}, \end{array}$ where z is the positive real solution of $f(z)=z^4+2\,z^3+z^2-1$. The polynomial f(z) is factored as $f(z)=(z^2+z+1)(z^2+z-1)$, which implies that the positive real root of f(z) is $z=\frac{1}{\displaystyle {\uptau }}$. From $z^2+z-1=0$, we get $\alpha _1=\frac{1}{\displaystyle {\uptau ^2}}$, $\alpha _2=1$, $\alpha _3=\uptau$, and $\alpha _4=1$.

Lemma 4

The companion sequence associated with $\mathbf{GC} _{p}$ is a Golden-Fibonacci sequence.

Proof

From (2) the companion sequence related to $\mathbf{GC}_p$ is:

$$\begin{aligned} \begin{array}{c} k^{(p)}_n= k^{(p)}_{n-2p}+ k^{(p)}_{n-3p}+\cdots +k^{(p)}_{n-(p-2)p}+2\, k^{(p)}_{n-(p-1)p}+k^{(p)}_{n-p^2}. \end{array} \end{aligned}$$

(12)

Similar to the proof of Lemma 2, one can show that the limit values of $k^{(p)}_n$ given in (12) are:

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} \alpha _1=\frac{1}{\displaystyle {\uptau ^2}},&\alpha _{i}=1~ \text{ for }~ 2\le i \le p-2,&\alpha _{p-1}=\uptau ,&\alpha _p=1. \end{array} \end{aligned}$$

$\square$

In the next subsection, we introduce a method to construct a ${\text {GPCM}}$ by making use of a special polynomials having integer coefficients.

4.2 Construction of ${\text {GPCM}}$ via polynomials

Assume we want to obtain an arbitrary ${\text {GPCM}}$, denoted $\widetilde{\mathbf{C}}_p$, such that its assigned companion sequence is a Golden-Fibonacci sequence. To construct $\widetilde{\mathbf{C}}_p$, we need a polynomial g(z) of degree $p-2$ which has no positive real root and satisfies the following condition:

$$\begin{aligned} f(z)=g(z)\,(z^2+z-1)=z^p+u_{p-1}\,z^{p-1}+u_{p-2}\,z^{p-2}+\cdots + u_1\,z-1, \end{aligned}$$

(13)

where $u_i\in \{0,1,2\}$ for $1\le i \le p-1$.

Now consider $\widetilde{\mathbf{C}}_p=Com(1,u_{p-1},u_{p-2},\ldots , u_1)$. From (2), the companion sequence associated with $\widetilde{\mathbf{C}}_p$ is

$$\begin{aligned} \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} k^{(p)}_n=u_1\, k^{(p)}_{n-p}+u_2\, k^{(p)}_{n-2p}+\cdots +u_{p-1}\,k^{(p)}_{n-(p-1)p}+k^{(p)}_{n-p^2} ,&n\ge p^2, \end{array} \end{aligned}$$

(14)

where its $p^2$ initial terms are defined by $\widetilde{\mathbf{C}}_p$. It follows from (8) that the limit values of $k^{(p)}_n$ given in (14) for $1\le i \le p-1$ are:

$$\begin{aligned} \alpha _i =\displaystyle {\frac{z^{i-1}+u_{p-1}\, z^{i-2}+ u_{p-2}\, z^{i-3}+\cdots + u_{p-i+2}\, z+u_{p-i+1}}{z^{i}+u_{p-1}\, z^{i-1}+ u_{p-2}\, z^{i-2}+\cdots + u_{p-i+1}\, z+u_{p-i}}}, \end{aligned}$$

(15)

where, based on (7), z in (15) is the positive real root of f(z), which is equal to $z=\frac{1}{\displaystyle {\uptau }}$. Now the primitive companion matrix $\widetilde{\mathbf{C}}_p$ is a ${\text {GPCM}}$ if the companion sequence $k^{(p)}$ given in (14) is a Golden-Fibonacci sequence or equivalently the values of $\alpha _i$’s in (15) are powers of the Golden ratio.

One of the main reasons for the condition $u_i\in \{0,1,2\}$, given in (13), is that the inverse of the Golden ratio $z=\frac{1}{\displaystyle {\uptau }}$ satisfies equations $z+1 =\frac{1}{\displaystyle {z}}$ and $z+2=\frac{1}{\displaystyle {z^2}}$, which implies that the values of $\alpha _i$’s in (15) can be in the form of power of Golden ratio $\uptau$ (such as $\alpha _i$’s obtained in Lemmas 2, 3 and 4).

Example 7

Consider polynomial $g_1(z)=z^{2p-2}+z^{2p-3}+z^{2p-5}+\cdots +z^3+z+1$. The polynomial $g_1(z)$ has no positive real root and also satisfies relation (13), since we have

$$\begin{aligned} g_1(z)\,(z^2+z-1)=z^{2p}+2\,z^{2p-1}+z^{2p-4}+z^{2p-6}+\cdots +z^6+z^4+2\,z^2-1. \end{aligned}$$

Now if we set $\widetilde{\mathbf{C}}_{2p}=Com(1,2,0,0,1,0,\ldots ,1,0,2,0)$, then it can be verified that the companion sequence assigned to $\widetilde{\mathbf{C}}_{2p}$ is a Golden-Fibonacci sequence. Moreover, it can be checked that (13) is satisfied by polynomial $g_2(z)=z^{2p-1}+z^{2p-2}+z^{2p-4}+\cdots +z^4+z^2+1$.

In (13), instead of polynomial $z^2+z-1$, we may use a polynomial $r(z)=z^2+nz-1$ for some positive integer n. The polynomial r(z) has a positive real root $\widetilde{z}=\frac{1}{\frac{n+\sqrt{n^2+4}}{2}}=\dfrac{1}{\displaystyle {\widetilde{\uptau }}}$ in the interval (0, 1) and a negative root. By using r(z) in (13), we get results similar to those obtained for the case of polynomial $z^2+z-1$ in Lemmas 2, 3 and 4.

Lemma 5

Assume $\widetilde{f}(z)=(\sum _{i=0}^{p-1}z^{2i})(z^2+nz-1)=z^{2p}+nz^{2p-1}+nz^{2p-3}+\cdots + nz-1$ and set $\widetilde{\mathbf{EC}}_{2p}=Com(1,n,0,n,0,n,\ldots ,0,n)$. Then the limit values of companion sequence related to $\widetilde{\mathbf{EC}}_{2p}$ are $\alpha _i= \left\{ \begin{array}{l@{\quad }l} \widetilde{\uptau } &{}i=0~(\text{ mod } \,\,2),\\ \dfrac{1}{\displaystyle {\widetilde{\uptau }} } &{}i=1~(\text{ mod }~2), \end{array} \right.$ if $1\le i \le 2p-1$ and $\alpha _{2p}=1$.

Proof

The proof process is similar to that given in Lemma 2. $\square$

4.3 A relation between the roots of the characteristic polynomial of $\mathbf{C}_p$ and the related limit values

Consider a companion matrix $\mathbf{C}_p=Com(u_p,u_{p-1},\ldots , u_2,u_1)$. The characteristic polynomial [2] of $\mathbf{C}_p$, denoted h(z), is $h(z)=\det (z\mathbf{I}_p-\mathbf{C}_p)=z^p-u_1z^{p-1}-u_2z^{p-2}-\cdots -u_{p-1}z-u_p$. Based on (7) we assigned a polynomial f(z) to $\mathbf{C}_p$ where $f(z)=z^p+u_{p-1}\, z^{p-1}+ u_{p-2}\, u_p\, z^{p-2}+\cdots + u_{2}\, u_p^{p-3}\, z^2+u_{1}\, u_p^{p-2}\, z -u_p^{p-1}.$ Assume that $k^{(p)}_n$ is the companion sequence related to $\mathbf{C}_p$. Based on (8), the limit values of $k^{(p)}_n$ are obtained by the positive real root of f(z). In the next lemma, we get a connection between the roots of h(z) and f(z).

Lemma 6

A number $\mathbf{z}$ is a root of f(z) if and only if $\frac{ u_p}{\mathbf{z}}$ is a root of h(z).

Proof

It is easy to see that that $f(z)=-{\frac{z^p}{u_p}}\, h(\frac{u_p}{z}),$ which completes the proof. $\square$

It follows from Theorem 3 that f(z) has a unique positive real root. Therefore, it follows from Lemma 6 that by the positive real root of the characteristic polynomial of a companion matrix $\mathbf{C}_p$, we can obtain the limit values of the companion sequence assigned to $\mathbf{C}_p$.

Example 8

Consider $\mathbf{C}_3=Com(1,0,1)$, then we get $h(z)=z^3-z^2-1$ and $f(z)=z^3+z-1$. It follows from Lemma 6 that $f(z)=-z^3 h(\frac{1}{z})$. The positive real root of h(z) is 1.465571232 and hence the positive real root of f(z) is $z= 0.6823278040$. The companion sequence assigned to $\mathbf{C}_3$ is $k^{(3)}_n= k^{(3)}_{n-3}+ k^{(3)}_{n-9}$. Based on (8), the limit values of $k^{(3)}_n$ are $\alpha _1=\frac{1}{z}=1.465571232$ and $\alpha _2=({\frac{z}{{z}^{2}+1}})=z^2=0.465571232$.

5 Error-correcting process of Companion coding method

The process of companion coding method is similar to Fibonacci coding system explained in [5, 9]. To make this paper more self-contained, we provide a brief description of encoding and decoding process of this method here by giving an illustrating example. In this paper, we consider Fibonacci coding based on the ground matrix $\mathbf{C}_p$.

The measure of error-correcting capability of the companion coding is based on the limit values of the companion sequence assigned to a given companion matrix $\mathbf{C}_p$. In fact, the companion coding is a coding of integer numbers and we have no binary operations in its encoding and decoding process. In other words, the metric of the companion coding is not related to binary form of massages and just directly associated with some real numbers that are called limit values. First, we explain how to encode a massage matrix.

Encoding process  For encoding in companion coding method, we take a matrix $\mathbf{C}_p$ given by (1) wherein $u_i$’s, $1\le i \le p$, are arbitrary integer numbers with $u_i\ge 0$ for $1\le i \le p-1$, and $u_p> 0$. The companion sequence assigned to (1) is given by (2). Then, we consider a positive integer n and employ $\mathbf{C}_p^n$ given by (3) as the encoder matrix. The message to be encoded is considered as a $p\times p$ matrix $\mathbf{M}$ referred to as the message matrix. The encoded matrix $\mathbf{E}$ is defined by $\mathbf{E}:=\mathbf{M} \, \mathbf{C}_p^n$. Suppose the encoded matrix $\mathbf{E}$ is in the form

$$\begin{aligned} \mathbf{E}=\left( \displaystyle \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} e_1 &{} e_2 &{} \cdots &{} e_{p-1} &{} e_p\\ e_{p+1} &{} e_{p+2} &{} \cdots &{} e_{2p-1} &{} e_{2p} \\ \vdots &{} \vdots &{} \vdots &{} \vdots &{}\vdots \\ e_{p^2-p+1} &{} e_{p^2-p+2} &{} \cdots &{} e_{p^2-1} &{} e_{p^2} \end{array} \right) . \end{aligned}$$

In companion coding system, we assume that the entries of encoded matrix $\mathbf{E}$ together with the determinant of the message matrix, $\det (\mathbf{M})$, are transmitted through a communication channel, and assume that the entries $e_i$, $1\le i \le p^2$, may be received with error but the value of $\det (\mathbf{M})$ is received correctly. In fact, if $\det (\mathbf{M})$ is transmitted several times, using majority logic decoding, then we may assume that $\det (\mathbf{M})$ is received correctly.

Decoding process It follows from $\mathbf{E}=\mathbf{M} \, \mathbf{C}_p^n$ that

$$\begin{aligned} det(\mathbf{E}) =det(\mathbf{M})\times det(\mathbf{C}_p^n)=det(\mathbf{M}) \times u_p^n\, {(-1)}^{n(p+1)}. \end{aligned}$$

(16)

The receiver reconstruct an estimated matrix $\mathbf{E}'$ by using the received entries and then checks for (16). The relation (16) is a means of error-detection. We say that no errors have occured if this relation is satisfied by $\mathbf{E}'$ (note that when using a linear code with parity-check matrix $\mathbf{H}$, a received word $\mathbf{x}$ is considered as a codeword if and only if $\mathbf{H}{} \mathbf{x}=\mathbf{0}$).

If the received matrix dose not satisfy (16), then we say that some entries of the encoded matrix are received with error. We need to get some relations correcting errors in the received matrix. In Theorem 5, we obtain some relations between the elements of the encoded matrix $\mathbf{E}$ and the limit values of the companion sequence assigned to the encoder matrix.

Theorem 5

Consider an encoded matrix $\mathbf{E}=\mathbf{M} \, \mathbf{C}_p^n$, where $\mathbf{M}$ and $\mathbf{C}_p^n$ are the message and encoder matrices, respectively. Then the relations between the entries of $\mathbf{E}$ and the limit values $\alpha _i$’s given by (6), are as follows

$$\begin{aligned} \left\{ \begin{array}{lcc} \displaystyle {e_{i}} \approx \displaystyle {\alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\, e_{j}} ,&{} 1\le i<j\le p, &{}\quad \text{ the } \text{ first } \text{ row } \text{ of } \mathbf{E},\\ \displaystyle {e_{p+i}} \approx \displaystyle { \alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\,e_{p+j}} ,&{} 1\le i<j\le p, &{} \quad \text{ the } \text{ second } \text{ row } \text{ of } \mathbf{E}, \\ \vdots &{}\vdots &{} \vdots \\ \displaystyle {e_{p^2-p+i}} \approx \displaystyle { \alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\, e_{p^2-p+j}} ,&{} 1\le i<j\le p, &{}\quad \text{ the }~p\text{ th } \text{ row } \text{ of } \mathbf{E}. \end{array}\right. \end{aligned}$$

(17)

Proof

Consider the nth power of companion matrix, $\mathbf{C}_p^n$, given by (3). Now, similar to the proof of Theorem 4 in [9], it can be shown that the following relations hold among the entries of the first row of $\mathbf{E}$:

$$\begin{aligned} \begin{array}{c@{\quad }c} \displaystyle {\frac{ k^{(p)}_{p(n-1)+i-1}}{k^{(p)}_{p(n-1)+i}}}~\le \displaystyle {\frac{e_i}{e_{i+1}}}\le \displaystyle {\frac{k^{(p)}_{pn+i-1}}{k^{(p)}_{pn+i}}},&1\le i \le p-1 . \end{array} \end{aligned}$$

(18)

It follows from (6) and (18) that the following relations hold between the elements of the first row of $\mathbf{E}$:

$$\begin{aligned} \left. \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} \displaystyle {\frac{e_1}{e_2}}\approx \alpha _1,&\displaystyle {\frac{e_2}{e_3}}\approx \alpha _2,&\cdots \, ,&\displaystyle {\frac{e_{p-1}}{e_p}}\approx \alpha _{p-1} . \end{array}\right. \end{aligned}$$

Applying the same process on the other rows of $\mathbf{E}$, we get the following relationships between the entries of $\mathbf{E}$ for $1\le i \le p-1$:

$$\begin{aligned} \displaystyle {\frac{e_i}{e_{i+1}}=\frac{e_{p+i}}{e_{p+i+1}}=\cdots =\frac{e_{p^2-p+i}}{e_{p^2-p+i+1}}}\approx \alpha _i. \end{aligned}$$

(19)

Now, consider $v=h\,p$ with $0\le h \le p-1$; it follows from (19) that

$$\begin{aligned} \frac{e_{v+i}}{e_{v+j}}=\frac{e_{v+i}}{e_{v+i+1}}\times \frac{e_{v+i+1}}{e_{v+i+2}}\, \times \cdots \times \, \frac{e_{v+j-1}}{e_{v+j}} \approx \alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\,~\text{ for }~1\le i<j\le p, \end{aligned}$$

which is the system given by (17). $\square$

The set of relations given by (17) is called the checking relation and is used for checking and correcting errors in the received matrix. Consider $\mathbf{{EC}}_{2p}$ introduced in Definition 4. In the next corollary, we prove if the nth power of $\mathbf{{EC}}_{2p}$ is used as an encoder matrix in Theorem 5, then the error-correcting relations are connected with the golden ratio $\uptau =\frac{1+\sqrt{5}}{2}$.

Corollary 2

Assume that $\mathbf{E}=\mathbf{M} \, \mathbf{{({EC}}}_{2p})^n$, then for $1\le i \le 2p-1$, we have

$$\begin{aligned} \begin{array}{l} \displaystyle {\frac{e_i}{e_{i+1}}=\frac{e_{2p+i}}{e_{2p+i+1}} =\cdots =\frac{e_{4p^2-2p+i}}{e_{4p^2-2p+i+1}}}\approx \begin{array}{c@{\quad }c@{\quad }c} \left\{ \begin{array}{l@{\quad }l} \uptau &{}i=0~(\text{ mod } \,\,2),\\ \frac{1}{\uptau } &{}i=1~(\text{ mod }~2). \end{array} \right. \end{array} \end{array} \end{aligned}$$

(20)

Proof

The proof is derived from Lemma 2 and Theorem 5. $\square$

Consider matrices $\mathbf{{OC}}_{2p+1}$ and $\mathbf{{GC}}_{p}$ introduced in Definitions 5 and 6. By applying $\mathbf{{OC}}_{2p+1}^n$ and $\mathbf{{GC}}_{p}^n$ as encoder matrices in Theorem 5, we can obtain relations similar to those given by (20).

Suppose $\mathbf{E}$ is transmitted and $\mathbf{E}'$ is received and assume that $det(\mathbf{M})$ is sent correctly to the receiver. If Eq. (16) holds by $\mathbf{E}'$, we consider $\mathbf{E}'$ as the transmitted encoded matrix $\mathbf{E}$, otherwise we move on to the error-correcting process. The number of errors in $\mathbf{E}'$ varies from one to $p^2$. We begin by assuming that it has just one error and try to find and correct the erroneous element; in case of not being successful, we then consider the existence of error patterns of size two in the received matrix $\mathbf{E}'$, and so on. More details about error-correcting process are available in [5, 9].

Example 9

Consider the following message matrix $\mathbf{M}$ and the matrix $\mathbf{C}_3=Com(1,0,1)$:

$$\begin{aligned} \begin{array}{c@{\quad }c} \mathbf{M}= \left( \begin{array}{c@{\quad }c@{\quad }c} 27&{}99&{}89\\ 53&{}62&{}20\\ 46&{}74&{}54 \end{array} \right) ,&{} \mathbf{C}_3= \left( \begin{array}{c@{\quad }c@{\quad }c} 0&{}1&{}0\\ 0&{}0&{}1\\ 1&{}0&{}1\end{array} \right) . \end{array}~ \end{aligned}$$

Consider $\mathbf{C}_3^{30}$ as an encoder matrix and let $\mathbf{E}$ and $\mathbf{E}'$ be the transmitted and received messages, respectively.

$$\begin{aligned} \mathbf{E}= & {} \mathbf{M}\times \mathbf{C}_3^{30}= \left( \begin{array}{c@{\quad }c@{\quad }c} 6742004&{}4600257&{}9880887\\ 3467442&{}2365932&{}5081783\\ 5019344&{}3424838&{}7356206 \end{array} \right) ,\\ \mathbf{E}'= & {} \left( \begin{array}{c@{\quad }c@{\quad }c} 9548124&{}4600257&{}9880887\\ 3467442&{}6127897&{}5081783\\ 5019344&{}3424838&{}2187946 \end{array} \right) . \end{aligned}$$

We can verify that the relation (16) is not satisfied by $\mathbf{E}'$ meaning that some entries of $\mathbf{E}'$ are received with error ($\mathbf{E}'\ne \mathbf{E}$). According to (17), the checking relation for this example is

$$\begin{aligned} \left\{ \begin{array}{l@{\quad }l} \displaystyle {e_{i}} \approx \displaystyle {\alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\, e_{j}} ,&{} \\ \displaystyle {e_{3+i}} \approx \displaystyle { \alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\,e_{3+j}} ,&{} 1\le i<j \le 3.\\ \displaystyle {e_{6+i}} \approx \displaystyle { \alpha _i \, \alpha _{i+1} \,\ldots \, \alpha _{j-1}\, e_{6+j}}.&{} \end{array}\right. \end{aligned}$$

(21)

From Example 8, the values of $\alpha _i$’s in (21) are $\alpha _1=1.465571232$ and $\alpha _2=0.465571232$. It can be checked that by the decoding algorithm for one and two errors, we cannot obtain a matrix satisfying (16). As for error patterns of size three, assume that the eronious elements are the entries of the main diagonal of $\mathbf{E}'$ (i.e. $e'_1$, $e'_5$ and $e'_9$) and that the other entries of $\mathbf{E}'$ are received correctly. Now from (21) we get $e'_1\approx e'_2 \, \alpha _1 \approx 6742004$, $e'_5 \approx \frac{e'_4}{\alpha _1} \approx 2365932$ and $e'_9 \approx \frac{e'_8}{\alpha _2} \approx 7356206$. Now, it can be checked that the values $e'_1$, $e'_5$ and $e'_9$ together with the other entries of $\mathbf{E}'$ satisfy (16). In addition, no other three-error case may end up with a matrix satisfying (16). Therefore, the matrix $\mathbf{E}'$ contains just three erroneous entries and we have guessed correctly the position of the errors and corrected the erroneous entries.

6 Summary

The class of companion matrices was considered and a companion sequence was assigned to each companion matrix $\mathbf{C}_p$. We introduced a simple method for calculating some limit values of a companion sequence. We provided a closed-form expression for the nth power of $\mathbf{C}_p$ by making use of its associated companion sequence. We gave a condition under which a companion matrix is a primitive matrix. We introduced some special cases of primitive companion matrices such that are related to the Golden ratio. A new extension of the sequence of Fibonacci numbers was introduced and it was shown that the limit values of the introduced sequences are powers of the Golden ratio. Based on the theory of the primitive companion matrices and their associated companion sequences, a class of error-correcting codes was introduced. The availability of a large class of encoder matrices is a result of this approach as far as the theory of error-correcting codes is concerned.