金晶晶
(福建船政交通职业学院公共教学部,福建福州 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}-矩阵;向量;变换;可共同实现

基于以上对{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}-矩阵对应位置上的元素特点和子矩阵变换角度出发,对猜想的已知条件作补充,使得该猜想成立并证明之,并且由此得到了两个新定理.
为方便讨论,以下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}-矩阵.
必要性:假设……