# On Serre Reduction of Multidimensional Systems

Authors: Dongmei Li; Jinwang Liu; Licui Zheng
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Serre reduction of a system plays a key role in the theory of Multidimensional systems, which has a close connection with Serre reduction of polynomial matrices. In this paper, we investigate the Serre reduction problem for two kinds ofnD polynomial matrices. Some new necessary and sufficient conditions about reducing these matrices to their Smith normal forms are obtained. These conditions can be easily checked by existing Gröbner basis algorithms of polynomial ideals.


---

## Body

## 1. Introduction

Multidimensional (nD) systems arise naturally in several fields of control, circuits, signals, and network synthesis (see [1–5]). Serre reduction problem aims at simplifying nD systems to some equivalent forms with fewer equations in fewer unknowns, and rewriting these systems such that the key information on them [6], which does not show obviously in the original forms, can be derived from the new equivalent forms more easily. In general, this involves Serre reduction of multivariate (nD) polynomial matrices to some simple equivalent forms, especially their Smith normal forms. Serre reduction can help to investigate the structural of nD polynomial matrices, which has wide applications in image, complex networked system, and other areas (see [6–11]).In the theory ofnD systems, the Serre reduction for a polynomial matrix to its Smith normal form plays a critical role. It preserves relevant system properties from the system theory point of view. The reduced matrix has good properties and corresponds to a system which consists of much less equations in unknowns than its original form. For single variable polynomial matrices, the problem for reducing the matrix to its Smith normal form has been well solved. Frost and Storey presented an example for 2D polynomial matrices which cannot be reduced to its Smith normal form [12]. For nD n≥2 case, since this reduction problem is equivalent to a highly difficult problem, the isomorphism of two finitely presented modules, the criteria determining whether arbitrary nD polynomial matrix can be Serre reduced to its Smith normal form has not been presented so far. The reduction for several special classes of polynomial matrices to their Smith normal forms has been investigated. For the polynomial ring Kx1,x2, Lee and Zak [13] presented a necessary condition for a class of 2D polynomial matrices on reducing them to the Smith normal forms. Lin et al. [14] proposed a sufficient and necessary condition, the existence of a special polynomial vector, under which a kind of nD polynomial matrices can be reduced to the Smith normal forms. Lin et al. [14] generalized this result to the case when Kx1,x2,…,xn, n≥3. Furthermore, they showed that a class of l×lnD polynomial matrices P can be reduced to its Smith normal form diag Il−1,d for det P=x1−fx2,…,xn≜d. Boudellioua [15] gave some similar conditions using module theoretic approach. Li et al. [16] proposed a sufficient and necessary condition under which P can be reduced to its Smith normal form diag Il−1,dq for P∈Kl×lx1,x2,…,xn and det P=dq, d=x1−fx2,…,xn.The results that we mentioned above mainly study polynomial matrices whose reduced matrices correspond to systems which contains only one equation in one unknown with form diagIl−1,detFz, where Fz is the polynomial matrix corresponds to the given nD system. In practical applications, the reduced matrix corresponds to a given system which is a more general form with more than one equation in unknowns, such as, diag Ir,dIl−r. In this paper, we will investigate these systems and the reduced matrices. The following questions are considered.Problem 1.
LetFz∈Kl×lz and detFz=dr=z1−fz2,…,znr, where r is a positive integer. When is Fz reduced to its Smith normal form diag Il−r,dIr?Problem 2.
LetFz∈Kl×mzl≤m has full rank and drF=dq=z1−fz2,…,znq, where drF is the greatest common divisor (g.c.d.) of all the r×r minors of Fz and q is a positive integer. Is there a tractable criterion for Fz to be reduced to its Smith normal form?
This paper is organized as follows. We present some basic preliminary knowledge and main results for reducing several kinds of matrices to their Smith normal forms in Section2. An example is established to illustrate our results and the constructive computational method in Section 3.


## 2. Preliminaries and Results

In the following,Kz=Kz1,…,zn denotes the polynomial ring in n variables z1,…,zn with coefficients in the field K, K¯ denotes the algebraic closed field of K, Kl×mz denotes the set of l×m matrices with entries in Kz, 0r×t denotes the r×t zero matrix, and Ir denotes the r×r identity matrix. The argument (z) is omitted whenever its omission does not cause confusion, for example, we denote Fz by F for simplicity.ForFz∈Kl×mz, we use diF to denote the greatest common divisor of all the i×ii=1,…,l minors of Fz.Definition 1 (see [17]).
SupposeFz∈Kl×mz be of full row (column) rank, we say Fz is zero left prime (zero right prime) if all the l×lm×m minors of Fz have no common zero or generate the unit ideal Kz.
IfFz is a zero left prime (zero right prime) matrix, we simply say that Fz is ZLP (ZRP). By Quillen–Suslin theorem [18], we see that Fz is ZLP iff there exists an m×m invertible matrix Nz∈Kz such that Fz⋅Nz=El0l×m−l. Quillen–Suslin theorem states that finite generated projective Kz-modulo is free, and it is equivalent to saying that any ZLP (ZRP) matrix on Kz can be completed to an invertible (unimodular) square matrix.Definition 2 (see [17]).
LetFz∈Kl×mz, l≤m, the Smith normal form of Fz is defined as(1)S=diagΦi0l×m−l,where(2)Φi=didi−1,1≤i≤r,0,r<i≤m,r is the rank of Fz, d0≡1, di is the g.c.d. of the i×i minors of F, and Φi satisfies the divisibility property:(3)Φ1Φ2…Φr.Definition 3 (see [17]).
LetT1z and T2z be two matrices in Kl×mz, then T1z and T2z are said to be equivalent (or T1z can be reduced to T2z if there exist two invertible (unimodular) matrices Mz and Nz such that T2z=Mz⋅T1z⋅Nz).
First, we give the following several well-known results about the factorization ofnD polynomial matrices [10, 17, 19, 20].Lemma 1 (see Hilbert zeros Theorem [17, 20]).
Supposef1z,f2z,…,fsz∈Kz, then f1z, f2z,…,fsz have no common zero in K¯n if and only if the ideal generated by f1z,f2z,…,fsz is the unit ideal Kz.Lemma 2 (see [19]).
SupposeFz∈Kl×mz is of full column rank and the reduced minors of Fz generate Kz, then Fz admits a zero prime factorization Fz=F0z·G0z with F0z∈Kl×mz, G0z∈Km×mz, and detG0z=dmF, and F0z is a ZRP matrix.Remark 1.
SupposeFz∈Kl×mz has full row rank and the l×l reduced minors of Fz generate Kz, then Fz admits the factorization as Fz=G0z·F0z with G0z∈Kzl×l, F0z∈Kl×mz, and det G0z=dlF. Hence, F0z is a ZLP matrix.Lemma 3 (see [17, 20]).
SupposeFz∈Kl×mz has normal rank r, if the r×r reduced minors of F generate Kz, then there exists a ZLP matrix Hz∈Kl−r×lz such that HzFz=0l−r×m.Lemma 4 (see [17]).
Letgz∈Kz=Kz1,z2,…,zn and fz∈Kz2,…,zn. Suppose that gf,z2,…,zn=0, then z1−fz2,…,zn is a divisor of gz.In what follows, for a polynomial matrixFz, we use Fi1i2…isj1j2…jt to denote an s×t submatrix of Fz constituted by the i1,…,is rows and j1,…,jt columns of Fz.Lemma 5.
SupposeFz=F1zF2z with Fz,F1z,F2z∈Kl×mz. If all the k×k minors of Fz have no common zero, for some k k≤l, then all the k×k minors of Fiz i=1,2 have no common zero.Proof.
For anyk≤l, since(4)Fi1i2…ikj1j2,…jk=F1i1i2…ik12…l⋅F212…lj1j2…jk,according to Cauchy–Binet formula, we obtain(5)detFi1i2…ikj1j2…jk=∑gi⋅hi,where gi and hi are k×k minors of F1z and F2z, respectively. Suppose that all the k×k minors of Fiz have a common zero point a0. So, the k×k minors of Fz have a common zero point a0. This contradicts the assumption. Therefore, all the k×k minors of Fiz i=1,2 have no common zero.Lemma 6.
SupposeAz,Bz∈Kl×mz and Az can be reduced to Bz, then dkA=dkB for k=1,2,…,α, α=minl,m.Proof.
SinceA can be reduced to B, by Definition 3, there are invertible matrices U and V such that A=UBV. Setting C=UB, according to Cauchy–Binet formula, we have that(6)detCi1i2…ikj1j2…jk=Σfigj,where fi is a k×k minors of U, gj is a k×k minors of B, and so dkBdkC. Note that B=U−1C, similar to the procedure above, we have that dkCdkB. Hence, dkC=dkB.
In the following, we denotez1−fz2,…,zn by d and dlFz by dF simply. We can obtain the following result, which gives a positive answer to Problem 1.Theorem 1.
SupposeFz∈Kl×lz has a full row rank and det Fz=dr, where d=z1−fz2,…,zn, r is a positive integer. If all the l−r×l−r minors of Fz have no common zero and ddl−r+1F, then Fz can be reduced to its Smith form:(7)Dz=1⋱1d⋱d,with det Dz=dr.Proof.
We first prove that rankFfz2,…,zn,z2,…,zn is l−r. Since ddl−r+1F, it follows that rank Ffz2,…,zn,z2,…,zn≤l−r. Because l−r×l−r minors of Fz have no common zero, then d∤drF. Combined with Lemma 5, we obtain that drFfz2,…,zn,z2,…,zn≠0, and rank Ffz2,…,zn,z2,…,zn=l−r. Let b1z1,z2,…,zn,…,bqz1,z2,…,zn, c1z2,…,zn,…,cqz2,…,zn be the l−r×l−r minors of Fz1,z2,…,zn and Ffz2,…,zn,z2,…,zn, respectively. It is straightforward that ciz2,…,zn is a divisor of bif,z2,…,zni=1,…,q. Since b1z,…,bqz have no common zero, then b1fz2,…,zn,z2,…,zn,…, bqfz2,…,zn,z2,…,zn also have no common zero. So, c1z2,…,zn, …,cqz2,…,zn also have no common zero, i.e., the l−r×l−r minors of Ffz2,…,zn,z2,…,zn have no common zero.
We then show thatFz can be reduced to its Smith normal form. According to Lemma 3, there exists a ZLP polynomial matrix H∈Kr×lz which satisfies H·Ff,z2,…,zn=0r×m. By Quillen–Suslin Theorem, we can complete H into an l×l unimodular matrix Vz2,…,zn, that is, H is the last r rows of Vz2,…,zn. We have that the last r rows of the matrix V⋅Ff,z2,…,zn are the zero polynomials. According to Lemma 4, there is the common divisor d in the last r rows of V⋅Fz1,z2,…,zn, i.e.,(8)V⋅F=1⋱1d⋱dg11…g1l⋮⋱⋮gr1…grlgr+11…gr+1l⋮⋱⋮gl1…gll,where gij∈Kz. Setting Dz=diag1,…,1,d,…,d, then det Dz=dr. Combining with d∤dl−rF, ddl−r+1F, and det Fz=dr, we obtain that the Smith normal form of Fz is Dz. Let(9)G=g11…g1l⋮⋱⋮gr1…grmgr+11…gr+1l⋮⋱⋮gl1…gll,Then, det G=1 and F=V−1DG. Note that UandG are unimodular matrices, so Fz can be reduced to its Smith normal form Dz.
Denote(10)Dz=Il−rdIr.
In order to investigate Problem2, we consider the following simple case first.Theorem 2.
SupposeFz∈Kl×mz l≤m has full row rank with dlF=dr, where r is a positive integer. If all the l−r×l−r minors of Fz have no common zero and ddl−r+1F, then Fz can be reduced to its Smith normal form.Proof.
Since all thel−r×l−r minors of Fz have no common zero, by Lemma 1, then all the l−r×l−r minors of Fz generate Kz. Combined with ddr+1F, we have that the Smith normal form of Fz is the matrix:(11)Pz=Dz0l×m−l.
According to Remark1, there exist G0z∈Kl×lz with detG0z=dr, F0z∈Kl×m such that Fz=G0z·F0z, and F0z is ZLP. Combining with Lemma 5, we have that the l−r×l−r minors of G0z have no common zero and ddl−r+1G0. From Theorem 1, there exist two l×l unimodular polynomial matrices UzandVz which satisfy G0z=Uz⋅Dz⋅Vz. It is straightforward that Vz⋅F0z is also ZLP. According to Quillen–Suslin theorem, there is an invertible matrix Qz∈Km×mz such that Vz⋅F0z⋅Qz=Il0l×m−l. Hence,(12)Fz⋅Qz=G0z⋅F0z⋅Qz=Uz⋅Dz⋅Vz⋅F0z⋅Qz=Uz⋅Dz⋅Il0l×m−l=Uz⋅Pz.
Thus,Fz can be reduced to its Smith normal form Pz.Lemma 7.
SupposeVz∈Kl×lz2,…,zn is a unimodular matrix. If all the l−r×l−r minors of Dsz⋅Vz⋅Dz have no common zero, then the matrix Dsz⋅Vz⋅Dz can be reduced to the matrix Ds+1z.Proof.
SettingFz=Dsz⋅Vz⋅Dz and(13)V1=P1P2P3P4,where P1∈Kl−r×l−rz2,…,zn, P2∈Kl−r×rz2,…,zn, P3∈Kr×l−rz2,…,zn, and P4∈Kr×rz2,…,zn, we obtain that(14)Fz=Il−rdsIrP1P2P3P4Il−rdIr.
Note thatP1 is ZLP (since Uz an invertible matrix), and according to Quillen–Suslin theorem, there exists an invertible matrix Q11∈Kl−r×l−rz2,…,zn such that P1⋅Q11=Il−r. Setting(15)Q1≜Q11Ir,P3⋅Q11≜P31,we partition P2 and P31 as(16)P2=α1⋮αm,P31=β1…βm,where α1,…,αm∈K1×rz2,…,zn and β1,…,βm∈Kr×1z2,…,zn.
We obtain that(17)Fz=Il−rdsIr⋅P1dP2P3dP4⋅Q1⋅Q1−1=Il−rdsIr⋅P1dP2P3dP4⋅Q11Ir⋅Q1−1=Il−rdsIr⋅Il−rdP2P31dP4⋅Q1−1=1⋱1dα1…dαl−rdsβ1…dsβl−rds+1P4⋅Q1−1.
Setting(18)Q2=1⋱10l−r×r−dsβ1…−dsβl−rIr,Q3=1⋱1−dα1⋮−dαl−r0l−m×l−rIr,we have that(19)Q2⋅Fz=1⋱1dα1…dαl−r0r×l−rds+1P4⋅Q3⋅Q3−1⋅Q1−1=Il−rds+1P4⋅Q3−1⋅Q1−1.
SinceP4 is ZLP, according to Quillen–Suslin theorem, there exists an invertible matrix Q51∈Kr×rz2,…,zn such that P4⋅Q51=Ir. Setting(20)Q5≜Il−rQ51,we see that(21)Fz=Q2−1Il−rds+1P4Il−rQ51Q5−1Q3−1Q1−1=Q2−1⋅Il−rds+1IrQ5−1Q3−1Q1−1.
Obviously,Q2−1 and Q5−1Q3−1Q1−1 are invertible. So, Fz can be reduced to(22)Ds+1z≜Il−rds+1Ir.Theorem 3.
SupposeFz∈Kl×lz with det Fz=dq. If all the l−r×l−r minors of Fz have no common zero and dq/rdl−r+1F, where q,q/r are positive integers. Then, Fz can be reduced to its Smith normal form:(23)Dq/rz=Il−rdq/rIr.Proof.
Whenq/r=1, by Theorem 1, the conclusion is correct.
Whenq/r≥2, since ddl−r+1F, it follows that rank Ffz2,…,zn,z2,…,zn≤l−r. All the l−r×l−r minors of Fz have no common zero, and doing the same as that of the proof of Theorem 1, we obtain that rank Ffz2,…,zn,z2,…,zn=l−r and(24)V1z⋅Fz=Il−r0l−r,r0r,l−rdIr⋅F1z,where V1z∈Kl×lz is a unimodular matrix and F1z∈Kl×lz. Hence,(25)Fz=V1−1z⋅Dz⋅F1z.
We know thatdetF1z=dq−rz from the equation above. According to Lemma 5, all the l−r×l−r minors of F1z have also no common zero. If q/r≥2, combined with r is a positive integer, then q−r≥2; imitating the procedure above, we obtain that(26)F1z=V2−1z⋅Dz⋅F2z.
Then,(27)Fz=V1−1⋅Dz⋅V2−1z⋅Dz⋅F2z.
Using Lemma5 again, all the l−r×l−r minors of Dz⋅V2−1z⋅Dz also have no common zero. Combined with Lemma 7, two invertible matrices N1z,U1z∈Kl×lz exist and satisfy Dz⋅V2−1z⋅Dz=N1z⋅D2z⋅U1z. Therefore,(28)Fz=V1−1⋅N1z⋅D2z⋅U1z⋅F2z.
Note thatdetFz=dq and detD2z=d2r, then detU1z⋅F2z=dq−2r. Furthermore, from Lemma 5, we see that the l−r×l−r minors of U1z⋅F2z also have no common zero.
Ifq/r≥3, repeating the previous process, we obtain that(29)Fz=V1−1z⋅N1z…Nq/r−1z⋅Dq/rz⋅Uq/r−1z⋅Fq/rz.
Note thatdetFz=dq and detDq/rz=dq, we see detUq/r−1z⋅Fq/rz=1. Hence, V1−1z⋅N1z…Nq/r−1z and Uq/r−1z⋅Fq/rz are invertible matrices. So, Fz can be reduced to its Smith normal form Dq/rz.Theorem 4.
SupposeFz∈Kl×mz (l≤m) has full row rank with dlF=dq and dq/rdl−r+1F, where q and q/r are positive integers. Then, Fz can be reduced to its Smith normal form if and only if all the l−r×l−r minors of Fz have no common zero.Proof (sufficiency).
Since all thel−r×l−r minors of Fz have no common zero and dq/rdl−r+1F, then the Smith normal form of Fz is(30)Pz=Dq/rz0l×m−l.
According to Remark1, there exist G0z∈Kl×lz with detG0z=dr, F0z∈Kl×m satisfy Fz=G0z⋅F0z, and F0z is ZLP. Combining with Lemma 5, we have that the l−r×l−r minors of G0z have no common zero and ddl−r+1G0. From Theorem 3, there are invertible matrices Uz,Vz∈Kl×lz which satisfy G0z=Vz⋅Dq/rz⋅Uz. It is straightforward that Uz⋅F0z is also a ZLP matrix. From Quillen–Suslin theorem, we have that there is an invertible matrix Qz∈Km×mz which satisfy Uz⋅F0z⋅Qz=Il0l×m−l. Hence,(31)Fz⋅Qz=G0z⋅F0z⋅Qz=Vz⋅Dq/rz⋅Uz⋅F0z⋅Qz=Vz⋅Dq/rz⋅Il0l×m−l=Uz⋅Pz.
So,Fz can be reduced to its Smith normal form Pz.Necessity.
AssumePz is the Smith normal form of Fz. It is obvious that all the l−r×l−r minors of Pz have no common zero and dq/rdl−r+1P. Since Fz can be reduced to Pz, by Lemmas 5 and 6, we have that all the l−r×l−r minors of Fz have no common zero and dq/rdl−r+1F.Remark 2.
Letf1z,…,fsz be some nonzero polynomials in Kz; by Lemma 1, we know a necessary and sufficient condition of f1z,f2z,…,fsz have no common zero. Kz is the reduced Gröbner basis of the ideal I, which is generated by f1z,…,fsz, and contains a unit of K. By Theorems 1–4, we can check whether such a kind of nD polynomial matrices can be reduced to its Smith normal form by using the existing Gröbner basis algorithms. So, the conditions of Theorems 1–4 can be verified easily.


## 3. An Example

In this section, we present an example to explain our method on how to reduce the polynomial matrix we considered to its Smith normal form.Example 1.
We consider the following3D polynomial matrix:(32)Fz=1+z31−z32−z3z1z3−z22−z12+2z1z22+z24z3z12z3−2z1z22z3−z24z32+z24z1z24z3−2z1z24+z12z22−2z12+4z1z22−2z242z12z3−4z1z22z3+2z24z3z12−2z12z24−2z1z24−2z1z22+2z26+z24,with detFz=z1−z224. Then, we will prove that Fz can be reduced to its Smith normal form.Step 1.
By computing,d2F=z1−z222 and the reduced Gröbner basis of the ideal, which is generated by the 1×1 minors of Fz, is 1. Combined with Remark 2 and Lemma 1, we have that the 1×1 minors of Fz have no common zero. Let d=z1−z22, and then according to Theorem 3, we have that Fz is can be reduced to its Smith normal form:(33)Pz=1d2d2,where d=z1−z22.Step 2.
Substitutingfz2,z3=z22 for z1 in Fz, we have(34)Fz22,z2,z3=1+z31−z32−z3z22z3−z22z24+z24z3z24−z24z32−z24z3z26z3−z26000.
Then, we construct the following invertible matrix:(35)U1z2,z3=100−z2410001,such that(36)U1z2,z3⋅Fz22,z2,z3=1+z31−z3−z32z22z3−z22000000.
Computing by singular,(37)U1z2,z3⋅Fz1,z2,z3=1dd⋅1+z31−z3−z32z1z3−z22−z1+z22z1z3−z22z3z1z22−z24−2z1+2z222z1z3−2z22z3z1+2z1z22−2z24−z22.Step 3.
Suppose(38)F1=1+z31−z3−z32z1z3−z22−z1+z22z1z3−z22z3z1z22−z24−2z1+2z222z1z3−2z22z3z1+2z1z22−2z24−z22,repeating Step 2 to F1, we have(39)U2=1000100−21.
Hence,(40)U2⋅F1=1dd⋅1+z31−z3−z32z1z3−z22−1z3z22001.Step 4.
Let(41)F2=1+z31−z32−z3z1z3−z22−1z3z22001,we check easily that F2 is an invertible matrix.Step 5.
By Lemma7, we obtain(42)1dd⋅U2−1⋅1dd=U2−1⋅U2⋅1dd⋅U2−1⋅1dd=U2−1⋅1000100−21⋅1dd⋅100010021⋅1dd=U2−1⋅1000d00−2dd⋅100010021⋅1dd=U2−1⋅1d2d2.
Hence,(43)Fz=U1−1⋅1dd⋅F1=U1−11dd⋅U2−1⋅F2=U1−1⋅U2−1⋅1d2d2⋅F2.
Thus,(44)Fz=Uz⋅1d2d2⋅Vz,where Uz=U1−1⋅U2−1 and Vz=F2 are invertible matrices.


## 4. Conclusions

In this paper, we have investigated the Serre reduction problem for two classes of multivariate polynomial matricesFz with the g.c.d. of maximal order minors as z1−fz2,…,znq. We have obtained some tractable sufficient and necessary conditions under which such kinds of matrices can be reduced to their Smith forms. These conditions can be checked by using the existing Gröbner basis algorithms to the associated minors of the given matrix. We also give an example to illustrate our method. All of these could provide useful information for reducing nD systems.



---

*Source: 7435237-2020-04-11.xml*