關于Brualdi－Anstee猜想*

金晶晶

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

關于Brualdi－Anstee猜想*

金晶晶

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

著名的組合圖論專家Brualdi和Anstee于1980年獨立地提出了下述猜想：設R＝（r1，r2，…，rm）、R′＝（r′1，r′2，…，r′m）、S＝（s1，s2，…，sn）、S′＝（s′1，s′2，…，s′n）是非負整數(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猜想的反例.對猜想的已知條件作補充，使得該猜想成立并證明之，并且由此得到了兩個新定理.

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

1 基礎知識

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

但顯然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′）稱為可共同實現(xiàn).

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

2 主要結論

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

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

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

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

定理1 設R、R′、S、S′是非負整數(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（R，S）、u（R′，S′）和u（R＋R′，S＋S′）均非空.另外，A、B和A＋B均為｛0，1｝－矩陣，由引理1得，A與B與在相同位置上的元素不全為“1”.

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

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

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

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

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

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

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

則有A＋B＝C.

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

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

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

例2 設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 設R＝（r1，r2，…，rm）、R′＝（r′1，r′2，…，r′m）、S＝（s1，s2，…，sn）、S′＝（s′1，s′2，…，s′n）是非負整數(shù)向量，則矩陣類h（R，S）、h（R′，S′）和h（R＋R′，S＋S′）可共同實現(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ù)，定理仍然成立.此處不再贅述.

［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.

（責任編校：晴川）

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

福建省中青年教師教育科研項目（批準號：JA13379）.

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