關(guān)于Brualdi－Anstee猜想*

金晶晶

（福建船政交通職業(yè)學(xué)院公共教學(xué)部，福建福州 350007）

關(guān)于Brualdi－Anstee猜想*

金晶晶

（福建船政交通職業(yè)學(xué)院公共教學(xué)部，福建福州 350007）

著名的組合圖論專家Brualdi和Anstee于1980年獨(dú)立地提出了下述猜想：設(shè)R＝（r1，r2，…，rm）、R′＝（r′1，r′2，…，r′m）、S＝（s1，s2，…，sn）、S′＝（s′1，s′2，…，s′n）是非負(fù)整數(shù)向量，u（R，S）表示具有行和向量為R、列和向量為S的｛0，1｝－矩陣類，則存在矩陣A∈u（R，S），B∈u（R′，S′），使A＋B∈u（R＋R′，S＋S′）的充要條件是u（R，S）、u（R′，S′）和u（R＋R′，S＋S′）均非空.1986年，陳永川找到Brualdi－Anstee猜想的反例.對(duì)猜想的已知條件作補(bǔ)充，使得該猜想成立并證明之，并且由此得到了兩個(gè)新定理.

｛0，1｝－矩陣；向量；變換；可共同實(shí)現(xiàn)

1 基礎(chǔ)知識(shí)

基于以上對(duì)｛0，1｝－矩陣類u（R，S）的定義，1980年，Brualdi和Anstee獨(dú)立地提出了下述猜想：

但顯然A＋B≠C，即Brualdi－Anstee猜想不成立.

基于上述反例，1989年，陳永川給出如下定義：

定義2 若存在矩陣A∈u（R，S），B∈u（R′，S′），使A＋B∈u（R＋R′，S＋S′），則u（R，S）、u（R′，S′）和u（R＋R′，S＋S′）稱為可共同實(shí)現(xiàn).

1989年，陳永川從矩陣的不可避免的結(jié)構(gòu)出發(fā)（關(guān)于矩陣“不可避免的結(jié)構(gòu)”的定義，見(jiàn)文獻(xiàn)［3］），發(fā)現(xiàn)并證明導(dǎo)致u（R，S），u（R′，S′）和u（R＋R′，S＋S′）非空、但不可共同實(shí)現(xiàn)的必要條件［4］，并且，A.A Chernyak和Z.A Chernyak于1992年對(duì)此結(jié)論作了改進(jìn)［5］.關(guān)于該猜想的后續(xù)相關(guān)研究，文獻(xiàn)均未提及.與以上研究不同的是，本文將從｛0，1｝－矩陣對(duì)應(yīng)位置上的元素特點(diǎn)和子矩陣變換角度出發(fā)，對(duì)猜想的已知條件作補(bǔ)充，使得該猜想成立并證明之，并且由此得到了兩個(gè)新定理.

2 主要結(jié)論

為方便討論，以下u（R，S）和u（R′，S′）都是m×n的，故u（R＋R′，S＋S′）也是m×n的.

引理1 設(shè)A與B均為｛0，1｝－矩陣，則A＋B也是｛0，1｝－矩陣的充要條件是A與B與在相同位置上的元素不全為“1”.

證明 充分性：令C＝A＋B，設(shè)A、B和C中的第i行、第j列位置上的元素分別為aij、bij和cij（i＝1，…，m，j＝1，…，n），則cij＝aij＋bij．又因?yàn)閍ij，bij∈｛0，1｝，所以cij∈｛0，1，2｝．由A與B在相同位置上的元素不全為“1”，得cij∈｛0，1｝，即A＋B也是｛0，1｝－矩陣.

必要性：假設(shè)A與B與在某個(gè)相同位置上的元素全為“1”，則A＋B在對(duì)應(yīng)位置上的元素為“2”，這與A＋B也是｛0，1｝－矩陣矛盾，所以A與B與在相同位置上的元素不全為“1”，證畢.

定理1 設(shè)R、R′、S、S′是非負(fù)整數(shù)向量，則存在矩陣A∈u（R，S），B∈u（R′，S′），使A＋B∈u（R＋R′，S＋S′）的充要條件是u（R，S）、u（R′，S′）和u（R＋R′，S＋S′）均非空，并且A與B與在相同位置上的元素不全為“1”.

證明 必要性：由于存在A∈u（R，S），B∈u（R′，S′）且有A＋B∈u（R＋R′，S＋S′），所以u(píng)（R，S）、u（R′，S′）和u（R＋R′，S＋S′）均非空.另外，A、B和A＋B均為｛0，1｝－矩陣，由引理1得，A與B與在相同位置上的元素不全為“1”.

充分性：因?yàn)閡（R，S），u（R′，S′）均非空，所以不妨設(shè)A∈u（R，S），B∈u（R′，S′），下證A＋B∈u（R＋R′，S＋S′）．因?yàn)锳與B均為｛0，1｝－矩陣，且A與B與在相同位置上的元素不全為“1”，所以由引理1得，A＋B也是｛0，1｝－矩陣.設(shè)A、B和A＋B中的第i行、第j列位置上的元素分別為aij、bij和aij＋bij（i＝1，…，m，j＝1，…，n），則aij，bij，aij＋bij∈｛0，1｝．

由定理1可得到一些有趣的結(jié)論，如：對(duì)于任意的矩陣A∈u（R，S），B∈u（R′，S′），滿足A與B在相同位置上的元素不全為“1”，則有A＋B∈u（R＋R′，S＋S′）；根據(jù)矩陣的加法運(yùn)算，對(duì)于任給的A∈u（R，S），B∈u（R′，S′），則u（R＋R′，S＋S′）中均存在唯一的矩陣C，滿足C＝A＋B．

引理2 對(duì)于非空的u（R，S）中任意的矩陣A和B，存在一系列的變換，由此可將A轉(zhuǎn)變?yōu)锽，同樣地，由此可得到u（R，S）中所有矩陣［6］.

引理2說(shuō)明u（R，S）具有較強(qiáng)的連通性的，且引理2的逆否命題表明，如果非空的u（R，S）中的矩陣A不存在任何變換，那么u（R，S）中僅含一個(gè)矩陣.

定理2 設(shè)R、R′、S、S′是非負(fù)整數(shù)向量，如果對(duì)于任意的矩陣A∈u（R，S），B∈u（R′，S′），C∈u（R＋R′，S＋S′），滿足以下條件：

（1）A與B在相同位置上的元素不全為“1”；

（2）C中不存在任何變換.

則有A＋B＝C.

證明：因?yàn)锳與B與在相同位置上的元素不全為“1”，由定理1得，存在矩陣A1∈u（R，S），B1∈u（R′，S′），使A1＋B1∈u（R＋R′，S＋S′）．

但對(duì)于任意的矩陣A∈u（R，S），B∈u（R′，S′），因?yàn)锳與B在相同位置上的元素不全為“1”，由定理1得，A＋B∈u（R＋R′，S＋S′）．因?yàn)镃不是變換矩陣，由引理2，u（R＋R′，S＋S′）中僅存在唯一的矩陣，即A＋B＝C，證畢.

在定理2中，若條件（2）不滿足，則定理2不成立.

例2 設(shè)R＝（1，0），S＝（1，0）；R′＝（0，1），S′＝（0，1）；則R＋R′＝（1，1），S＋S′＝（1，1）；

下面，h（R，S）表示所有的｛0，1，…，k｝－矩陣A＝（aij）m×n的集合，則有：

定理3 設(shè)R＝（r1，r2，…，rm）、R′＝（r′1，r′2，…，r′m）、S＝（s1，s2，…，sn）、S′＝（s′1，s′2，…，s′n）是非負(fù)整數(shù)向量，則矩陣類h（R，S）、h（R′，S′）和h（R＋R′，S＋S′）可共同實(shí)現(xiàn)的充分必要條件是h（R，S）、h（R′，S′）和h（R＋R′，S＋S′）均非空.

證明：

必要性：由于存在A∈h（R，S），B∈h（R′，S′）且有A＋B∈h（R＋R′，S＋S′），所以h（R，S），h（R′，S′）和h（R＋R′，S＋S′）均非空.

不難證明，在定理3中，若h（R，S）中任意矩陣A的元素aij取值為有理數(shù)、實(shí)數(shù)或復(fù)數(shù)，定理仍然成立.此處不再贅述.

［1］Brualdi R A.Matrices of zeros and ones with fxed row and column sum vectors［J］.Linear Algebra and Its Applications，1980，（33）：159－231.

［2］Chen Y.A counterexample to a conjecture of Brualdi and Anstee［J］.Journal of Mathmatical Research and Exposition，1986，（1）：68.

［3］Ryser H J.Combinatorial configurations［J］.SIAM Journal on Applied Mathmatics，1969，（17）：593－602.

［4］Chen Y，Shastri A.On joint realization of（0，1）matrices［J］. Linear Algebra and Its Applications，1989，（112）：75－85.

［5］Chernyak A A，Chernyak Z A.Joint realization of（0，1）matrices revisited［J］.Linear Algebra and Its Applications，1992，（174）：25－35.

［6］Brualdi R A.Combinatorial Matrix Classes［M］.Cambridge：Cambridge University Press，2006.

（責(zé)任編校：晴川）

On Brualdi－Anstee Conjecture

JIN Jingjing
（Department of Public Education，F(xiàn)ujian Chuanzheng Communications College，F(xiàn)uzhou Fujian 350007，China）

Brualdi and Anstee，two famous experts of combinatorics and graph theory，raised a conjecture in 1980 as follows：Let R＝（r1，r2，…，rm），R′＝（r′1，r′2，…，r′m），S＝（s1，s2，…，sn）and S′＝（s′1，s′2，…，s′n）be nonnegative integral vector.Denote by u（R，S）the classes of（0，1）matrix with row sum vector R and column sum vector S．There exist amatrix A∈u（R，S）and amatrix B∈u（R′，S′）such that A＋B∈u（R＋R′，S＋S′）．The necessary and sufficient condition for it is u（R，S）、u（R′，S′）and u（R＋R′，S＋S′）are not empty.Y.C.Chen found the counterexample in 1986.In this paper，tomake the conjecture established and prove it，wemake some supplement for the known conditions of the conjecture，then two new theorems are obtained according to it.

（0，1）matrix；vector；interchange；jointly realizable

O157.1；O151.21

A

1008－4681（2014）05－0006－03

2014－09－04

福建省中青年教師教育科研項(xiàng)目（批準(zhǔn)號(hào)：JA13379）.

金晶晶（1983－），男，福建福州人，福建船政交通職業(yè)學(xué)院公共教學(xué)部講師，碩士.研究方向：組合圖論.