某些给定性质的符号模式矩阵其非零元数目的界

邢婷文

（广州民航职业技术学院，广东 广州 510403）

元素取自于集合{1，-1，0}的矩阵称为符号模式矩阵。设Rn×n表示所有n阶实矩阵的集合。设A∈Rn×n，以sign（A）记把实矩阵A的所有正元和负元分别替换为“1”和“-1”所得的符号模式矩阵。对于一个n阶符号模式矩阵S，记S的符号模式矩阵类为：Q(S)={A∈Rn×n:sign(A)=S}.

在过去的二十多年，有大量的研究关注于包括符号模式矩阵在内的矩阵特征问题［1］，其中包含了“要求”或“允许”给定性质的相关问题［2，3］。对于一个给定的性质φ，一个符号模式矩阵S称为“要求φ”，如果任意的A∈Q(S)均满足性质φ;而S称为“允许φ”，如果存在一个A∈Q(S)其满足性质φ（见文献［6］）。同时，关于各类矩阵（特别是非负矩阵）其非零元数目的界和极矩阵刻画问题一直备受关注（见［5］及其引文）。在近年来，越来越多的文献关注于要求（或允许）给定性质的符号模式矩阵其非零元的数目［3，4］。例如：确定“要求属于某个n阶谱任意符号模式矩阵类”的符号模式矩阵其非零元的最小数目（即著名的2n-猜想［4］）；寻找“允许属于某个n阶惯量任意符号模式矩阵类”的符号模式矩阵其非零元的最小数目等。

记Zn为所有非主对角线位置的元素均是非正的n阶实矩阵的集合。一个n阶实矩阵A称为N-矩阵，如果其所有主子式是负的；A称为P-矩阵，如果其所有主子式是正的;A称P0-为阵，如果其所有主子式是非负的；一个n阶矩阵A称为M-矩阵，如果A∈Zn且A是正稳定的（文章均假设M-矩阵是非奇异的）；一个n阶非奇异矩阵A称为逆M-矩阵，如果A-1是M-矩阵。分别把所有n阶N-矩阵，P-矩阵，P0-矩阵，M-矩阵和逆M-矩阵所成之集称为N-矩阵类，P-矩阵类，P0-矩阵类，M-矩阵类和逆M-矩阵类。

文章研究“要求（或允许）分别属于N-矩阵类，P-矩阵类，P0-矩阵类，M-矩阵类和逆M-矩阵类”的符号模式矩阵其非零元数目的上、下界和极矩阵刻画问题。

1 要求（或允许）给定性质的符号模式矩阵其非零元的数目

记一个符号模式矩阵S的非零元数目为σ(S).

1.1 要求（或允许）属于N-矩阵类

若一个（符号模式）方阵其非主对角线上的元素都是零，则称其为对角（符号模式）方阵。设D是一个主对角线上的元素均非零的对角（符号模式）方阵，称P和DPD是对角相似的，其中D和P是阶数相同的（符号模式）方阵。显然，DPD也是一个（符号模式）方阵。设

引理1.1［8］任一n阶N-矩阵必对角相似于一个N-矩阵A∈Sn.

定理1.2 设S是“允许属于N-矩阵类”的n阶符号模式矩阵，则σ(S)=n2，且S对角相似于sign(A)，其中A∈Sn.

证明 依定理条件，存在一个N-矩阵B∈Q(S)，根据引理1.1，B对角相似于一个N-矩阵A∈Sn，即存在对角方阵D使得A=DBD.从而，sign(A)=ESE，其中E=sign(D).故S对角相似于sign(A)，且由A∈Sn可导出σ(S)=n2.

设A是一个n阶（符号模式）矩阵，记选取A的若干行α及若干列β的子（符号模式）矩阵为A[α|β]，其中α,β⊆{1,…,n}.特别地，简记选取A的若干行α及对应列的主子（符号模式）矩阵A[α|α] 为A[α].

定理1.3 设S是“要求属于N-矩阵类”的1阶符号模式矩阵，则S=(- 1)且σ(S)=1.另外，不存在“要求属于N-矩阵类”的n阶符号模式矩阵，其中n≥2.

证明 若S是“要求属于N-矩阵类”的1阶符号模式矩阵，则S=(- 1)且σ(S)=1.显然成立。下面用反证法说明n≥2时的结论。不妨设存在一个“要求属于N-矩阵类的n阶符号模式矩队S=(sij)，其中n≥2.因为任何一个A=(aij)∈Q(S)都是N-矩阵，所以A的所有主子式都是负的，从而det(A[{i}])＜0，故sii=-1，其中i∈{1,…,n}.下面对主子符号模式矩阵S[{1,2}]分类讨论。

情形1s12=0或s21=0.对于任一A∈Q(S),det(A[{1，2} ]）=a11a12＞0，与A是N-矩阵矛盾。

1.2 要求（或允许）属于P-矩阵类

设R（nm）表示主对角线上的元素均是1，且恰有m个非零元在非主对角线的位置的n阶符号模式矩阵之集，其中0≤m≤n2-n.

定理1.4 设S是“允许属于P-矩阵类”的n阶符号模式矩阵，则n≤σ（S）≤n2，且σ(S)=k当且仅当S∈R（nk-n），其中k∈{n,n+1,…,n2}.

证明 因为存在一个P-矩阵A∈Q(S)，所以对于任意的α⊆{1,2,…,n}，det(A[α] )＞0。特别地，对i∈{1,…,n}均有det(A[{i} ] )＞0.从而∀i∈{1,…,n}，sii=1,故n≤σ(S)≤n2.

下面，证明σ(S)=k当且仅当S∈Rn(k-n)，其中k∈{n,n+1,…,n2}.

这亦说明了n≤σ(S)≤n2是最好的上、下界。

一方面，如果σ(S)=k，注意到sii=1(i∈{1,…,n})，故恰有k-n个非零元在非主对角线的位置，即S∈Rn(k-n).另一方面，若S∈Rn(k-n)，易见σ(S)=k，故只需验证S是“允许属于P-矩阵类”的n阶符号模式矩阵Bε=（bij）是一个n阶实矩阵，其中ε是一个正实数，

显然，Bε∈Q(S).那么，对于任意的α⊆{1,…,n}，de（tBε[α])=1+pα(ε)，其中pα(ε)是一个零多项式或关于ε的无常数项多项式。从而，取充分接近于0的正实数ε，使得pα(ε)趋向于0，故 det(Bε[α])＞0.因此Bε是一个P-矩阵。

定理1.5 设S是“要求属于P-矩阵类”的n阶符号模式矩阵，则σ(S)≥n，等号成立当且仅当S∈Rn(0).

证明 因为任意的A∈Q(S)都是P-矩阵，所以对i∈{i, …,n}均有det(A[{i}])＞0.从而sii=1(i∈{1,…,n})，故σ(S)≥n.

若σ(S)=n，易见S∈Rn(0).反之，如果S∈Rn(0)，则S是一个主对角线上元素均是1的对角符号模式矩阵，从而对于任意的A∈Q(S)，都有det(A[α])＞0，其中α⊆{1,…,n}.因此，S是“要求属于P-矩阵类”的n阶符号模式矩阵且σ(S)=n.

令Un=(uij)和分别为n阶的符号模式矩阵，其中

引理1.6 对于所有A∈)，均有 det(A)＞0.

证明 将用数学归纳法对阶数n归纳证明：det(An)＞0，其中An=(aij)∈).当n=1时，因为a11＞0，易见det(A1)=a11＞0.假设结论当n≤p-1时均成立，下面考虑n=p的情形，其中p≥2.通过在第一列处展开行列式det(Ap)，有

命题1.7 存在“要求属于P-矩阵类”的n阶符号模式矩阵S满足σ(S)=k，其中且n≥2.

对于k∈，记X(k)为把Un中位于的0元替换为-1所得的n阶符号模式矩阵，显然，，对于任意的矩阵A=(aij)∈Q(X(k))，任取{i1,…,it}⊆{1,2,…,n}(t=1,2,…,n)（不失一般性，假设＜ip+1＜it且P∈{0,1,…,t})，那么

注意到：A[{i1,…,ip}]∈Q(Un*)，故根据引理1.6可得：

又因为aii＞0(i∈ {1,…,n} )，所以det(A[{i1,…,it}])＞0，其中{i1,…,it}⊆{1,…,n}，综上可得：任意的A∈Q(X(k))均是P-矩阵，故存在“要求属于P-矩阵类”的n阶符号模式矩阵X(k)其满足σ(X(k))=k.

1.3 要求（或允许）属于P0-矩阵类

以On表示n阶零符号模式矩阵，即其所有元素都是0的符号模式矩阵。

定理1.8 设S是“允许属于P0-矩阵类”的n阶符号模式矩阵，0≤σ(S)≤n2，且第1个等号成立当且仅当S=On，第2个等号成立当且仅当S∈Rn(n2-n).

证明 显然，对于任意的n阶符号模式矩阵S均有O≤σ(S)≤n2，若σ(S)=0，则S=On;

反之，对于A∈Q(On)的所有主子式均为零，故On是“允许属于P0-矩阵类”的n阶符号模式矩阵。因此，σ(S)=0，当且仅当S=On.下面，将证明σ(S)=n2当且仅当S∈Rn(n2-n).

一方面，因为存在一个P0-矩阵A∈Q(S)，所以 ∀i∈{1,…,n}，det(A[{i}])≥0.若σ(S)=n2，则sii=1(∀i∈ {1,…,n}).注意到：σ(S)=n2，即恰有n2-n非零元位于非主对角线位置，从而S∈Rn{n2-n}.

另一方面，若S∈Rn{n2-n}，则σ(S)=n2，现只需验证S是“允许属于P0-矩阵类”的n阶符号模式矩阵。令Aε=(aij)是一个n阶实矩阵，其中

注意到：Aε∈Q(S)，且 det(Aε[α] )=1+Pα(ε)(∀α⊆{1,…,n})，其中Pα(ε)是一个关于ε的无常数项多项式。因此，取充分接近于0的正实数ε，使得Pα(ε)趋向于0，故 det(Aε[α])＞0.因此Aε是一个P0-矩阵。

命题1.9 存在“允许属于P0-矩阵类”的n阶符号模式矩阵S满足σ(S)=k，其中k∈{1 , 2,…,n2-1}.

证明 若k∈{1,2,…,n-1,n}，令为一个n阶符号模式矩阵，其中，而其余位置为0.显然σ(S(k))=k，且对于任意的A∈Q(S(k))其所有的主子式均是非负的。故S(k)是“要求属于P0-矩阵类”的，从而亦是“允许属于P0-矩阵类”的n阶符号模式矩阵。

若k∈{n+1,n+2,…,n2-1}，根据定理1.4，S∈R（nk-n）是“允许属于P-矩阵类”的，自然也是“允许属于P0-矩阵类”的n阶符号模式矩阵。

定理1.10 设S是“要求属于P0-矩阵类”的n阶符号模式矩阵，则σ(S)≥0，且等号成立当且仅当

S=On.另外，存在“要求属于P0-矩阵类”的n阶符号模式矩阵S满足σ(S)=k，其中

证明 显然，σ(S)≥0.若σ(S)=0，则S=On另一方面，任意的A∈Q(On)其所有主子式都为零，因此On是“要求属于P0-矩阵类”的n阶符号模式矩阵且σ(On)=0.故σ(S)=0当且仅当S=On.

当k∈{1,2,…,n-1,n} 时，令Sk=()为一个n阶符号模式矩阵，其中=…==1，而其余位置为0.由命题1.9的证明过程知：S(k)是“要求属于P0-矩阵类”的n阶符号模式矩阵。

足σ(S)=k，从而S亦是“要求属于P0-矩阵类”的n阶符号模式矩阵。

注1.11 根据命题1.7和定理1.10，猜想:

其中S是“要求属于P-矩阵类（或P0-矩阵类）”的n阶符号模式矩阵。

下面，证明上述猜想当n=1，2，3时是正确的。

定理1.12 设S=(sij)是“要求属于P-矩阵类（或P0-矩阵类）”的n阶符号模式矩阵，其中n=1，2，3.则

证明 当n=1或2时，显然，

当n=3时，用反证法，假设，从而sij=1或-1(∀i，j∈{1,2,3}).

断言1sij=1(i=1,2,3).因为S=(sij)是“要求属于P-矩阵类（或P0-矩阵类）”的n阶符号模式矩阵，所以对于任意的A∈Q(S)及i∈{1，2，3}，det(A[{i}])＞0（或det(A[{i}])≥0），故结合条件σ(S)=9可得：sii=1.

断言2sij=-s（ji∀i≠j）用反证法，不失一般性，假设s12=s21.结合断言1可知：

S[{1,2}]显然A∈Q(S).容易计算得：det(A[{1,2}])=-1＜0，其与A∈Q(S)是一个P-矩阵（或P0-矩阵）矛盾。

令易见A∈Q(S).直接计算可得：det(A)=-77＜0，与A∈Q(S)是一个P-矩阵（或）P0-矩阵）矛盾。

1.4 要求（或允许）属于M-矩阵类

引理1.13［6］A∈是一个M-矩阵当且仅当A是一个P-矩阵。

以Nn(m)表示主对角线上元素均是1，且恰有m个负元位于非主对角线位置的n阶符号模式矩阵之集，其中0≤m≤n2-n.

定理1.14 设S是“允许属于M-矩阵类”的n阶符号模式矩阵，则n≤σ(S)≤n2.另外，σ(S)=k当且仅当S∈Nn(k-n)，其中k∈{n,n+1…,n2}.

证明 因为存在一个M-矩阵A∈Q(S)，结合引理1.13可得：A∈Zn且A是一个P-矩阵。根据定理1.4的证明过程可得：sii=1(∀i∈{1,…,n} ).又由于A∈Zn，故sij=0或-1，其中i,j∈{1,…,n} 且i≠j，因此，n≤σ(S)≤n2.

若σ(S)=k，注意到：∀i∈{1,…,n}，sii=1，故恰有k-n个负元位于非主对角线位置，即S∈Nn(k-n)，其中k∈{n,n+1,…,n2}.

反之，若S∈Nn(k-n)，显然σ(S)=k，现只需证明S是“允许属于M-矩阵类”的n阶符号模式矩阵。令Bε=(bij)是一个n阶实矩阵，其中

注意到：Bε∈Q(S)且扎Bε∈Zn.类似于定理1.4的证明，可证得对于充分接近于0的常数ε，Bε是一个P-矩阵。再结合引理1.13，可得：Bε∈Q(S)是一个M-矩阵。故S是“允许属于M-矩阵类”的n阶符号模式矩阵。

定理1.15 设S是“要求属于M-矩阵类”的n阶符号模式矩阵，则σ(S)≥n，等号成立当且仅当S∈Nn(0).

证明 因为每一个实矩阵A∈Q(S)均是M-矩阵，所以根据引理1.13知：A∈Zn且A是一个P-矩阵。从而∀i∈{1,2,…,n}，det(A[{i} ] )=aii＞0，这便导出了sii=1.因此σ(S)≥n.

若σ(S)=n，则S∈Nn(0).反之，若S∈Nn(0)，则对于任意的A∈Q(S)，有 det(A[α] ) ＞0，且A∈Zn，其中α⊆{1,…,n}.因此S是“要求属于M-矩阵类”的n阶符号模式矩阵且σ(S)=n.

令V=(vij)一个n阶符号模式矩阵，其中

命题1.16 存在“要求属于M-矩阵类”的n阶符号模式矩阵S满足σ(S)=k，其中

定理1.17 设S是“要求属于M-矩阵类”的n阶符号模式矩阵，则

证明 用反证法，假设S是“要求属于M-矩阵类”的n阶符号模式矩阵但

由定理1.15的证明过程可知：sii=1且sij=0或-1，其中i，j∈{1,…,n} 且i≠j.因为，所以至少存在一对元素skl=slk=-1，其中k≠l.考察子符号模式矩阵S，令A∈Q(S)满足.直接计算得：det(A[{k，l} ] )=-3＜0，与A∈Q(S)是一个M-矩阵矛盾。定理得证。

1.5 要求（或允许）属于逆M-矩阵类

一个n阶实矩阵A称为可约的，如果n≥2且存在某个n阶置换矩阵P使得:，其中B和D都是方阵；如果n=1且A=(0).否则，称A为不可约的。一个n阶符号模式矩阵S称为可约（或不可约）的，如果所有的矩阵A∈Q(S)都是可约（或不可约）的。

引理1.18［9］设S=(sij)是一个n阶符号模式矩阵，且其Frobenius标准型为:

其中S11,S22，…,Skk，分别是q1,q2,…,qk阶的不可约符号模式矩阵。若存在一个逆M-矩阵A∈Q(S)，则S11，S22，…，Skk都是全正符号模式矩阵（即其所有的元素都是1），且Sij(i≠j)是全正或零符号模式矩阵。反之，若Sij(j≥i)都是全正符号模式矩阵，则存在一个逆M-矩阵A∈Q(S).

记n阶单位矩阵为In，而n阶全正矩阵为Jn.

引理1.19［9］给定实数 0＜a＜1，则n阶实矩阵Cnα=(1-α)In+αJn是一个逆M-矩阵。

定理1.20 设S是“允许属于逆M-矩阵类”的n阶符号模式矩阵，且其Frobenius标准型如式（1）所示，则

上式第1个等号成立当且仅当Sii(1≤i≤k)均是全正符号模式矩阵，且Sij(1≤i＜j≤k)都是零符号模式矩阵，上式第2个等号成立当且仅当Sij(1≤i≤j≤k)都是全正符号模式矩阵。

证明 若S是“允许属于逆M-矩阵类”的n阶符号模式矩阵，根据引理1.18，S11，S22，…，Skk都是全正符号模式矩阵，且Sij(i≠j)是全正或零符号模式矩阵。于是，有.另外，易见上式第1个和第2个等号成立的必要性是显然的。

对于上式第1个等号的充分性，若Sii(1≤i≤k)均是全正符号模式矩阵，且Sij(1≤i＜j≤k)都是零符号模式矩阵，则只需证明S是“允许属于逆M-矩阵类”的n阶符号模式矩阵。令

其中0＜α＜1.显然，C∈Q(S)，结合引理1.19不难证得：C是一个逆M-矩阵。

对于上式第2个等号的充分性，若Sij(1≤i≤j≤k)都是全正符号模式矩阵，容易计算又根据引理1.18，必存在一个逆M-矩阵A∈Q(S)，即S是“允许属于逆M-矩阵类”的n阶符号模式矩阵。

定理1.21 设S是“要求属于逆M-矩阵类”的n阶符号模式矩阵，贝σ(S)≥n，且上式的等号是可达的。

证明 如果S是“要求属于逆M-矩阵类”的n阶符号模式矩阵，那么任意的A∈Q(S)均是非奇异的，故A至少含有n个非零元，从而σ(S)≥n.考察n阶符号模式矩阵sign(In)，易见σ(s i gn(In))=n.下证 sign(In)是“要求属于逆M-矩阵类”的n阶符号模式矩阵。对于任意的A=(aij)∈Q(sign(In))，不难发现：

因为＞0(i=1,2,…,n)且A，A-1∈Zn，所以A-1是一个P-矩阵，从而也是一个M-矩阵，故任意的A∈Q(sign(In))是一个逆M-矩阵。

参考文献：

［1］C.R.Johnson，Combinatorial matrix analysis:an overview［J］.Linear Algebra Appl.1988，（107）：3-15.

［2］M.Catral，D.D.Olesky，P.van den Driessche，Allow problems concerning spectral properties of sign pattern matrices:A survey［J］.Linear Algebra Appl.2009，（430）：3080-3094.

［3］C.Mendes Araiijo，J.R.Torregrosa，Sign pattern matrices that admit M-，N-，P-or inverse M-matrices［J］.Linear Algebra Appl.2009，（431）：724-731.

［4］T.Britz，J.J.McDonald，D.D.Olesky，P.van den Driessche，Minimal spectrally arbitrary sign patterns，SIAM［J］.Matrix Anal.Appl.2004，（26）：257-271.

［5］M.Fang，A.Wang，Possible numbers of positive entries of imprimitive nonnegative matrices［J］.Linear and Multilinear Algebra 2007，（55）：399-404.

［6］A.Berman，R.J.Plemmons，Nonnegative Matrices（非负矩阵）in the Mathematical Sciences［M］.SIAM，1994.

［7］M.Lewin，M.Neumann，On the inverse M-matrix problem for（0，1）-matrices［J］.Linear Algebra Appl.1980，（30）：41-50.

［8］C.Mendes Araujo，J.R.Torregrosa，A.M.Urbano，N-matrix completion problem［J］.Linear Algebra Appl.2003，（372）：111-125.

［9］方保镕，等，矩阵论［M］.北京：清华大学出版社，2013.