一個(gè)含有兩個(gè)1-separation符號模式矩陣的最小秩*

龍佳平，邵燕靈

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

?

一個(gè)含有兩個(gè)1-separation符號模式矩陣的最小秩*

龍佳平，邵燕靈

(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)

摘要:一個(gè)符號模式矩陣的最小秩指該符號模式矩陣定性類中實(shí)矩陣秩的最小值. 對于一個(gè)含有兩個(gè)1-separation的符號模式矩陣，利用矩陣秩的性質(zhì)，采用證明不等式的方法，給出了該符號模式矩陣最小秩的計(jì)算公式.

關(guān)鍵詞:符號模式矩陣； 最小秩； 1-separation

0引言

一個(gè)符號模式矩陣(簡稱符號模式)是一個(gè)元素取自{+,-,0}的矩陣. 對于任意給定的實(shí)矩陣B=[bi,j]，B的符號模式是指一個(gè)以B中對應(yīng)元素bi,j的符號為元素的矩陣，記為sgn(B). 一個(gè)m×n 符號模式A的定性類Q(A)，是所有滿足sgn(B)=A的實(shí)矩陣B∈Rm×n的集合. 一個(gè)符號模式A的最小秩為mr(A)=min{rank(B)∶B∈Q(A)}.最近十幾年，關(guān)于符號模式最小秩問題的一些新的結(jié)果不斷由世界各地專家學(xué)者給出[1-5]. 2012年，LiZhongshan等得到了最小秩mr(A)≤2的符號模式矩陣A的一些特性[6]. 2014年，M.Arav等人利用與1-Separation相關(guān)聯(lián)的某些廣義符號模式的最小秩，得到了一個(gè)含有一個(gè)1-Separation的符號模式的最小秩的計(jì)算公式[7]. 廣義符號模式的概念是通過允許符號模式中的某些元素為未定元擴(kuò)展來的[8-11].

令

為一個(gè)符號模式，其中A1,1，a2,2，A3,3，a3,3，A5,5分別為m1×n1，1×1，m2×n2，1×1，m3×n3符號模式，稱符號模式M含有兩個(gè)1-Separation. 本文將給出M的最小秩的計(jì)算公式.

1有關(guān)結(jié)論

令1≤k,l≤m1,m2,m3,n1,n2,n3, 且k+l≤m2,n2，并令

分別為m1×n1，m2×n2和m3×n3的分塊實(shí)矩陣，其中A2,2和B1,1為k×k方陣，B3,3和C1,1為l×l方陣，在文獻(xiàn)[12]中介紹了A和B的k-子直和，記為A⊕kB. 這里定義A，B和C的k-l-子直和，記為A⊕kB⊕lC，為矩陣A⊕kB⊕lC=

引理 1[13]令

其中：C2,2和D1,1為k×k矩陣，則rank(C⊕kD)≤rank(C⊕D).

由以上引理，不難得出以下推論：

推論 1令

其中:C2,2和D1,1為k×k矩陣；D3,3和E1,1為l×l矩陣. 則有rank(C⊕kD⊕lE)≤rank(C⊕D⊕E).引理 2令

為一個(gè)符號模式. 其中：A1,1，A3,3，A5，5，a2,2，a4,4分別為m1×n1，m2×n2，m3×n3，1×1，1×1符號模式. 則下列不等式(1)～式(10)成立：

1) mr(A1,1)+mr(A3,3)+mr(A5,5)+4≥mr(M).

2) mr(A1,1)+mr([A3,3A3,4])+mr([A5,4A5,5])+3≥mr(M).

3) mr([A1,1A1,2])+mr([A3,2A3,3])+mr(A5,5)+3≥mr(M).

6)mr([A1,1A1,2])+mr([A3,2A3,3A3,4])+mr([A5,4A5,5])+2≥mr(M).

10) 對于任意的 p,q∈{+,-,0}，

證明對于1)式，令C1,1∈Q(A1,1)，C3,3∈Q(A3,3)，C5,5∈Q(A5,5)，使得rank(C1,1)=mr(A1,1)，rank(C3,3)=mr(A3,3)，rank(C5,5)=mr(A5,5). 令C1,2∈Q(A1,2)，C2,1∈Q(A2,1)，C2,3∈Q(A2,3)，C3.2∈Q(A3,2)，C3.4∈Q(A3,4)，C4,3∈Q(A4,3)，C5,4∈Q(A5,4)，sgn(c2,2)=a2,2以及sgn(c4,4)=a4,4，則

對于2)式，令

使得

顯然，

式3)～9)的證明與式2)類似.

對于10)中最后一個(gè)不等式，令p,q∈{+,-,0}，令

并令

使得rank(C)=mr(Rp)，rank(D)=mr(Spq)和rank(E)=mr(Tq). 顯然，C⊕1D⊕1E∈Q(M). 由推論1得mr(M)≤rank(C⊕1D⊕1E)≤

rank(C)+rank(D)+rank(E)=

剩余6個(gè)不等式的證明與式10)中最后一個(gè)不等式的證明類似.

2主要結(jié)果

定理 1令

為一個(gè)符號模式，其中A1,1，A3,3，A5,5，a2,2，a4,4分別為m1×n1，m2×n2，m3×n3，1×1，1×1符號模式. 對于任意的p,q∈{+,-,0}，令

則

證明設(shè)

則

(1)

因此，rank(PBQ)≥rank(B). 由矩陣秩的性質(zhì)，rank(PBQ)≤rank(B)，故 rank(PBQ)=rank(B).

因而以下5種情形中的16個(gè)等式至少有一個(gè)成立：

(2)由推論1可知不等式反過來同樣成立，即式(2)為等式.

通過計(jì)算，我們可以得到P2B2Q2=

rank(B1,1)+rank(B2)+1=

(3)

類似地，E,H,F,G中僅有一個(gè)含有非零元，當(dāng)存在0≠e∈E時(shí)，

(5)

(6)

(7)

與情形2以及前面討論類似地，可以得到以下5個(gè)式子：

當(dāng)0≠e∈E和0≠f∈F時(shí)，

rank(B)=rank(B1,1)+

(8)

當(dāng)0≠e∈E和0≠g∈G時(shí)，

(9)

當(dāng)0≠f∈F和0≠g∈G時(shí)，

(10)

當(dāng)0≠f∈F和0≠h∈H時(shí)，

(11)

當(dāng)0≠g∈G和0≠h∈H時(shí)，

(12)

情形 4E,H,F,G中有3個(gè)含有非零元，不妨設(shè)0≠f∈F，0≠h∈H，0≠g∈G，則有以下式子成立

(13)

類似的3種情況分別有以下式子成立

rank(B)=rank(B1,1)+

(14)

(15)

rank(B)=rank(B1,1)+

(16)

情形 5E,H,F,G中都含有非零元，不妨設(shè)0≠e∈E，0≠h∈H，0≠f∈G，0≠g∈G，由矩陣的初等變換易得

rank(B)=rank(B1,1)+rank(B3,3)+

(17)

由引理3可知，定理結(jié)論中的等式左邊小于等于右邊成立，因而我們只需證明右邊至少有一項(xiàng)等于左邊.

令

使得rank(C)=mr(M).

由上面的討論，我們將矩陣B替換成矩陣C，可以得到與以上5種情形中等式對應(yīng)的16個(gè)類似的等式. 假設(shè)對應(yīng)于情形3中式(9)

成立，則

rank(C)=mr(M).

對應(yīng)于以上情形中式(5)～(7)、 式(10)～(14)的等式的證明，都與對應(yīng)于情形3中式(9)證明類似.

對于與情形1中2)對應(yīng)的等式的情況，由于

因此，

rank(C)=rank(M).

對于情形1至情形5中剩余等式的證明，都與情形1中2)對應(yīng)的等式的情況類似.

參考文獻(xiàn):

[1]ForsterJ.Alinearlowerboundontheunboundederrorprobabilisticcommunicationcomplexity[J].JournalofComputerandSystemSciences, 2002, 65(4)： 612-625.

[2]BarioliF,FallatSM,HogbenL.Computationofminimalrankandpathcovernumberforcertaingraphs[J].LinearAlgebraanditsApplications, 2004, 392： 289-303.

[3]邵燕靈, 高玉斌. 非負(fù)不可約模式的最小秩[J]. 華北工學(xué)院學(xué)報(bào), 2005, 26(1)： 6-10.

ShaoYanling,GaoYubin.Theminimumrankofnonnegativeirreduciblepatterns[J].JournalofNorthChinaInstituteofTechnology, 2005, 26(1)： 6-10. (inChinese)

[4]DeAlbaLM,HardyTL,HentzelIR,etal.Minimumrankandmaximumeigenvaluemultiplicityofsymmetrictreesignpatterns[J].LinearAlgebraanditsApplications, 2006, 418(2)： 394-415.

[5]BuC,WangW,SunL,etal.Minimum(maximum)rankofsignpatterntensorsandsignnonsingulartensors[J].LinearAlgebraanditsApplications, 2015, 483： 101-114.

[6]LiZ,GaoY,AravM,etal.Signpatternswithminimumrank2andupperboundsonminimumranks[J].LinearandMultilinearAlgebra, 2013, 61(7)： 895-908.

[7]AravM,HallFJ,LiZ,etal.Theminimumrankofasignpatternmatrixwitha1-separation[J].LinearAlgebraanditsApplications, 2014, 448： 205-216.

[8]高玉斌, 邵燕靈. 廣義星符號模式的秩[J]. 數(shù)學(xué)研究與評論, 2005, 25(4)： 610-614.

GaoYubin,ShaoYanling.Ranksofgeneralizedstarsignpatterns[J].JournalofMathematicalResearchandExposition, 2005, 25(4)： 610-614. (inChinese)

[9]BarioliF,FallatSM,HallHT,etal.Ontheminimumrankofnotnecessarilysymmetricmatrices：apreliminarystudy[J].ElectronicJournalofLinearAlgebra, 2009, 18： 126-145.

[10]HogbenL.Anoteonminimumrankandmaximumnullityofsignpatterns[J].ElectronicJournalofLinearAlgebra, 2011, 22(1)： 202-213.

[11]HallF,LiZ.Signpatternmatrices,in：L.Hogben(Ed),HandbookofLinearAlgebra, 2ndedition,Chapman/HallCRCPress, 2013,Chapter42.

[12]FallatSM,JohnsonCR.Sub-directsumsandpositivityclassesofmatrices[J].Linearalgebraanditsapplications, 1999, 288： 149-173.

[13]BarioliF,BarrettW,FallatSM,etal.ParametersRelatedtoTree-Width,ZeroForcing,andMaximumNullityofaGraph[J].JournalofGraphTheory, 2013, 72(2)： 146-177.

The Minimum Rank of a Sign Pattern Matrix with Two 1-Separations

LONG Jia-ping, SHAO Yan-ling

(Dept. of Mathematics, North University of China, Taiyuan 030051, China)

Abstract:The minimum rank of a sign pattern matrix is the smallest value among all real matrices ranks belong to the qualitative class of the sign pattern matrix. For the sign pattern matrix that has two 1-separations, the formula to compute the minimum rank of the sign pattern matrix is presented by the properties about the matrix rank and the methods of proving inequality.

Key words:sign pattern matrix; minimum rank; 1-separation

文章編號:1673-3193(2016)02-0112-08

*收稿日期:2015-08-10

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(11071227)

作者簡介：龍佳平(1992-)，男，碩士生，主要從事組合數(shù)學(xué)研究.

中圖分類號:O157

文獻(xiàn)標(biāo)識碼:A

doi:10.3969/j.issn.1673-3193.2016.02.004