# Algorithms for Finding Inverse of Two Patterned Matrices overZp

Authors: Xiaoyu Jiang; Kicheon Hong
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Circulant matrix families have become an important tool in network engineering. In this paper, two new patterned matrices overZp which include row skew first-plus-last right circulant matrix and row first-plus-last left circulant matrix are presented. Their basic properties are discussed. Based on Newton-Hensel lifting and Chinese remaindering, two different algorithms are obtained. Moreover, the cost in terms of bit operations for each algorithm is given.


---

## Body

## 1. Introduction

Circulant matrix families play an important role in network engineering. Basic [1] gave a simple condition for characterizing weighted circulant graphs allowing perfect state transfer in terms of their eigenvalues. Noual et al. [2] showed some preliminary results on the dynamical behaviours of some specific nonmonotone Boolean automata networks that were called xor circulant networks. Using the circulant matrix, the charge transport and the noise of a quantum wire network, made of three semi-infinite external leads attached to a ring crossed by a magnetic flux, were investigated [3]. Based on the circulant adjacency matrices of the networks induced by these interior symmetries, Aguiar and Ruan [4] analyzed the impact of interior symmetries on the multiplicity of the eigenvalues of the Jacobian matrix at a fully synchronous equilibrium for the coupled cell systems associated with homogeneous networks. Involving circulant matrix, the storage of binary cycles in Hopfield-type and other neural networks was investigated [5]. A new structure for the decoupling of circulant symmetric arrays of more than four elements was presented in [6]. Wang and Cheng [7] studied the existence of doubly periodic travelling waves in cellular networks involving the discontinuous Heaviside step function by circulant matrix. Pais et al. [8] proved conditions for the existence of stable limit cycles arising from multiple distinct Hopf bifurcations of the dynamics in the case of circulant fitness matrices. Cho and Chung [9] discussed the routing of a message on circulant networks, that is, a key to the performance of this network. Grassi [10] designed DTCNNs where each trajectory converges to a unique equilibrium point, which depends only on the input and not on the initial state, by exploiting the global asymptotic stability of the equilibrium point of DTCNNs with circulant matrices. Wu [11] obtained the coexistence of multiple large-amplitude wave solutions for the delayed Hopfield-Cohen-Grossberg model of neural networks with a symmetric circulant connection matrix. The system model of the OFDM is based on AF relay networks as well as the strategy of the superimposed training involved circulant matrix [12]. Two-way transmission model was considered in [13] and ensured circular convolution between two frequency selective channels.In this paper, we give two algorithms for ann×n nonsingular RSFPLR circulant matrix over Zp. The primitive problem is transformed into an equivalent problem over Zp[x]. The first algorithm supposes the factorization of p is given and the costs of multiplications and additions over Zp are nlog2n+nlog⁡p and nlog2nlog⁡log⁡n, respectively. We obtain the bit complexity bound:
(1)O((nlog2n+nlog⁡p)μ(log⁡p)+nlog2nlog⁡log⁡nlog⁡p),
where μ(d) denotes the bit complexity of multiplying d-bit integers. The second algorithm does not know the factorization of p and its cost is greater, by a factor log⁡p, than in the first algorithm.Definition 1.
A row skew first-plus-last right (RSFPLR) circulant matrix with the first row(a0,a1,…,an-1) over Zp, denoted by RSFPLRcircfr(a0,a1,…,an-1), meant a square matrix of the form
(2)(a0a1⋯an-1-an-1a0+an-1⋱an-2⋮-an-1+an-2⋱⋮-a2⋮⋱a1-a1-a2+a1⋯a0+an-1)n×n.
Obviously, the RSFPLR circulant matrix over a field is axn-x+1-circulant matrix [14], and that is neither the extention of circulant matrix over Zp [15] nor its special case, and they are two different families of patterned matrices.
We defineΘ(-1,1) as the basic RSFPLR circulant matrix over Zp; that is,
(3)Θ(-1,1)=(010⋯0⋮⋱⋱⋱⋮⋮⋱⋱00⋯⋯01-110⋯0)n×n=RSFPLRcircfr(0,1,0,…,0).
It is easily verified thatg(x)=xn-x+1 has no repeated roots over Zp and g(x)=xn-x+1 is both the minimal polynomial and the characteristic polynomial of the matrix Θ(-1,1). In addition, Θ(-1,1) is nonderogatory and satisfies Θ(-1,1)j=RSFPLRcircfr(0,…,0︸j,1,0,…,0︸n-j-1) and Θ(-1,1)n=In-Θ(-1,1). In view of the structure of the powers of the basic RSFPLR circulant matrix Θ(-1,1) over Zp, it is clear that
(4)A=RSFPLRcircfr(a0,a1,…,an-1)=∑i=0n-1‍aiΘ(-1,1)i.
Thus, A is a RSFPLR circulant matrix over Zp if and only if A=f(Θ(-1,1)) for some polynomial f(x) over Zp. The polynomial f(x)=∑i=0n-1‍aixi will be called therepresenter of the RSFPLR circulant matrix A over Zp. By Definition 1 and (4), it is clear that A is a RSFPLR circulant matrix over Zp if and only if A commutes with Θ(-1,1); that is, AΘ(-1,1)=Θ(-1,1)A.
In addition to the algebraic properties that can be easily derived from the representation (4), we mention that RSFPLR circulant matrices have very nice structure. The product of two RSFPLR circulant matrices is a RSFPLR circulant matrix and A-1 is a RSFPLR circulant matrix, too. Furthermore, let Zp[Θ(-1,1)]={A∣A=f(Θ(-1,1)),f(x)∈Zp[x]}. It is a routine to prove that Zp[Θ(-1,1)] is a commutative ring with the matrix addition and multiplication.Definition 2.
A row first-plus-last left (RSLPFL) circulant matrix with the first row(a0,a1,…,an-1) over Zp, denoted by RSLPFLcircfr(a0,a1,…,an-1), meant a square matrix of the form
(5)(a0a1⋯an-2an-1a1a2⋯an-1+a0-a0⋮⋮⋰-a0+a1⋮an-2⋰⋰⋮-an-3an-1+a0⋯⋯-an-3+an-2-an-2)n×n.Lemma 3.
Let(6)I^n=(00⋯0100⋯10⋯⋯⋯⋯⋯10⋯00)
be the n×n matrix of the counteridentity. Then(i)
RSLPFLcircfr(a0,a1,…,an-1)=RSFPLRcircfr(an-1,…,a1,a0)In^;(ii)
RSLPFLcircfc(a0,a1,…,an-1)In^=RSFPLRcircfc(an-1,…,a1,a0).LetA be a nonsingular matrix over Zp; we explore the problem of finding a RSFPLR circulant matrix B=∑i=0n-1‍biΘ(-1,1)i, such that AB=I.SolvingA-1 is clearly equivalent to finding a polynomial g(x)=∑i=0n-1‍bixi in Zp[x] such that
(7)f(x)g(x)≡1(mod⁡xn-x+1).The congruence moduloxn-x+1 follows from the equality Θ(-1,1)n=In-Θ(-1,1). Hence, the problem of solving A-1 is equivalent to inversion in the ring Zp[x]/〈xn-x+1〉.The following theorem describes a necessary and sufficient condition for the nonsingularity of a RSFPLR circulant matrix overZp.Theorem 4.
LetA=RSFPLRcircfr(a0,a1,…,an-1) be a RSFPLR circulant matrix over Zp; then the matrix A is nonsingular if and only if
(8)gcd(f(x),xn-x+1)=1inZpi[x],
for i=1,…,l, where p=p1k1p2k2⋯plkl is the prime powers factorization of p and f(x)=∑j=0n-1‍ajxj.Proof.
IfA is nonsingular, by (7), there exists s(x) such that, for i=1,…,l,
(9)f(x)g(x)+s(x)(xn-x+1)=1inZpi[x];
that is, gcd(f(x),xn-x+1)=1 in Zpi[x].
The proof of sufficient condition for nonsingularity will be given in Section2 (Lemmas 5 and 6).Review of Bit Complexity Results [15]. The sum of two polynomials in Zp[x] of degree at most n can be trivially calculated in O(nlog⁡p) bit operations. The product of two such polynomials can be calculated in O(nlog⁡n) multiplications and O(nlog⁡nlog⁡log⁡n) additions or subtractions in Zp. Therefore, the cost of polynomial multiplication is O(∏‍(p,n)) bit operations, where
(10)Π(p,n)=nlog⁡nμ(log⁡p)+nlog⁡nlog⁡log⁡nlog⁡p.Leta(x),b(x) be two polynomials of degree at most n over Zp[x] (p prime); we calculate d(x)=gcd(a(x),b(x)) in O(Γ(p,n)) bit operations, where
(11)Γ(p,n)=Π(p,n)log⁡n+nμ(log⁡p)log⁡log⁡p.


## 2. Finding Inversion inZp[x]/〈xn-x+1〉 for Factorization of p Given

In this section, letp=p1k1p2k2⋯plkl be the given prime powers factorization of p. In the following, we discuss the inverse of a RSFPLR circulant matrix over Zp by studying the equivalent problem, that is, finding the inversion of a polynomial f(x) over Zp[x]/〈xn-x+1〉. We obtain algorithms of calculating the inverse via Chinese remaindering, the extended Euclidean algorithm, and Newton-Hensel lifting.Lemma 5.
Letg1(x),…,gl(x) be known such that
(12)f(x)gi(x)≡1(modxn-x+1)inZpiki[x],
for i=1,2,…,l and p=p1k1p2k2⋯plkl and f(x) is a polynomial in Zp[x].
One can solveg(x)∈Zp[x] such that
(13)f(x)g(x)≡1(modxn-x+1),
and the cost of bit operations is O(nlμ(log⁡p)+μ(log⁡p)log⁡log⁡p).Proof.
Due tof(x)gi(x)≡1(mod⁡xn-x+1) in Zpiki[x], we get
(14)f(x)gi(x)≡1+λi(x)〈xn-x+1〉(mod⁡piki).
Letαi=p/piki. Distinctly, for j≠i,αi≡0 (mod⁡pjkj). Since gcd(αi,piki)=1, we can solve βi which satisfies αiβi≡1 (mod⁡piki). Let g(x)=∑i=1l‍αiβigi(x),λ(x)=∑i=1l‍αiβiλi(x).
By construction, fori=1,2,…,l, we get g(x)≡gi(x) (mod⁡piki) and λ(x)≡λi(x) (mod⁡piki). Then, for i=1,2,…,l, we obtain f(x)g(x)=∑j=1l‍αjβjf(x)gj(x)≡ f(x)gi(x)(mod⁡piki)≡1+λi(x)〈xn-x+1〉(mod⁡piki)≡1+λ(x)〈xn-x+1〉(mod⁡piki). We come to the conclusion that
(15)f(x)g(x)≡1+λ(x)〈xn-x+1〉(mod⁡p);
that is,
(16)f(x)g(x)≡1(mod⁡xn-x-1)inZp[x].
The computation ofg(x) consists in n (one for each coefficient) applications of Chinese remaindering. Obviously, the computation of αi,βi,i=1,…,l should be done only once. Since integer division has the same asymptotic cost as multiplication, the cost of bit operations for αi,…,αl is O(lμ(log⁡⁡p)). Because each βi is got via an inversion in Zpiki, the cost of bit operations for β1,…,βl is O(∑j=1l‍μ(log⁡pjkj)log⁡log⁡pjkj). Finally, the cost of bit operations for calculating g(x) is O(nlμ(log⁡⁡p)) by using α1,…,αl,β1,…,βl,g1(x),…,gl(x). The thesis follows using the inequality
(17)μ(log⁡a)log⁡log⁡a+μ(log⁡b)log⁡log⁡b≤μ(log⁡(ab))log⁡log⁡(ab).By Lemma5, we can find the inversion of a polynomial over Zp[x]/〈xn-x+1〉 when p=rk is a prime power. The following lemma presents how to solve this special problem.Lemma 6.
Supposegcd(f(x),xn-x+1)=1 in Zr[x]; then f(x) is invertible in Zrk[x]/〈xn-x+1〉, where f(x) is a polynomial in Zrk[x]. In this case, the cost of bit operations for the inverse of f(x) is O(Γ(r,n)+Π(rk,n)), where Γ(r,n) and Π(rk,n) are the same as (11) and (10), respectively.Proof.
Supposegcd(f(x),xn-x+1)=1 in Zr[x]; by Bezout’s lemma, there exist s(x),t(x) which satisfy
(18)f(x)s(x)+〈xn-x+1〉t(x)≡1(mod⁡r).
In the following, we consider Newton-Hensel lifting; that is,
(19)g0(x)=s(x),gi(x)=2gi-1(x)-[gi-1(x)]2f(x)mod⁡xn-x+1.
It is easy to verify by induction that gi(x)f(x)≡1+r2iλi(x)(mod⁡xn-x+1). Therefore, the inverse element of f(x) in Zrk[x]/〈xn-x+1〉 is g⌈log⁡k⌉(x).
The cost of bit operations for calculatings(x) is O(Γ(r,n)). Calculating g1(x),g2(x),…,g⌈log⁡k⌉(x) is calculating each gi modulo r2i. Therefore, the cost of bit operations for the whole sequence is O(Π(r2,n)+Π(r4,n)+⋯+Π(r2⌈log⁡k⌉,n))=O(Π(rk,n)).By Theorem4 and Lemmas 5 and 6, we obtain Algorithm 1 for the inversion of a polynomial f(x) over Zp[x]/〈xn-x+1〉. The cost of bit operations for the algorithm is T(p,n)=O(nlμ(log⁡p)+μ(log⁡p)log⁡log⁡p+∑j=1l‍Γ(pj,n)+Π(pjkj,n)), where l and pj are bounded by log p and pjkj, respectively. On the side, by using Π(a,n)+Π(b,n)≤Π(ab,n) and Γ(a,n)+Γ(b,n)≤Γ(ab,n), we get
(20)T(p,n)=O(nlog⁡pμ(log⁡p)+μ(log⁡p)log⁡log⁡paaaa+Γ(p,n)+Π(p,n))=O(nlog⁡pμ(log⁡p)+Π(p,n)log⁡n).
Particularly, if p=O(n), the ascendent term is Π(p,n)log⁡n. That is, the cost of calculating the inverse of f(x) is gradually bounded by the cost of executing log⁡n multiplications in Zp[x].Algorithm 1:Finding inversion in Zp[x]/〈xn-x+1〉 for factorization of p given.
Inverse1(f(x),p,n)→g(x)
{Calculates the inverseg(x) of f(x)  in Zp[x]/〈xn-x+1〉}
(1)letp=p1k1p2k2,…,plkl;
(2)for  j=1,2,…,l do
(3)if  gcd(f(x),xn-x+1)=1 in Zpj[x] then
(4)calculate gj(x) which satisfy
f(x)gj(x)≡1(mod xn-x+1) in Zpjkj[x]
(5)using Newton-Hensel lifting (Lemma 6);
(6)else
(7)return “f(x) is not invertible”;
(8)endif
(9)endfor
(10) calculateg(x) using Chinese remaindering (Lemma 5).


## 3. Algorithm of Finding Inversion inZp[x]/〈xn-x+1〉 for Factorization of p Unknown

In this section, we show how to compute the inverse off(x) without knowing the factorization of the modulus. The number of bit operations of the new algorithm is only a factor O(log⁡p) greater than in the previous case.Our idea consists in trying to computegcd(f(x),xn-x+1) in Zp[x] using the gcd algorithm for Zp[x]. Such algorithm requires the inversion of some scalars, which is not a problem in Zp[x], but it is not always possible if p is not prime. Therefore, the computation of gcd(f(x),xn-x+1) may fail. However, if the gcd algorithm terminates, we have solved the problem. In fact, together with the alleged gcd a(x), the algorithm also returns s(x),t(x) such that f(x)s(x)+(xn-x+1)t(x)=a(x) in Zp[x]. If a(x)=1, then s(x) is the inverse of f(x). If deg⁡(a(x))≠0, one can easily prove that f(x) is not invertible in Zp[x]/〈xn-x+1〉. Note that we must force the gcd algorithm to return a monic polynomial.If the computation ofgcd(f(x),xn-x+1) fails, we use recursion. In fact, the gcd algorithm fails if it cannot invert an element y∈Zp. Inversion is done by using the integer gcd algorithm. If y is not invertible, the integer gcd algorithm returns d=gcd(p,y), with d>1. Hence, d is a nontrivial factor of p. We use d to compute either a pair m1,m2, such that gcd(m1,m2)=1 and m1m2=p, or a single factor m1, such that m1∣p and p∣(m1)2. In the first case, we invert f(x) in Zm1[x]/〈xn-x+1〉 and Zm2[x]/〈xn-x+1〉, and we use Chinese remaindering to get the desired result. In the second case, we invert f(x) in Zm1[x]/〈xn-x+1〉 and we use one step of Newton-Hensel lifting to get the inverse in Zp[x]/〈xn-x+1〉.The computation of the factorsp1,p2 is done by procedure GetFactors whose correctness is proven by Lemmas 4.1 and  4.2 in [15]. Combining these procedures together, we get Algorithm 2.Algorithm 2:Finding inversion in Zp[x]/〈xn-x+1〉 for factorization of p unknown.
Inverse2(f(x),p)→g(x)
{Calculates the inverseg(x) of f(x) in Zp[x]/〈xn-x+1〉}
(1)if  gcd(f(x),xn-x+1)=1  then
(2)let  s(x),t(x) which satiefy f(x)s(x)+(xn-x+1)t(x)=1 in Zp[x];
(3)return  s(x);
(4)else if  gcd(f(x),xn-x+1)=a(x),  deg⁡(a(x))>0  then
(5)return “f(x) is not invertible”;
(6)else if  gcd(f(x),xn-x+1) fails let d satisfy  d∣p;
(7)let  (m1,m2)← GetFactors(p,d);
(8)if  m2≠1,then
(9)g1(x)← Inverse2(f(x),m1);
(10)  g2(x)← Inverse2(f(x),m2);
(11)  calculate g(x) using Chinese remaindering  (Lemma 5);
(12)else
(13)  g1(x)← Inverse2(f(x),m1);
(14)  calculate g(x) using Newton-Hensel lifting (Lemma 6);
(15)endif
(16)return  g(x);
(17)endif
GetFactors  (p,d)→(m1,m2)
(18)let  m1←gcd(p,d⌊log⁡p⌋);
(19)if (p/m1)≠1  then
(20)return  (m1,p/m1);
(21)endif
(22)let  e←p/d;
(23)let  m1←gcd(p,e⌊log⁡p⌋);
(24)  if(p/m1)≠1  then
(25)return  (m1,p/m1);
(26)endif
(27)let  m1←lcm(d,e);
(28)return  (m1,1);Theorem 7.
Supposef(x) is invertible in Zp[x]/〈xn-x+1〉; the cost of bit operations for Algorithm 2 which returns the inverse g(x) is O(Γ(p,n)log⁡p).Proof.
It is similar to the proof of Theorem  4.3 in [15].In addition, by Lemma3 and Algorithms 1 and 2, it is easy to get two algorithms for inverting RSLPFL circulant matrices over Zp, respectively.


## 4. Conclusion

In this paper, we consider the problem of finding inverse matrix for an×n RSFPLR circulant matrix with entries over Zp. We present two different algorithms. Our algorithms require different degrees of knowledge of p and n, and their costs range, roughly, from nlog⁡⁡nlog⁡⁡log⁡⁡n to nlog⁡⁡2nlog⁡⁡log⁡⁡nlog⁡⁡p operations over Zp. Moreover, for each algorithm, we give the cost in terms of bit operations. Finally, the extended algorithms are used to solve the problem of inverting RSLPFL circulant matrices over Zp. Based on the existing problem in [16–19], we will develop solving these problems by circulant matrices technology.



---

*Source: 840435-2014-08-26.xml*