# A New Method of Matrix Decomposition to Get the Determinants and Inverses ofr-Circulant Matrices with Fibonacci and Lucas Numbers

Authors: Jiangming Ma; Tao Qiu; Chengyuan He
Journal: Journal of Mathematics
 (2021)

---

## Abstract

We use a new method of matrix decomposition forr-circulant matrix to get the determinants of An=CircrF1,F2,…,Fn and Bn=CircrL1,L2,…,Ln, where Fn is the Fibonacci numbers and Ln is the Lucas numbers. Based on these determinants and the nonsingular conditions, inverse matrices are derived. The expressions of the determinants and inverse matrices are represented by Fibonacci and Lucas Numbers. In this study, the formulas of determinants and inverse matrices are much simpler and concise for programming and reduce the computational time.


---

## Body

## 1. Introduction

The good properties and structure of the circulant matrix are widely given in the area of coding theory, image processing, signal system, and cybernetics [1–4]. For instance, Carrasquinha et al. [5] propose an innovative method for image reconstruction based on circulant matrices. This method significantly reduces the computational time than the principal component analysis (PCA), the discrete Fourier transform (DFT), and the randomized singular value decomposition (RSVD). By using the circulant matrices, Nguyen and Kim [6] get a new construction method of entanglement-assisted quantum error correction code (EAQECC). The circulant matrix also plays an important role in cryptography. Yu [7] investigates the security of a cryptosystem which is based on compressed sensing. The cryptosystem encrypts a plaintext with a secret circulant matrix and transmits the ciphertext over a wireless channel. When the EA and AE robustness and X-robustness of interval circulant matrices over max-min algebra are defined, Myšková and Plavka [8] give polynomial algorithms for checking these types of robustness and X-robustness. By comparing the coefficients in the expansion of the permanent with those in the expansion of the determinant of a three-line circulant matrix, Poi et al. [9] solve a conjecture stated in the minimality of GT systems. Using block circulant matrices, Dong [10] considers the GPU acceleration of deep neural networks.Recently, many scholars focus on the norms, determinants, and inverses of circulant and r-circulant matrices whose entries are special integer sequences. In particular, various algorithms for the determinants and inverses of nonsingular circulant matrices andr-circulant matrices were gained. For example, Shen and Cen [11] get the upper and lower bounds for the spectral norms of r-circulant matrices in the forms A=CircrF0,F1,F2,…,Fn−1 and B=CircrL0,L1,L2,…,Ln−1 and obtain some bounds for the spectral norms of Kronecker and Hadamard products of A and B. Shen et al. [12] prove that circulant matrices A=CircF0,F1,F2,…,Fn−1 is invertible for n>2 and B=CircL0,L1,L2,…,Ln−1 is invertible for any positive integer n. The formulas for calculating the determinants and inverses of A and B are derived, respectively. Afterwards, Bozkurt and Tam [13] also find the explicit determinants and inverses of circulant matrices with Jacobsthal and Jacobsthal–Lucas numbers by the same matrix decompositions. Then, Bozkurt and Tam [14] analyze the determinants and inverses of r-circulant matrices with generalized linear recursive sequence and give more accurate bounds for spectral norms of r-circulant matrix involving Fibonacci and Lucas numbers. Yazlik and Taskara [15] summarize the computing method for inverse of circulant matrices, in which the elements include all second-order sequences and polynomials. Zheng and Shon [16] consider the invertibility of generalized Lucas skew circulant matrix and give the determinant and inverse matrix by constructing the transformation matrices. Carmona et al. [17] propose the necessary and sufficient conditions for the invertibility of some circulant matrices that depend on three parameters and compute explicitly the inverse of a general symmetric, circulant, and tridiagonal matrix. Hong and Jing [18] investigate the invertibility of the Tribonacci r-circulant matrix and show the determinant and the inverse matrix based on constructing the transformation matrices. He et al. [19] and Türkmen and Gökbas [20] study the spectral norm of r-circulant matrices with Fibonacci and Lucas numbers and Pell and Pell–Lucas numbers, respectively. When certain circulant matrices having k ones and k+1 zeros in the first row are nonsingular, Chen [21] proves the conditions which nonsingular matrices satisfy.Shen et al. [12] give the techniques for calculating the determinants and inverses of circulant matrices including Fibonacci and Lucas numbers. The authors construct two matrices P and Q1, which are convenient to obtain the determinant. Then, simplify the circulant matrix A to a simple form after promultiplied by P and postmultiplied by Q1. After that, they introduce an upper triangular matrix Q2 and reduce the product of PAQ1Q2 to a direct sum of two matrices and finally obtain the inverse matrices of A=CircF0,F1,F2,…,Fn−1 and B=CircL0,L1,L2,…,Ln−1.From the above papers, we find that there are no simple ways to compute the determinant and inverse ofr-circulant matrices. The r-circulant matrix An can be written as a polynomial about basic r-circulant matrix, π=Circr0,1,0,…,0. By simplifying the subtraction of An and Anπ, we obtain a special factorization E−απE−βπ. On the properties of Fibonacci and Lucas numbers, we use this new method of matrix decomposition to express the determinants and inverses of r-circulant matrices where the elements are Fibonacci and Lucas numbers. The nonsingular condition of the r-circulant matrices is obtained. The expression of the inverse is determined by the first row of the inverse matrix. These computing formulas are simpler than the related studies. Therefore, they are more useful for practical application.The arrangement of this paper is as follows. In Section2, we give the preliminary knowledge and lemmas. In Section 3, the determinants and inverses of r-circulant matrix with Fibonacci numbers are obtained. In Section 4, the determinants and inverses of r-circulant matrix with Lucas numbers are obtained. Section 5 presents numerical examples.


## 2. Preliminaries

Forn∈N0, the Fibonacci and Lucas numbers are defined by Fn+2=Fn+1+Fn and Ln+2=Ln+1+Ln under the initial conditions F0=0,F1=1 and L0=2,L1=1, respectively. Let α=1+5/2 and β=1−5/2 be the roots of the characteristic equation x2−x−1=0; then, the Binet formulas of the sequences Fn and Ln have the form(1)Fn=αn−βnα−β,Ln=αn+βn.Definition 1.
(see [8]). For any given c0,c1,…,cn−1∈C, the n×nr-circulant matrix Cn=Circrc0,c1,…,cn−1 is defined by(2)Cn=c0c1c2⋯cn−2cn−1rcn−1c0c1⋯cn−3cn−2⋮⋮⋮⋱⋮⋮rc2rc3rc4⋯c0c1rc1rc2rc3⋯rc1c0,
wherer=1 and Cn is a classical circulant matrix, and reduced to Cn=Circc0,c1,…,cn−1.Letπ=Circr0,1,0,…,0; we have πi=Circ0,…,0,1i+1,0,…,0 and πn=rE. If π0=E, we obtain(3)Cn=c0E+c1π+c2π2+⋯+cn−1πn−1.Lemma 1.
detaE−bπ=an−rbn.Lemma 2.
Inverse matrix of ther-circulant matrix is a r-circulant matrix.Lemma 3.
Product ofr-circulant matrices is a r-circulant matrix.Lemma 4.
(see [12]). Let An=CircF1,F2,…,Fn be a circulant matrix, and we have(4)detAn=1−Fn+1n−1+Fnn−2∑k=1n−1Fk1−Fn+1Fnk−1,where Fn is the nth Fibonacci number.Lemma 5.
(see [12]). Let An=CircF1,F2,…,Fnn>2 be a circulant matrix; we have(5)An−1=1fnCirc1+∑i=1n−2Fn−iFni−1F1−Fn+1i,−1+∑i=1n−2Fn−1−iFni−1F1−Fn+1i,−1F1−Fn+1,−FnF1−Fn+12,−Fn2F1−Fn+13,…,−Fnn−3F1−Fn+1n−2,where fn=F1−Fn+∑k=1n−2FkFn/F1−Fn+1n−k+1.Lemma 6.
(see [12]). Let Bn=CircL1,L2,…,Ln be a circulant matrix; the determinant of Bn is(6)detBn=1−Ln+1n−1+Ln−2n−2∑k=1n−1Lk+2−3Lk+11−Ln+1Ln−2k−1,where Ln is the nth Lucas number.Lemma 7.
(see [12]). Let Bn=CircL1,L2,…,Ln be a circulant matrix; the determinant of Bn is(7)Bn−1=1lnCirc1+∑i=1n−2Ln+2−i−3Ln+1−iLn−2i−1L1−Ln+1i,−3+∑i=1n−2Ln+1−i−3Ln−iLn−2i−1L1−Ln+1i,−5L1−Ln+1,−5Ln−2L1−Ln+12,−5Ln−22L1−Ln+13,…,−5Ln−2n−3L1−Ln+1n−2,where ln=L1−3Ln+∑k=1n−2Lk+2−3Lk+1Ln−2/L1−Ln+1n−k+1.Lemma 8.
(see [22]). Let C=circkc0,c1,c2,…,cn−1 be an invertible matrix with complex entries. Then, C−1=circkc0′,c1′,c2′,…,cn−1′, where c0′,c1′,c2′,…,cn−1′ is the unique solution of the following system of linear equations:(8)Cx0kxn−1⋮kx1=10⋮0.Lemma 9.
(see [23]). Let C=circnc0,c1,c2,…,cn−1k be a nonsingular matrix with complex entries. Then, C−1=circnc0′,c1′,c2′,…,cn−1′k, where c0′,c1′,c2′,…,cn−1′ is the unique solution of the following system of linear equations:(9)Cxj−1⋮x1x0kxn−1⋮kxj=0⋮010⋮0←j,j=1,n¯.


## 3. Determinant and Inverse of r-Circulant Matrix with Fibonacci Numbers

In this section,An=CircrF1,F2,…,Fn is a r-circulant matrix. A determinant formula for the r-circulant matrix An is obtained. We prove that An is an invertible matrix and obtain the inverse of the r-circulant matrix An.Theorem 1.
Whenr≠α−n and r≠β−n, the determinant of An is(10)detAn=1−rFn+1n−rn+1Fnn1+−1nr2−rLn,where Fn and Ln are the nth Fibonacci number and Lucas number, respectively.Proof.
From equation (3), An is represented by(11)An=F1E+F2π+F3π2+⋯+Fnπn−1.
Right multiplication matrixπ on both sides of equation (7) is(12)Anπ=F1π+F2π2+F3π3+⋯+Fnπn.
From (11) and (12), we obtain(13)An−Anπ=F1−rFnE+F2−F1π+F3−F2π2+⋯+Fn−Fn−1πn−1.
BecauseF0=0, F1=1, and Fn+2=Fn+1+Fn, equation (11) and equation (13) become(14)An−Anπ=F1−rFnE+F0π+F1π2+⋯+Fn−2πn−1=1−rFn−rFn−1E−rFnπ+F1E+F2π+F3π2+⋯+Fnπn−1π2=1−rFn+1E−rFnπ+Anπ2.
Thus,(15)AnE−π−π2=1−rFn+1E−rFnπ.
Whenr≠α−n, r≠β−n, and Lnn=αn+βn, we obtain(16)detE−π−π2=detE−απE−βπ=1−rαn1−rβn=1+−1nr2−rLn≠0.
From Lemma1, the determinant of equation (15) is(17)detAndetE−π−π2=detAnE−π−π2=det1−rFn+1E−rFnπ=1−rFn+1n−rn+1Fnn.
Hence, the determinant ofAn is(18)detAn=1−rFn+1n−rn+1Fnn1+−1nr2−rLn.
□Corollary 1.
Under the assumption of Theorem1, when r=1, the determinant of An is(19)detAn=1−Fn+1n−Fnn1+−1n−Ln,where Fn and Ln are the nth Fibonacci number and Lucas number, respectively.Proof.
From the proof of Theorem1, we have(20)AnE−π−π2=1−Fn+1E−Fnπ.
Whenr=1, we get 1≠α−n and 1≠β−n; thus,(21)detE−π−π2=detE−απE−βπ=1−αn1−βn=1+−1n−Ln≠0det1−Fn+1E−Fnπ=1−Fn+1n−Fnn.
Hence, we obtain(22)detAn=1−Fn+1n−Fnn1+−1n−Ln.
Obviously, the computation formula of Corollary1 is simpler than Lemma 4.Corollary 2.
Under the assumption of Theorem1, when 1−rFn+1/rFnn≠r, An is an invertible matrix.Proof.
Since1−rFn+1/rFnn≠r, we have(23)det1−rFn+1E−rFnπ=1−rFn+1n−rn+1Fnn≠0.
Then,(24)detAn=1−rFn+1n−rn+1Fnn1+−1nr2−rLn≠0.
Therefore,An is an invertible matrix.Theorem 2.
Under the assumption of Theorem1, if 1−rFn+1/rFnn≠r, the inverse of An is(25)An−1=xn−1xn+−1n−1rynCircry1,y2,y3,…,yn,where x=1−rFn+1, y=−rFn, xy≠0, y1=1−r−y/xn−2−r−y/xn−1, y2=−1−−y/x−r−y/xn−1, and yi=−y/xi−1−−y/xi−2−−y/xi−3i=3,4,…,n.Proof.
From the proof of Theorem1, we have(26)AnE−π−π2=1−rFn+1E−rFnπ.
When1−rFn+1/rFnn≠r, let x=1−rFn+1 and y=−rFn, xy≠0. From Lemma 2, the r-circulant matrix xE+yπ is an invertible r-circulant matrix. From Lemmas 8 and 9, xE+yπ−1=Circrx1,x2,x3,…,xn, where x1, x2, x3, ⋯, xn are the unique solutions of the following linear system:(27)xy0⋯00xy⋯0⋮⋮⋮⋱⋮000⋯yry00⋯xx1rxn⋮rx3rx2=10⋮00.
Then, the solution of equation (27) is(28)x1=xn−1xn+−1n−1ryn,x2=xn−1xn+−1n−1ryn−yx,x3=xn−1xn+−1n−1ryn−yx2,⋮xn=xn−1xn+−1n−1ryn−yxn−1.
Let(29)E−π−π2Circr1,−yx,−yx2,…,−yxn−1=Circry1,y2,…,yn.
We obtain(30)y1=1−r−yxn−2−r−yxn−1,y2=−1−yx−r−yxn−1,yi=−yxi−1−−yxi−2−−yxi−3,i=3,4,…,n.
Hence, the inverse ofAn is(31)An−1=xn−1xn+−1n−1rynCircry1,y2,y3,…,yn.
□Corollary 3.
Under the assumption of Theorem2, when 1−Fn+1/Fnn≠1 and r=1, the inverse of An is(32)An−1=xn−1xn+−1n−1ynCircr1−r−yxn−2−r−yxn−1,−1−yx−r−yxn−1,−yx2−−yx−1,…,−yxi−1−−yxi−2−−yxi−3,where x=1−Fn+1 and y=−Fn,xy≠0.Proof.
Under the condition of Corollary2, when 1−Fn+1/Fnn≠1 and r=1, then An is an invertible circulant matrix. From Theorem 2, we obtain(33)An−1=xn−1xn+−1n−1ynCircr1−r−yxn−2−r−yxn−1,−1−yx−r−yxn−1,−yx2−−yx−1,…,−yxi−1−−yxi−2−−yxi−3,where x=1−Fn+1 and y=−Fn,xy≠0.
Obviously, the formula of Corollary3 is simpler than Lemma 5.


## 4. Determinant and Inverse ofr-Circulant Matrix with Lucas Numbers

LetBn=CircrL1,L2,…,Ln be a r-circulant matrix, where Ln is the Lucas numbers. We discuss the nonsingular conditions for Bn and obtain the determinant formula and inverse of the r-circulant matrix Bn.Theorem 3.
Whenr≠α−n and r≠β−n, the determinant of Bn is(34)detBn=1−rLn+1n−rrLn−2n1+−1nr2−rLn,where Ln is the Lucas numbers.Proof.
By the proof of Theorem1, we have(35)BnE−π−π2=1−rLn+1E+2−rLnπ.
Whenr≠α−n, r≠β−n, and Ln=αn+βn, we obtain(36)detE−π−π2=1+−1nr2−rLn≠0.
From Lemma1, we obtain(37)det1−rLn+1E+2−rLnπ=1−rLn+1n−rrLn−2n.
Hence, the determinant ofBn is(38)detBn=1−rLn+1n−rrLn−2n1+−1nr2−rLn.
□Corollary 4.
Under the assumption of Theorem3, when r=1, the determinant of Bn is(39)detBn=1−Ln+1n−Ln−2n1+−1n−Ln,where Ln is the nth Lucas number.Obviously, the computation formula of Corollary4 is simpler than Lemma 6.Corollary 5.
Under the assumption of Theorem3, when 1−rLn+1/rLn−2n≠r, Bn is an invertible matrix.Proof.
Since1−rLn+1/rLn−2n≠r, we obtain(40)det1−rLn+1E+2−rLnπ=1−rLn+1n−rrLn−2n≠0.
Because(41)detBn≠0,Bn is an invertible matrix.Theorem 4.
Under the assumption of Theorem3, if 1−rLn+1/rLn−2n≠r, the inverse of Bn is(42)Bn−1=xn−1xn+−1n−1rynCircry1,y2,y3,…,yn,where x=1−rLn+1, y=2−rLn, xy≠0, y1=1−r−y/xn−2−r−y/xn−1, y2=−1−y/x−r−y/xn−1, andyi=−y/xi−1−−y/xi−2−−y/xi−3i=3,4,…,n.Proof.
From the proof of Theorem3, we have(43)BnE−π−π2=1−rLn+1E+2−rLnπ.
When1−rLn+1/rLn−2n≠r, let x=1−rLn+1 and y=2−rLn, xy≠0; from Lemma 2, the r-circulant matrix xE+yπ is an invertible r-circulant matrix. From Lemmas 8 and 9, xE+yπ−1=Circrx1,x2,x3,…,xn, where x1, x2, x3, ⋯, xn are the unique solution of the following linear system:(44)xy0⋯00xy⋯0⋮⋮⋮⋱⋮000⋯yry00⋯xx1rxn⋮rx3rx2=10⋮00.
Then, the solution of equation (44) is(45)x1=xn−1xn+−1n−1ryn,x2=xn−1xn+−1n−1ryn−yx,x3=xn−1xn+−1n−1ryn−yx2,⋮xn=xn−1xn+−1n−1ryn−yxn−1.
Since(46)E−π−π2Circr1,−yx,−yx2,…,−yxn−1=Circry1,y2,…,yn.
We obtain(47)y1=1−r−yxn−2−r−yxn−1,y2=−1−yx−r−yxn−1,yi=−yxi−1−−yxi−2−−yxi−3i=3,4,…,n.
Hence, the inverse ofBn is(48)A−1=xn−1xn+−1n−1rynCircry1,y2,y3,…,yn.
□Corollary 6.
Under the assumption of Theorem4, when 1−Ln+1/Ln−2n≠1 and r=1, the inverse of Bn is(49)Bn−1=xn−1xn+−1n−1ynCircr1−r−yxn−2−r−yxn−1,−1−yx−r−yxn−1,−yx2−−yx−1,…,−yxi−1−−yxi−2−−yxi−3,where x=1−Ln+1 and y=2−Ln, xy≠0.Proof.
Under the condition of Corollary5, when 1−Ln+1/Ln−2n≠1 and r=1, then Bn is an invertible circulant matrix. From proof of Theorem 4, we obtain(50)Bn−1=xn−1xn+−1n−1ynCircr1−r−yxn−2−r−yxn−1,−1−yx−r−yxn−1,−yx2−−yx−1,…,−yxi−1−−yxi−2−−yxi−3,where x=1−Ln+1 and y=2−Ln, xy≠0. Obviously, the formula of Corollary 6 is simpler than Lemma 7.


## 5. Numerical Examples

Next, we further discuss our conclusion through numerical simulation.Example 1.
Whenr=1 and n=1000, we obtain the inverse matrix of An by Lemma 5 and Corollary 3.Example 2.
Whenr=1 and n=1000, we obtain the inverse matrix of Bn by Lemma 7 and Corollary 6.Examples1 and 2 calculate the inverse of a matrix for 1000 orders. Due to the limited space, we only cut 12 orders. Through Figures 1–4, we can find that our conclusion is more accurate than Lemmas 5 and 7 in the process of numerical simulation. At the same time, in the process of practical application, our conclusion will further reduce the error.Figure 1
The result of Lemma5.Figure 2
The result of Corollary3.Figure 3
The result of Lemma7.Figure 4
The result of Corollary6.Example 3.
Whenr=1, we compare the running time of Lemma 4 and Corollary 1 in milliseconds (ms).Example 4.
Whenr=1, we compare the running time of Lemma 6 and Corollary 4 in milliseconds (ms).Through calculating, it can be concluded that the time complexity of these formulas in Lemmas4–7 are On2. And the time complexity of formulas in Corollaries 1–6 are On. This new method of matrix decomposition reduces computation by an order of magnitude. We also find that the computation time is greatly reduced through programming with C language. From Tables 1 and 2, the same conclusions are easily found. We calculate the inverse matrices by MATLAB; when n⩾1000, the expression for the inverse matrices are more accurate than Lemmas 5 and 7.Table 1
Running time comparison of Lemma4 and Corollary 1.
nLemma4Corollary12000253116301721093522781201362855199637475832763875505164Table 2
Running time comparison of Lemma6 and Corollary 4.
nLemma6Corollary420002547153028110935307311863649761903378112302638129794992


## 6. Conclusion

In this paper, we use a new matrix decomposition method to solve the determinant and inversem of the r−circulant matrix with Fibonacci sequence and Lucas sequence. Some simpler forms are obtained and the corresponding proofs are given. Through numerical examples, we find that the new formulas not only reduce the computation time of determinant but also increase the accuracy of solving inverse matrix and are more conducive to the application of real life.



---

*Source: 4782594-2021-11-18.xml*