# Generalized Serre Problem over Elementary Divisor Rings

Authors: Licui Zheng; Jinwang Liu; Weijun Liu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Matrix factorization has been widely investigated in the past years due to its fundamental importance in several areas of engineering. This paper investigates completion and zero prime factorization of matrices over elementary divisor rings (EDR). The Serre problem and Lin-Bose problems are generalized to EDR and are completely solved.


---

## Body

## 1. Introduction

In engineering and communication sciences, polynomial matrices are used in several different areas including circuits, multidimensional systems, controls, signal processing, and other areas. The Serre problem (or Serre Theorem) stands for a fundamental breakthrough in the understanding of polynomial matrices, and it is a powerful mathematical tool for engineers in practical designs. Following the work of Youla and Gnavi [1] on the basic structure of n-D system theory, many papers have been published in studying various prime factorization of multivariate polynomial matrices.Lin and Bose in 2001 [2] formulated a generalized Serre conjecture for the polynomial ring k[x1,x2,…,xn] over a field k. They found out that zero prime matrix completion and matrix primitive factorization were all related to the generalized Serre conjecture. So they proposed the existence problem of zero prime factorization for n-D polynomial matrices, which is now called Lin-Bose problem and it has been solved in [3–5].We are interested in generalizing Serre conjecture and Lin-Bose problem to elementary divisor rings, which is defined in the next section. For example, let(r1,r2,…,rn) be any row vector with entries in R, and let d be any maximal common divisor of r1,…,rn. We want to know if the row can be completed to a square matrix whose determinant is d. More generally, we will solve both Serre problem and Lin-Bose problem for an arbitrary matrix (not just a row) over elementary divisor rings.The organization of the paper is as follows. In Section2, we first give some basic notions and describe Serre Problem and Lin-Bose problem precisely. In Section 3, we give proofs for the problems proposed in Section 2. Finally, a brief conclusion is given in Section 4.


## 2. Basic Notions and Main Problems

LetR be a commutative ring with a unity element 1 and Ml×m(R) the free module of l×m matrices with entries in R. For any A∈Ml×m(R), It(A) denotes the ideal of R generated by all t×t minors of A, where 1≤t≤min⁡(l,m). Set I0(A)=0. The rank of A is defined to be(1)rank⁡A=max⁡t:0≤t≤r,AnnRItA=0, where AnnR(It(A))={r∈R:rc=0for allc∈It(A)}. When rank⁡(A)=l, we say A is of full row rank.Definition 1.
A commutative ringR is called an elementary divisor ring (EDR) if, for every m≤n and every matrix A∈Mm×n(R), there exist P∈GLm(R) and Q∈GLn(R) such that PAQ=D with D=(dij) is diagonal and every dii divides di+1,i+1.Whenm=1, A is row vector (a1,a2,…,an); the requirement PAQ=D implies that the ideal a1R+a2R+⋯+anR is generated by one element. So, in an elementary divisor ring, every finitely generated ideal is generated by one element. Note that an elementary divisor ring may not be a principle ideal domain, nor a unique factorization domain.Definition 2.
LetF∈Rl×m (or F∈Rm×l), where l≤m, be of full row rank. Then F is said to be (i)
ZLP (or ZRP) if alll×l minors of F generate the unit ideal R;(ii)
MLP if alll×l minors of F are relatively prime; that is, d(F) is a unit in R, where d(F) refer to the maximal common divisor of all l×l minors of F.Definition 3.
Leta1,a2,…,an∈R. d is said to be a common divisor of a1,a2,…,an if d∣ai, i=1,2,…,n. When d is divisible by every common divisor of a1,a2,…,an, one says that d is a maximal common divisor of a1,a2,…,an.Note that, for any two maximal common divisors ofa1,a2,…,an, since they divide each other, they are always associates of each other; that is, they are different only by a factor that is invertible in R. Let D(a1,…,an) denote the set of all maximal common divisors of a1,…,an.Lemma 4.
LetR be an elementary divisor ring and a1,…,an∈R. For any d∈R, one has d∈D(a1,…,an) if and only if a1R+⋯+anR=dR.Proof.
First supposea1R+⋯+anR=dR. Since R has a unity element 1, we have ai=ai·1∈aiR⊂dR, so d∣ai for i=1,…,n. Also, a1r1+⋯+anrn=d for some ri∈R; hence, for any b∈R such that b∣ai for i=1,…,n, we must have b∣d. Thus d∈D(a1,…,an).
Next supposed∈D(a1,…,an). Then ai=dri for some ri∈R, i=1,2,…,n, so a1R+⋯+anR⊆dR. Since R is an EDR, there exists e∈R such that a1R+⋯+anR=eR. This implies that e∣ai, i=1,…,n, so e∣d; thus d∈eR and dR⊆eR=a1R+⋯+anR. Therefore, a1R+⋯+anR=dR.A direct consequence of the above lemma is that, in an elementary divisor ring, any collection of elementsa1,a2,…,an∈R has at least one maximal common divisor, since the ideal a1R+⋯+anR is generated by one element. This means that, for a unimodular row (a1,a2,…,an), the maximal common divisors of a1,a2,…,an must be units.Definition 5.
LetF∈Ml×m(R) with l≤m, and let a1,a2,…,aβ denote all l×l minors of F, where β=m!/(m-l)!l!. Assume that there exists a maximal common divisor d(F) of a1,a2,…,aβ. Let bi be such that ai=dbi, i=1,2,…,β. Then b1,b2,…,bβ are called the “reduced minors” of F with respect to d.The original Serre problem and Lin-Bose problems are about the ringA=k[x1,x2,…,xn], a polynomial ring in the variable x1,x2,…,xn over a field k. More precisely, for any F∈Ml×n(A) (l≤n) of full row rank, let d(F) be the greatest common divisor of all l×l minors of F. Suppose all reduced minors of F generate A. Then Serre’s problem says that there exists a matrix E∈A(m-l)×l such that det⁡AE=d(F). Lin-Bose problem says that we can decompose F as F=D·F1, where D∈Ml×l(A), F1∈Ml×n(A), detD=d(F), and F1 is ZLP.In this paper, we extend the above two problems over to elementary divisor rings. Precisely, we completely solve the following problems.Problem 6.
LetR be an elementary divisor ring and A∈Ml×n(R), where l≤n, is of full row rank. Let d be a maximal common divisors of all l×l minors of A. (a)
(Serre) Is there a matrix E∈A(m-l)×l such that detAE=d?(b)
(Lin-Bose) Is it possible to write A as A=F·G1, where F∈Ml×l(R) with det⁡(F)=d and G1∈Ml×n(R) is ZLP?


## 3. Main Results

In this section, we give our main results. First, let us give some basic facts. For more details, we refer to [6]. Let R be a commutative ring. Then any finite number of elements in R have a maximal common divisor. Let A∈Ml×mR(l≤m) be of full row rank. Let a1,a2,…,at’s be all of its l×l minors and d the maximal common divisor of ai’s. Then there exists a matrix Hi∈Mm×l(R) such that AHi=aiIl=bidIl, where ai=bid and Il is the l×l identity matrix. Furthermore, if all the reduced minors of A generate the unit ideal R, then there exists a matrix H∈Mm×l(R) such that A·H=dIl. When l≥m, we have H·A=dIm.Lemma 7.
LetR be an EDR. Let P∈Ml×n(R) with l≤n with d being a maximal common divisor of all l×l minors of P. Then, for every F∈GLn(R), the matrix Q=PF also has d as a maximal common divisor of its l×l minors.Proof.
Letd′ be any maximal divisor of all l×l minors of Q with d′≠d. Let Qk be any l×l submatrix of Q. Then Qk=PFk, where Fk is a n×l submatrix of F. Then, by Cauchy-Binet formula, we can get that det⁡(Qk)=∑‍Δiδi, where Δi and δi are l×l minors of P and Fk, respectively. Since, for every i, we have d∣Δi and d∣det⁡(Qk), by the arbitrariness of Qk, we get d∣d′. Since QF-1=P, by the same reason, we have d′∣d, so dR=d′R. Therefore, d is also a maximal divisor of minors of Q.Theorem 8.
LetR be anEDR and A∈Ml×n(R). Let (r1,r2,…,rn) be an arbitrary row of A and d any maximal common divisor of r1,r2,…,rn. Then (r1,r2,…,rn) can be completed to a square matrix (2)r1,r2,…,rnCwhose determinant is d. Furthermore, the (n-1)×n matrix C may be chosen to be itself completed to a matrix in GLn(R).Proof.
Assume without loss of generality that(r1,r2,…,rn) is the first row of A; then according to the definition of an elementary divisor ring, there exist P1∈GLl(R) and Q1∈GLn(R) such that(3)P1AQ1=diag⁡d1,d2,…,dn. By Lemma 4  d1 is a maximal common divisor of (r1,r2,…,rn). Assume that det⁡(P1)=u and det⁡(Q1)=v are units in R. Let(4)P=diag⁡1,u-1,…,1P1,Q=Q1·diag⁡1,v-1,…,1.Then, det⁡(P)=det⁡(Q)=1, P∈SLl(R), Q∈SLn(R), and (5)Pr1,r2,…,rnA′Q=diag⁡d1,d2,…,dn, where A′ is the submatrix of A formed by the remaining rows after removing (r1,r2,…,rn) from A.
SetC=P-1(O(n-1)×1In-1)Q-1. Then(6)Pr1,r2,…,rnCQ=d101×n-1On-1×1In-1. Note that det(P)=det⁡(Q)=1. Thus(7)det⁡r1,r2,…,rnC=det⁡d101×n-1On-1×1In-1=d1. So C is ZLP and can be completed to matrix in GLn(R).
By Lemma4, dR=a1R+a2R+⋯+anR=d1R; we have that d=d1x and d1=dy, where x,y∈R. Then(8)d,0y1-yx-1x=d1,0. This proves the theorem.In the above theorem,d is an arbitrary maximal common divisor, but R is not UFD so the maximal common divisors are not unique. If d is a beforehand given maximal common divisor, is the above theorem also correct? The following theorem gives a positive answer.Theorem 9.
LetR be anEDR and F∈Ml×n(R) with l≤n. Then there exist A∈Ml×l(R) and F1∈Ml×n(R) such that F=A·F1, where det⁡(A) is a maximal common divisor of all l×l minors of F and F1 is ZLP.Proof.
SinceR is an elementary divisor ring, there exist P∈SLl(R) and Q∈SLn(R) such that(9)PFQ=D1,0,whereD1=diag⁡d1,d2,…,dl, and every di is a divisor of di+1, and 0∈Ml×(n-l)(R). By Lemma 7, det(D1)=d1d2⋯dl is a maximal common divisor of all l×l minors of A. Partition Q-1 as(10)Q1Q2,whereQ1∈Ml×nR,Q2∈Mn-l×nR. Let A=P-1D1. Since Q-1∈SLn(R), by Laplace expansion, Q1 is ZLP. Since F=P-1(D1,0)Q-1, we have det(A)=det(P-1D1)=d1d2⋯dl. Hence F=A·Q1, as claimed by the theorem.Theorem 10.
With the same notation as in the proof of the above theorem, the maximal divisor of alli×i minors of A is d1⋯di for 1≤i≤l.Proof.
First, we take care of the1×1 minors of A, which is d1aij as A=P-1D1, where P-1=(aij). Assume that u is a common divisor of aij, uaij′=aij. Then(11)det⁡P-1=∑s=1naisAis=u⁡∑s=1nais′Ais′=1, where Ais is (l-1)×(l-1) minors of P-1 and uAis′=Ais. Then we can get that u is a unit of R. It follows that the maximal divisor of all 1×1 minors of A is d1.
Now leti≥2. Suppose that the result is correct for (i-1)×(i-1) minors. We investigate this result for i×i minors. Let C1,…,Ck be all the i×i minors and B1,…,Bm all the (i-1)×(i-1) submatrix of C1,…,Ck, where m=n!/(n-i+1)!(i-1)! and k=n!/(n-i)!(i)!. Then, by the Laplace expansion,(12)det⁡Cj=∑t=1idiat,iBjt. But the common divisor of aij is a unit of R, and the common divisor of B1,…,Bm is d1⋯di-1, so the common divisor of C1,…,Ck is d1⋯di. The theorem follows by induction on i.Besides, we can also make some improvements for the above theorem, which can be seen as the Serre problem generalized to elementary divisor rings.Theorem 11.
LetR be an EDR and F∈Ml×nR(l≤n) of full row rank. Then, for any maximal common divisor d of all l×l minors of F, there exist A∈Ml×l(R) and F1∈Ml×n(R) such that F=A·F1 with det(A)=d and F1 is ZLP.Proof.
Assumed and d′ are two maximal common divisors of all l×l minors of F. By Lemma 4, dR=d′R, which means there exist x,y∈R such that d=d′x and d′=dy. Note that Il(F)=0 as F is of full row rank. Then d and d′ are not zero-divisors. Also, any two maximal common divisors of all l×l minors of F are associates of each other; that is, there exists a unit α in R such that d=α·d′.
By Theorem9, there exist D2∈Ml×l(R) and A2∈Ml×n(R) such that F=D2·A2, where d1=det(A2) is a maximal common divisor of all l×l minors of A, and D2 is ZLP. Set A=D2·diag⁡{α,1,…,1}. Then F1=diag⁡α-1,1,…,1·A2. Thus the theorem is proved.Remark 12.
The above two theorems are different from each other, as in Theorem11  d is beforehand given, but in Theorem 9  d is an arbitrary one.
By now, we proved that Lin-Bose problem over an elementary divisor ring is correct. Next we deal with the Serre problem.Theorem 13.
LetR be an elementary divisor ring and F∈Ml×n(R) with l<n. Then F can be completed to a square matrix FG whose determinant is a maximal common divisor of all l×l minors of F. Furthermore, the (n-l)×n matrix G may be completed to a matrix in GLn(R).Proof.
From Theorem8, we have that PFQ=(D,0), where P∈SLl(R),Q∈SLn(R), D=diag⁡{d1,d2,…,dl}, and det⁡(D)=d1d2⋯dl. Set G=P-1(O(n-1)×1In-1)Q-1. Then we have(13)PFGQ=D01×n-1On-1×1In-1. This implies that(14)det⁡FG=det⁡D00In-l=det⁡D. Furthermore, 1 is a maximal common divisor of all (n-l)×(n-l) minors of G. From above argument, the (n-l)×n matrix G may be chosen to be itself completable to a matrix in GLn(R) (SLn(R)).In this theoremd is a particular maximal common divisor. When d is an arbitrary maximal common divisor, this theorem is also correct.Theorem 14.
LetR be an EDR, let F∈Ml×n(R) be of full row rank, and let d be any maximal divisor of all l×l minors of F. Then F can be completed to a square matrix FG whose determinant is d. Furthermore, the (n-l)×n matrix G may be chosen to be itself completable to matrix in GLn(R).Proof.
From Lemma4, any two maximal common divisors of all minors of F are associates. From Theorem 8, there exist P∈SLl(R) and Q∈SLn(R) such that PFQ=(D,0), where D=diag⁡{d1,d2,…,dl}; every di is a divisor of di+1, and 0∈Ml×(n-l)(R). By Lemma 7, det(D) is a maximal common divisor of all l×l minors of F. Assume d=ε·det(D); ε is a unit in R. Set Q¯=Q·diag⁡{ε,1,…,1}. Then PFQ¯=(D¯,0), where Q¯∈GLn(R) and det(D¯)=d. Setting G=P-1(0(n-l)×lIn-l)Q¯-1, we obtain the result.Theorem 15.
LetR be an EDR and let A,B∈Mn×n(R) be of full row rank. Assume det(AB)≠0, and (15)P1AQ1=D1=diag⁡d1,…,dn,P2BQ2=D2=diag⁡e1,…,en,P3ABQ3=D3=diag⁡f1,…,fn,where Pj,Qj∈GLn(R) for j=1,2,3. Then di∣fi and ei∣fi for all 1≤i≤n.Proof.
By Theorem11, there exist D∈Mn×n(R) and A1∈SLn(R) such that A=DA1. Then det(A)=det(D)=d1⋯dn. For B, we also have B=EB1, and det(B)=det(E)=e1⋯en, where E∈Mn×n(R) and B1∈SLn(R). It follows that AB=DA1EB1 and det(AB)=det(DE)=d1⋯dne1⋯en.
Now forAB, there exist F∈Mn×n(R) and H∈SLn(R) such that AB=FH. Then det(AB)=det⁡(F)=f1⋯fn. So d1⋯dne1⋯en=f1⋯fn. So di and ei all divide f1⋯fn for i=1,…,n.
We prove the theorem by induction onn. If n=1, it is obvious. Let i≥1. Suppose that the result is correct for n=i; we investigate this result for n=i+1. By the definition of EDR and the assumption, we may set (16)d2=d1x1,d3=d1x1x2,⋮dl=d1x1x2⋯xl-1,dl+1=d1x1x2⋯xl,f1=d1y1,f2=d1y1y2,⋮fl=d1y1y2⋯yl,fl+1=d1y1y2⋯yl+1, where xi,yi∈R. By the above, d1d2⋯dl+1∣f1f2⋯fl+1; it follows that(17)d1·d1x1·d1x1x2⋯dlx1x2⋯xl∣d1y1·d1y1y2⋯dly1y2⋯yl+1. Hence(18)x1·x1x2·x1x2⋯xl∣y1·y1y2⋯y1y2⋯yl+1. Since d2∣f2,d3∣f3,…,dl∣fl, we conclude that(19)x1∣y1y2,x1x2∣y1y2y3,⋮x1x2⋯xl-1∣y1y2⋯yl. So there exist q1,q2,…,ql-1 such that(20)x1q1=y1y2,x1x2q2=y1y2y3,⋮x1x2⋯xl-1ql-1=y1y2⋯yl. That is,(21)x1·x1x2·x1x2⋯xl∣y1·x1q1⋯x1x2⋯xl-1ql-1·y1y2⋯yl+1. Thus(22)x1x2⋯xl∣y1·q1q2⋯ql-1·y1y2⋯yl+1.
Now, assume thatdl+1†fl+1. Then x1x2⋯xl†y1y2⋯yl+1, and x1x2⋯xl∣y1·q1q2⋯ql-1. But(23)y1∣y1y2⋯yl+1,q1∣y1y2⋯yl+1,⋮ql-1∣y1y2⋯yl+1. Therefore, we have x1x2⋯xl∣y1y2⋯yl+1, contradicting our assumption. So dl+1∣fl+1, and our theorem is proved.Theorem 16.
LetR be an EDR and let F1,F2∈Ml×mR(l≤m) be of full row rank. Suppose F1=F2U, where U∈Mm×m(R) is MLP. Then F1 is MLP if and only if F2 is MLP.Proof.
Letd1 and d2 be maximal common divisors of all l×l minors of F1 and F2, respectively. Let Fk be any l×l submatrix of F1, and Fk=F2Uk, where Uk is a m×l submatrix of U. By Cauchy-Binet formula, we have det⁡(Fk)=∑a2iβi, where the sum is all a2i and βi, which are l×l minors of F2 and Uk, respectively. Since d2∣a2i for every i, we have d2∣det⁡(Fk). Because det⁡(Fk) is an arbitrary l×l minor of F1, we have d2∣d1. As U is MLP, from Lemma 7, there exist Vk∈Mm×r(R) such that UVk=δkIr, where δk are l×l minors of U. Then, from F1=F2U, we get that δkF2=F1Vk. By Cauchy-Binet formula, d1∣δkld2 for every k. But gcd⁡(δ1l,δ2l,…,δrl)=1 as U is MLP, so d1∣d2.
Therefore, ifF1 is MLP, then d1 is a unit and so is d2, which means that F2 is also MLP. By similar reasoning, when F2 is MLP, so is F1.Theorem 17.
LetR be an EDR and F∈Mm×m+1(R) is of full row rank. If F is ZLP, then there exists a ZRP matrix b0∈Mm×m-1(R) such that Fb0=0.Proof.
LetF=[Uv], and set P=U-1v∈Mm×1(R). There exist P1∈GLl(R) and Q1∈R such that P1PQ1=diag⁡(d1,0,…,0) as R is an EDR, where d1∈R. Then(24)P=P1-1diag⁡d1,0,…,0Q1-1. Set B=P1-1diag⁡(d1,0,…,0) and a=Q1. Then P=Ba-1; that is, Ba-1=U-1v, and va=U(U-1va)=U(Ba-1)a=UB. It follows that (25)Uv-Ba=0.Let b0=-Ba. Then b0∈Mm×m-1(R) and Fb0=0. Let b1,b2,…,bm be the (m-1)×(m-1) minors of F. Then there exist k∈R∖{0} such that bi=kci (1≤i≤m) as Ba-1=U-1v. Hence, if F is ZLP, then b0 is ZRP.


## 4. Conclusions

The main results in this paper can be summarized as follows: (a) the Serre problem and Lin-Bose problems were solved over an elementary divisor ring; (b) by using the properties of EDR, some interesting results about ZLP matrices are proved. These results could provide engineers with useful information for finding desired matrix decomposition.



---

*Source: 926046-2015-10-07.xml*