关于Brualdi－Anstee猜想*

金晶晶

（福建船政交通职业学院公共教学部，福建福州 350007）

关于Brualdi－Anstee猜想*

金晶晶

（福建船政交通职业学院公共教学部，福建福州 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）是非负整数向量，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｝－矩阵；向量；变换；可共同实现

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′）称为可共同实现.

1989年，陈永川从矩阵的不可避免的结构出发（关于矩阵“不可避免的结构”的定义，见文献［3］），发现并证明导致u（R，S），u（R′，S′）和u（R＋R′，S＋S′）非空、但不可共同实现的必要条件［4］，并且，A.A Chernyak和Z.A Chernyak于1992年对此结论作了改进［5］.关于该猜想的后续相关研究，文献均未提及.与以上研究不同的是，本文将从｛0，1｝－矩阵对应位置上的元素特点和子矩阵变换角度出发，对猜想的已知条件作补充，使得该猜想成立并证明之，并且由此得到了两个新定理.

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′是非负整数向量，则存在矩阵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′）；根据矩阵的加法运算，对于任给的A∈u（R，S），B∈u（R′，S′），则u（R＋R′，S＋S′）中均存在唯一的矩阵C，满足C＝A＋B．

引理2 对于非空的u（R，S）中任意的矩阵A和B，存在一系列的变换，由此可将A转变为B，同样地，由此可得到u（R，S）中所有矩阵［6］.

引理2说明u（R，S）具有较强的连通性的，且引理2的逆否命题表明，如果非空的u（R，S）中的矩阵A不存在任何变换，那么u（R，S）中仅含一个矩阵.

定理2 设R、R′、S、S′是非负整数向量，如果对于任意的矩阵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）是非负整数向量，则矩阵类h（R，S）、h（R′，S′）和h（R＋R′，S＋S′）可共同实现的充分必要条件是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取值为有理数、实数或复数，定理仍然成立.此处不再赘述.

［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，Fujian Chuanzheng Communications College，Fuzhou 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－），男，福建福州人，福建船政交通职业学院公共教学部讲师，硕士.研究方向：组合图论.