布尔矩阵的组合合成及其图表示

第26卷第1期

2006年3月　　　　数学理论与应用

M A TH E M A T I CAL TH EOR Y AND A PPL I CA T I ON S 　　　　　　　　V o l . 26N o. 1　　M ar . 2006

布尔矩阵的组合合成及其图表示

左光纪

(青海民族学院, 西宁, 810007) Ξ

摘　要　本文综术了有关布尔矩阵的组合合成的现有结果, 用图论方法展示了它们的组合性质, 提出了一些待解决的问题。

关键词　布尔矩阵　伴随图　组合合成　可约性　强连通性

The Com bi nator i al Com pound of Boolean M atr ix

w ith Graph ical Represen tation

(Q Co , )

Abstract 　T h p t resu lts on the com b inato rial compound of Boo lean m atrix , and show their com b inato p by graph ical m ethod . Som e un so lved p rob lem s are p rovided .

Keywords 　Boo lean m atrix 　asso iciated digraph 　com b inato rial compound 　reducib ility 　strong connectivity

1　引言和基本概念

设A 是n 阶(0, 1) -矩阵, 若按Boo lean 运算来定义矩阵的加法和乘法, A 就是布尔矩阵。周知, 一个n 阶布尔矩阵A 对应一个n 阶有向图D (A ) , 称为A 的伴随图, 又称A 为D (A ) 的邻接矩阵。布尔矩阵A 的许多组合性质都可用它的伴随图D (A ) 直观表示, 一些基本概念和术语可参见文[1][2]. 下面重申与本文密切相关的几个概念。

n 阶方阵A 称为可约的, 如果有置换方阵P , 使

B 　0　　　　　　　P T A P =C 　D

其中B 为k 阶方阵, 1≤k ≤n -1, 右上角是k ×(n -k ) 的零矩阵。不是可约的方阵称为不可约的。

n 阶方阵A 称为部分可分的, 如果n >1, 有置换方阵P 和Q , 使

B 　0　　　　　　　PA Q =C 　D

Ξ冶成福教授推荐

　收稿日期:2005年6月17日

28数学理论与应用　　　　　　　　　　　　　　　　　第26卷　其中B 和D 是非空方阵。不是部分可分的方阵称为完全不可分的。

命题1　布尔方阵A 是不可约的当且仅当它的伴随图D (A ) 是强连通的。

k n 阶布尔方阵A 称为本原的, 若存在正整数k , 使A >0; 这些正整数的最小者k 0称为A 的

本原指数, 记作Χ(A ) .

命题2　布尔方阵A 为本原阵的充要条件是:

(1) A 的伴随图D (A ) 是强连通的,

(2) D (A ) 的所有不同的圈长数集的最大公约数为1。

n 阶(0, 1) -矩阵A 的项秩Θ(A ) 是取自A 中不同行和不同列的非零元的最大个数, 当p (A ) =n 时表示D (A ) 有完美匹配, 当Θ(A )

仿照一般矩阵的行列式合成, R. A. B rualdi 和李乔引入了布尔矩阵的组合合成[3]。设r , n 为正整数, 1≤r ≤n , Q r , n 表示取自集{1,2…, n }的所有长r 的严格递增序列的集合。对Α={i 1, i 2, …, i r }和Β=(j 1, j 2…, j r ) ∈Q r , n , A [Α Β]表示A 的r 阶子矩阵, 它的行由Α的项标记, 列由Β的项标记。n 阶布尔矩阵A 的r 级组合合成C r (A ) 是n

r 阶布尔矩阵, Q r , n 的元

素标记, 按字典序排列, C r (A ) =[c ΑΒ]:]r 时, c ΑΒ=1, 当Θ(A [Α Β]

C r ) , D 的r 级合成。设D 的顶点集为{1,2, , }1, 的r 级合成图D r 有顶点集Q r , n 。对D r 的任意顶点Α=(i 1, i 2, …, i r ) (j 1j 2…, j r ) , 从Α到Β有弧当且仅当存在1, 2, …, r 的置换k 1, k 2, …, k r , 使D 中有一组从i t 到i k t 的弧, t =1, 2, …, r .

从上述定义不难看出组合合成阵与合成图有如下对应关系。

命题3　对任意的n 阶布尔矩阵A , 有

　　　　　　　D (C r (A ) ) =(D (A ) ) r , r =1, 2, …, n .

一般说来, 组合合成阵的结构很复杂, 是一个较难的研究课题。文[3]开创这一研究方向后只得到少许结果就搁下了。近十年来, 作者在该研究方向做了一系列结果[4-10],现综述如下.

2　组合合成阵的可分性与可约性

正如文[1]所述, 矩阵的可分性是在置换相抵下不变的组合性质, 它只能用约化相伴二部图来描述。对布尔矩阵的组合合成, 很难用命题3来描述C r (A ) 的可分性。但是, 文[3]得到了下述结果。

定理1　设A 是n 阶(0, 1) 矩阵, r 为整数1≤r ≤n -1, 则A 是完全不可分的当且仅当r 组组合合成阵C r (A ) 是完全不可分的。

对n >1, 设P n =[p ij ]表示n 阶(0, 1) -矩阵, 其中仅有n 个非零元p 12=p 23=…=p n -1=p n 1=1, I n 表示n 阶单位矩阵, 令F n =I n +P n 。易见, F n 是完全不可分的。对n 阶(0, 1) -矩阵A , 用Ρ(A ) 表示A 中1的个数。容易检验, 若A 是完全不可分的, 则Ρ(A ) ≥2n , 仅当A 置换相抵于F n 时等号才成立。于是, 文[3]对组合合成阵中非零元的个数提出了如下猜想:设A 是一个完全不可分的n 阶(0, 1) -矩阵, 则对每个r , 1≤r ≤n , 有ΡC r (A ) ) ≥Ρ(C r (F n ) ) .

对r =2, 3, , 该文证明了猜想的正确性, 得到下述结果。

　第1期　　　　　　　　　　　　布尔矩阵的组合合成及其图表示29　　定理2　若A 是完全不可分的n 阶(0, 1) -矩阵A , 则

当n ≥3时, Ρ(C 2(A ) ) ≥n (2n -3) ;

当n ≥4时, Ρ(C 3(A ) ≥2n (n -2) (2n -5) 3.

矩阵的可约性是在置换相似下不变的组合性质, 可用它的伴随图来直观描述(见命题1) 。文[3]仅对特殊情形证明了下述结果。

定理3　设D 是有向图, 顶点集V (D ) ={1,2, …, n },各顶点有一个环, r 是整数, 1≤r ≤n . 若D 是强连通的, 则r 级合成图D r 也是强连通的, 且在各顶点有一个环。

用命题1可把定理3改用矩阵说法:设A 是对角元皆为正的n 阶(0, 1) -矩阵, 若A 是不可约的, 则r 级组合合成阵C r (A ) 也是不可约的, 且对角元皆为正。

文[4][5]进而考察了合成图的直径∆和对应组合合成阵的本原指数Χ, 得到了下述结果。定理4　若A 是正对角元本原矩阵, 则C r (A ) 也是正对角元本原矩阵, 且Χ(C r (A ) ) ) =∆(((D (A ) ) r ) .

定理5　设D 是各顶点有环的n 阶强连通图, 它的直径为∆, 则D 的2D 2的直径∆(D 2) 满足:∆-1≤∆(D 2) ≤∆+1及∆(D 2) ≤-n -n -2的直径满足:∆(D n -2) ≤2.

考察D 的邻接矩阵A , 1, 。

定理6　若A , Χ满足:Χ(A ) -1≤Χ(C 2(A ) ≤Χ(A ) +1, Χ(C 2(A -(C n -2A ) ≤2.

根据定理, 文[5]还提出了如下猜想:

设A 是正对角元n 阶本原矩阵, 则

(1) Χ(C r (A ) ) ≤n -2对一切r 成立;

(2) Χ(a ) -(r -1) ≤Χ(C r (A ) ) ≤Χ(A ) +(r -1) 对r

最近, 作者证明了第一个猜想(见文[10]) , 即

定理7　若A 是正对然元n 阶本原矩阵, 则它的r 级组合合成阵C r (A ) 的本原指数Χ(C r (A ) ) ≤n -r , 对一切r 成立.

除了定理3讨论的特殊情况, 许多例子表明, 不可约矩阵的组合合成并不保持不可约性。但是文[6]用图论方法得到了下述否命题。

定理8　若n 阶布尔矩阵A 中约, 则它的r 级组合合成阵C r (A ) 也可约, 1≤r ≤n . 一个非强连通图可分解为若干强连通分支; 对应的, 一个可约矩阵置换相似于某个分块下三角阵, 其中各对角块为不可约子阵。因此, 我们应重点研究不可约矩阵的组合合成, 于是提出下述待解决的问题:设A 是不可约布尔矩阵, 在什么条件下C r (A ) 也是不可约的? 进而, 还可以考察C r (A ) 的本原指数或幂敛指数问题。

3　一些特殊矩阵的组合合成及图论表示

组合合成阵C r (A ) 的复杂结构来自两个方面, 一是矩阵A 的结果, 二是较高的级别r . 我们先从简单的布尔矩阵A 做起, 由命题1, 需考察伴随图D (A ) 的r 级合成。由于圈是有向图的基本构形, 文[6]首先证明了下述结果。

定理9　若有向图D 无圈, 则r 级合成图D r 也无圈; 若D 有长l 的圈, 则当r

30数学理论与应用　　　　　　　　　　　　　　　　　第26卷　设有向圈C n 的顶点集V ={1,2, …, n },从点i 到i +1有弧, i =1, 2, …, n -1, 从点n 到1有弧。文[9]考察了C n 的r 级合成图(C n ) r , 得到了下述结果。

定理10　(1) (C n ) r 由若干互不相交的有向圈组成;

(2) 对所有r , (C n ) r 同构于(C n ) n -r , 记作(C n ) r =(C n ) n -r ;

(3) 对1≤r ≤n -1, (C n ) r 中的最长圈之长为n 。较短圈之长l 是n 的因子;

(4) (C n ) r 中有长l 的圈当且仅当d =n l 是n 与r 的公因子。

命题11　设r 与n 的所有公因子为1=d 1

　　　　　　　(C n ) r =k 1C l 1∪k 2C l 2∪…∪k t C lt .

其中长l i 的圈C li 的个数k i >0满足k 1l 1+k 2l 2+…+k t l t =n

r

定理12　设整数l ≤m , 则合成图(C m d ) kd 中长l 的圈之个数等于C m ) k 中长l 的圈之个数。. 上述定理12提供了一个递推方法来计算定理11中的圈数k 1, k 2, …, k t , 于是所有(C n ) r 被完全描述。

设C n 1…, C n k 分别是长n 1…n k 的有向圈, 文[9r 级合成, 引入圈之积的概念, 定理13　(1) r 1…n r , 且有(Cn 1∪…∪C n k ) n -r =(n k ) r n n 1+…+n k ;

(2) (C n 1C k ) r =∪(C n 1) r 1×…(C n k ) r k , 其中不相交圈之并∪取遍r 的所有k 项整数有序分拆:

　　　　　　　r =r 1+…+r k , r 1, …r k ≥0.

由于n 阶置换矩阵P 的伴随图D (P ) 或是一个有向圈C n , 或是多个不相交圈之并; 故定理11, 12, 13用图论方法完全描述了置换矩阵的组合合成。还有一个简要的结论如下:

定理14　设P 是n 阶置换矩阵, 则C r (P ) 是

C n -r (P ) . n r 阶置换矩阵, 且C r (P ) 置换相似于

对稍微复杂的布尔矩阵, 目前只能考虑它的2级组合合成。在有向圈C n 上添加一条从点k 到1的弧得到的有向图记作C n +[k , 1],称为带一条弦的有向圈。文[8]考察了带弦的有向圈的2级合成, 经过繁杂的推导, 得到了简明而有趣的结果。

定理15　对1≤k ≤n , 带弦有向圈的2级合成图(C n +[k , 1]) 2强连通的充要条件是k 与n 互素。

设A n , k =(a ij ) 为n 阶布尔矩阵, a i , i +1=1(i =1, 2, …, n -1) , a n 1=1, a k 1=1, 其它a ij =0; A n , k 正好是C n +[k , 1]的邻接矩阵; 于是有下述结果。

定理16　对1≤k

取两个有向圈C m =x 1x 2…x m x 1和C n =y 1y 2…y n y 1在C m 与C n 之间连两条弧x 1y 1和y k x l , 1≤k ≤n , 1≤l ≤m , 如此得到的有向图记作G (m , n ; k , l ) , 它是有m +n 个顶点和m +n +

m +n m 2条弧的强连通图。文[6]考察了该图的2级合成(G (m , n ; k , l ) 2, 把它的=+　22

　第1期　　　　　　　　　　　　布尔矩阵的组合合成及其图表示31n

+m n 个顶点划分为三个子集;

U ={(x i x 1) 1≤i , j ≤m , i ≠j },V ={(y i y j ) 1≤i , j ≤n , i ≠j },W ={(x i y j ) 1≤i ≤m },1≤j ≤n },

用下述定理刻画了它的结果。

定理17　设[U ]、[V ]、[W ]分别表示顶点集U , V , W 在(G (m , n ; k , l ) ) 2中的诱导子图则(1) [U ]由[m 2]个不相交圈组成, 有m

2条弧; [V ]由[n 2]个不相交圈组成, 有n

条

弧;

(2) [W ]由p 个长q 的不相交圈组成, 有m n +1条弧, 其中p 为m 与n 的最大公约数, q 为m 与n 的最小公倍数,

(3) 从U 到W 和从W 到U 各有m 1; 从V 到W 和从W 到V 各有n -1条弧;

+2(m +n ) -3条弧。　2

此外, 文[6]还给出了(G (m , n ; k , l ) ) 2定理18　(1) 若m 与n 互素, k G ; , l ) ) 2强连通; (2) 设m 与n . d (, ) , G , n ; p -1, p ) ) 2强连通, (3) m 2n ; -m ) ) 2强连通。(4) 2级合成圈(G (m , n ; k , l ) ) 2共有m +n

设图G (m l ) A (m , n ; k , l ) , 文[6]还得到了下述结果。

定理19　设m +n 阶布尔矩阵B ≥A (m , n ; k , l ) , 若下列条件之一满足, 则2级组合合成阵C 2(B ) 是不可约的, 且是本原的;

(1) g . c . d (m , n ) =1, 1≤k ≤n , 1≤l ≤m ;

(2) g . c . d (m , n ) =p ≥2, k =p -l , l =p ;

(3) m ≥1, n ≥2, k =n -1, l =m .

看来, 讨论复杂布尔矩阵A 的组合合成C r (A ) 的组合性质, 还有许多工作可做。我们期望有更多的矩阵类(例如循环矩阵) 的组合合成被探讨。

4　对称布尔矩阵的组合合成

设A 是对称布尔矩阵, 则D (A ) 的每条弧都有反向弧, 故可用一个无向图G (A ) 来代替D (A ) 。类似地, 对应于A 的r 级组合合成(C r (A ) , 可定义无向图G 的r 级合成G r 。对应于命题1和3, 我们有

命题4　设A 是对称布尔矩阵, 则A 不可约当且仅当图G (A ) 连通。

命题5　设A 是对称布尔矩阵, 则C r (A ) 也是对称布尔矩阵, 且G (C r (A ) ) =(G (A ) ) r . 由此可见, 对称布尔矩阵A 的组合合成C r (A ) 的不可约问题转化为考察合成图(G (A ) ) r 的连通性。容易证明, 若无向图G 不连通, 则它的r 级合成图G r 不连通。但是, 有例子表明, 图G 连通还不是G r 连通的充分条件。文[7]仅考察了2级合成图在什么条件下才是连通的, 得到了下述结果。

定理20　设C n 是长n 的无向圈, 则当n 为奇数时2级合成图(C n ) 2的连通; 当n 为偶数是(C n ) 2不连通, 仅有两个分支。

定理21　(1) 若G 是连通的二分图, 则2级合成图G 2不连通;

32数学理论与应用　　　　　　　　　　　　　　　　　第26卷　

(2) 若G 是2-连通图, 且含有奇圈(即G 不是二分图) , 则2级合成图G 2连通。上述两个定理表明, G 含有奇圈是G 2连通的必要条件。但是, 有例子表明, G 的2-连通性不是G 2连通的必要条件。

用图论方法考察对称布尔矩阵A 的2级合合成C 2(A ) , 文[7]还有如下结果。定理22　设A 是对称布尔矩阵, 对角元皆为零, 有2e 个非零元, 则C 2(A ) 恰有e 个非零对角元。

定理23　设A 是n 阶对称布尔矩阵, G (A ) 为2-连通图且含有奇圈, 则2-级组合合成阵C 2(A ) 是不可约的和本原的, 且本原指数Χ(C 2(A ) ) ≤n 2-2n -1.

最后指出, 虽然组合合成阵的结构复杂, 难以考察。但这也为大家提供了丰富的研究领域, 期望有更好的方法和更多的成果出现。

参考文献

[1]　柳柏濂1组合矩阵论[M ]1北京:科学出版社, 19961

[2]　R ichard A . B rualdi , H erbert J . R yser . Com b inato rial atrix []. b U n iversity P ress , 1991.

[3]　R ichard A . B rualdi , L i Q iao . O b atrix [J ]. M ath R es &Expo siti on , 1988, 1:153-162.

[4]　G . J . Zuo . b of p ri m itive m atrix [M ]. Com b inato rics and Graph T heo ry 95-100, pub lished by o Scien tific , Singapo r , 1993.

[5]　左光纪1组合合成阵的本原指数[J ]1应用数学, 1996(增刊) , 86-1011

[6]　左光纪1组合合成阵的不可约性[J ]1青海师大学报, 1998(3) :25-301

[7]　左光纪1对称布尔矩阵的组合合成[J ]1青海师大学报, 2000(2) , 1-41

[8]　左光纪1带弦有向圈的2级合成[J ]1数学研究, 2000(4) :379-3851

[9]　左光纪1置换矩阵的组合合成及其图表示[J ]1数学研究, 2001(1) , 100-1041

[10]　左光纪1组合合成阵本原指数的一个上界[J ]1数学研究, 2005(1) , 89-931

第26卷第1期

2006年3月　　　　数学理论与应用

M A TH E M A T I CAL TH EOR Y AND A PPL I CA T I ON S 　　　　　　　　V o l . 26N o. 1　　M ar . 2006

布尔矩阵的组合合成及其图表示

左光纪

(青海民族学院, 西宁, 810007) Ξ

摘　要　本文综术了有关布尔矩阵的组合合成的现有结果, 用图论方法展示了它们的组合性质, 提出了一些待解决的问题。

关键词　布尔矩阵　伴随图　组合合成　可约性　强连通性

The Com bi nator i al Com pound of Boolean M atr ix

w ith Graph ical Represen tation

(Q Co , )

Abstract 　T h p t resu lts on the com b inato rial compound of Boo lean m atrix , and show their com b inato p by graph ical m ethod . Som e un so lved p rob lem s are p rovided .

Keywords 　Boo lean m atrix 　asso iciated digraph 　com b inato rial compound 　reducib ility 　strong connectivity

1　引言和基本概念

设A 是n 阶(0, 1) -矩阵, 若按Boo lean 运算来定义矩阵的加法和乘法, A 就是布尔矩阵。周知, 一个n 阶布尔矩阵A 对应一个n 阶有向图D (A ) , 称为A 的伴随图, 又称A 为D (A ) 的邻接矩阵。布尔矩阵A 的许多组合性质都可用它的伴随图D (A ) 直观表示, 一些基本概念和术语可参见文[1][2]. 下面重申与本文密切相关的几个概念。

n 阶方阵A 称为可约的, 如果有置换方阵P , 使

B 　0　　　　　　　P T A P =C 　D

其中B 为k 阶方阵, 1≤k ≤n -1, 右上角是k ×(n -k ) 的零矩阵。不是可约的方阵称为不可约的。

n 阶方阵A 称为部分可分的, 如果n >1, 有置换方阵P 和Q , 使

B 　0　　　　　　　PA Q =C 　D

Ξ冶成福教授推荐

　收稿日期:2005年6月17日

28数学理论与应用　　　　　　　　　　　　　　　　　第26卷　其中B 和D 是非空方阵。不是部分可分的方阵称为完全不可分的。

命题1　布尔方阵A 是不可约的当且仅当它的伴随图D (A ) 是强连通的。

k n 阶布尔方阵A 称为本原的, 若存在正整数k , 使A >0; 这些正整数的最小者k 0称为A 的

本原指数, 记作Χ(A ) .

命题2　布尔方阵A 为本原阵的充要条件是:

(1) A 的伴随图D (A ) 是强连通的,

(2) D (A ) 的所有不同的圈长数集的最大公约数为1。

n 阶(0, 1) -矩阵A 的项秩Θ(A ) 是取自A 中不同行和不同列的非零元的最大个数, 当p (A ) =n 时表示D (A ) 有完美匹配, 当Θ(A )

仿照一般矩阵的行列式合成, R. A. B rualdi 和李乔引入了布尔矩阵的组合合成[3]。设r , n 为正整数, 1≤r ≤n , Q r , n 表示取自集{1,2…, n }的所有长r 的严格递增序列的集合。对Α={i 1, i 2, …, i r }和Β=(j 1, j 2…, j r ) ∈Q r , n , A [Α Β]表示A 的r 阶子矩阵, 它的行由Α的项标记, 列由Β的项标记。n 阶布尔矩阵A 的r 级组合合成C r (A ) 是n

r 阶布尔矩阵, Q r , n 的元

素标记, 按字典序排列, C r (A ) =[c ΑΒ]:]r 时, c ΑΒ=1, 当Θ(A [Α Β]

C r ) , D 的r 级合成。设D 的顶点集为{1,2, , }1, 的r 级合成图D r 有顶点集Q r , n 。对D r 的任意顶点Α=(i 1, i 2, …, i r ) (j 1j 2…, j r ) , 从Α到Β有弧当且仅当存在1, 2, …, r 的置换k 1, k 2, …, k r , 使D 中有一组从i t 到i k t 的弧, t =1, 2, …, r .

从上述定义不难看出组合合成阵与合成图有如下对应关系。

命题3　对任意的n 阶布尔矩阵A , 有

　　　　　　　D (C r (A ) ) =(D (A ) ) r , r =1, 2, …, n .

一般说来, 组合合成阵的结构很复杂, 是一个较难的研究课题。文[3]开创这一研究方向后只得到少许结果就搁下了。近十年来, 作者在该研究方向做了一系列结果[4-10],现综述如下.

2　组合合成阵的可分性与可约性

正如文[1]所述, 矩阵的可分性是在置换相抵下不变的组合性质, 它只能用约化相伴二部图来描述。对布尔矩阵的组合合成, 很难用命题3来描述C r (A ) 的可分性。但是, 文[3]得到了下述结果。

定理1　设A 是n 阶(0, 1) 矩阵, r 为整数1≤r ≤n -1, 则A 是完全不可分的当且仅当r 组组合合成阵C r (A ) 是完全不可分的。

对n >1, 设P n =[p ij ]表示n 阶(0, 1) -矩阵, 其中仅有n 个非零元p 12=p 23=…=p n -1=p n 1=1, I n 表示n 阶单位矩阵, 令F n =I n +P n 。易见, F n 是完全不可分的。对n 阶(0, 1) -矩阵A , 用Ρ(A ) 表示A 中1的个数。容易检验, 若A 是完全不可分的, 则Ρ(A ) ≥2n , 仅当A 置换相抵于F n 时等号才成立。于是, 文[3]对组合合成阵中非零元的个数提出了如下猜想:设A 是一个完全不可分的n 阶(0, 1) -矩阵, 则对每个r , 1≤r ≤n , 有ΡC r (A ) ) ≥Ρ(C r (F n ) ) .

对r =2, 3, , 该文证明了猜想的正确性, 得到下述结果。

　第1期　　　　　　　　　　　　布尔矩阵的组合合成及其图表示29　　定理2　若A 是完全不可分的n 阶(0, 1) -矩阵A , 则

当n ≥3时, Ρ(C 2(A ) ) ≥n (2n -3) ;

当n ≥4时, Ρ(C 3(A ) ≥2n (n -2) (2n -5) 3.

矩阵的可约性是在置换相似下不变的组合性质, 可用它的伴随图来直观描述(见命题1) 。文[3]仅对特殊情形证明了下述结果。

定理3　设D 是有向图, 顶点集V (D ) ={1,2, …, n },各顶点有一个环, r 是整数, 1≤r ≤n . 若D 是强连通的, 则r 级合成图D r 也是强连通的, 且在各顶点有一个环。

用命题1可把定理3改用矩阵说法:设A 是对角元皆为正的n 阶(0, 1) -矩阵, 若A 是不可约的, 则r 级组合合成阵C r (A ) 也是不可约的, 且对角元皆为正。

文[4][5]进而考察了合成图的直径∆和对应组合合成阵的本原指数Χ, 得到了下述结果。定理4　若A 是正对角元本原矩阵, 则C r (A ) 也是正对角元本原矩阵, 且Χ(C r (A ) ) ) =∆(((D (A ) ) r ) .

定理5　设D 是各顶点有环的n 阶强连通图, 它的直径为∆, 则D 的2D 2的直径∆(D 2) 满足:∆-1≤∆(D 2) ≤∆+1及∆(D 2) ≤-n -n -2的直径满足:∆(D n -2) ≤2.

考察D 的邻接矩阵A , 1, 。

定理6　若A , Χ满足:Χ(A ) -1≤Χ(C 2(A ) ≤Χ(A ) +1, Χ(C 2(A -(C n -2A ) ≤2.

根据定理, 文[5]还提出了如下猜想:

设A 是正对角元n 阶本原矩阵, 则

(1) Χ(C r (A ) ) ≤n -2对一切r 成立;

(2) Χ(a ) -(r -1) ≤Χ(C r (A ) ) ≤Χ(A ) +(r -1) 对r

最近, 作者证明了第一个猜想(见文[10]) , 即

定理7　若A 是正对然元n 阶本原矩阵, 则它的r 级组合合成阵C r (A ) 的本原指数Χ(C r (A ) ) ≤n -r , 对一切r 成立.

除了定理3讨论的特殊情况, 许多例子表明, 不可约矩阵的组合合成并不保持不可约性。但是文[6]用图论方法得到了下述否命题。

定理8　若n 阶布尔矩阵A 中约, 则它的r 级组合合成阵C r (A ) 也可约, 1≤r ≤n . 一个非强连通图可分解为若干强连通分支; 对应的, 一个可约矩阵置换相似于某个分块下三角阵, 其中各对角块为不可约子阵。因此, 我们应重点研究不可约矩阵的组合合成, 于是提出下述待解决的问题:设A 是不可约布尔矩阵, 在什么条件下C r (A ) 也是不可约的? 进而, 还可以考察C r (A ) 的本原指数或幂敛指数问题。

3　一些特殊矩阵的组合合成及图论表示

组合合成阵C r (A ) 的复杂结构来自两个方面, 一是矩阵A 的结果, 二是较高的级别r . 我们先从简单的布尔矩阵A 做起, 由命题1, 需考察伴随图D (A ) 的r 级合成。由于圈是有向图的基本构形, 文[6]首先证明了下述结果。

定理9　若有向图D 无圈, 则r 级合成图D r 也无圈; 若D 有长l 的圈, 则当r

30数学理论与应用　　　　　　　　　　　　　　　　　第26卷　设有向圈C n 的顶点集V ={1,2, …, n },从点i 到i +1有弧, i =1, 2, …, n -1, 从点n 到1有弧。文[9]考察了C n 的r 级合成图(C n ) r , 得到了下述结果。

定理10　(1) (C n ) r 由若干互不相交的有向圈组成;

(2) 对所有r , (C n ) r 同构于(C n ) n -r , 记作(C n ) r =(C n ) n -r ;

(3) 对1≤r ≤n -1, (C n ) r 中的最长圈之长为n 。较短圈之长l 是n 的因子;

(4) (C n ) r 中有长l 的圈当且仅当d =n l 是n 与r 的公因子。

命题11　设r 与n 的所有公因子为1=d 1

　　　　　　　(C n ) r =k 1C l 1∪k 2C l 2∪…∪k t C lt .

其中长l i 的圈C li 的个数k i >0满足k 1l 1+k 2l 2+…+k t l t =n

r

定理12　设整数l ≤m , 则合成图(C m d ) kd 中长l 的圈之个数等于C m ) k 中长l 的圈之个数。. 上述定理12提供了一个递推方法来计算定理11中的圈数k 1, k 2, …, k t , 于是所有(C n ) r 被完全描述。

设C n 1…, C n k 分别是长n 1…n k 的有向圈, 文[9r 级合成, 引入圈之积的概念, 定理13　(1) r 1…n r , 且有(Cn 1∪…∪C n k ) n -r =(n k ) r n n 1+…+n k ;

(2) (C n 1C k ) r =∪(C n 1) r 1×…(C n k ) r k , 其中不相交圈之并∪取遍r 的所有k 项整数有序分拆:

　　　　　　　r =r 1+…+r k , r 1, …r k ≥0.

由于n 阶置换矩阵P 的伴随图D (P ) 或是一个有向圈C n , 或是多个不相交圈之并; 故定理11, 12, 13用图论方法完全描述了置换矩阵的组合合成。还有一个简要的结论如下:

定理14　设P 是n 阶置换矩阵, 则C r (P ) 是

C n -r (P ) . n r 阶置换矩阵, 且C r (P ) 置换相似于

对稍微复杂的布尔矩阵, 目前只能考虑它的2级组合合成。在有向圈C n 上添加一条从点k 到1的弧得到的有向图记作C n +[k , 1],称为带一条弦的有向圈。文[8]考察了带弦的有向圈的2级合成, 经过繁杂的推导, 得到了简明而有趣的结果。

定理15　对1≤k ≤n , 带弦有向圈的2级合成图(C n +[k , 1]) 2强连通的充要条件是k 与n 互素。

设A n , k =(a ij ) 为n 阶布尔矩阵, a i , i +1=1(i =1, 2, …, n -1) , a n 1=1, a k 1=1, 其它a ij =0; A n , k 正好是C n +[k , 1]的邻接矩阵; 于是有下述结果。

定理16　对1≤k

取两个有向圈C m =x 1x 2…x m x 1和C n =y 1y 2…y n y 1在C m 与C n 之间连两条弧x 1y 1和y k x l , 1≤k ≤n , 1≤l ≤m , 如此得到的有向图记作G (m , n ; k , l ) , 它是有m +n 个顶点和m +n +

m +n m 2条弧的强连通图。文[6]考察了该图的2级合成(G (m , n ; k , l ) 2, 把它的=+　22

　第1期　　　　　　　　　　　　布尔矩阵的组合合成及其图表示31n

+m n 个顶点划分为三个子集;

U ={(x i x 1) 1≤i , j ≤m , i ≠j },V ={(y i y j ) 1≤i , j ≤n , i ≠j },W ={(x i y j ) 1≤i ≤m },1≤j ≤n },

用下述定理刻画了它的结果。

定理17　设[U ]、[V ]、[W ]分别表示顶点集U , V , W 在(G (m , n ; k , l ) ) 2中的诱导子图则(1) [U ]由[m 2]个不相交圈组成, 有m

2条弧; [V ]由[n 2]个不相交圈组成, 有n

条

弧;

(2) [W ]由p 个长q 的不相交圈组成, 有m n +1条弧, 其中p 为m 与n 的最大公约数, q 为m 与n 的最小公倍数,

(3) 从U 到W 和从W 到U 各有m 1; 从V 到W 和从W 到V 各有n -1条弧;

+2(m +n ) -3条弧。　2

此外, 文[6]还给出了(G (m , n ; k , l ) ) 2定理18　(1) 若m 与n 互素, k G ; , l ) ) 2强连通; (2) 设m 与n . d (, ) , G , n ; p -1, p ) ) 2强连通, (3) m 2n ; -m ) ) 2强连通。(4) 2级合成圈(G (m , n ; k , l ) ) 2共有m +n

设图G (m l ) A (m , n ; k , l ) , 文[6]还得到了下述结果。

定理19　设m +n 阶布尔矩阵B ≥A (m , n ; k , l ) , 若下列条件之一满足, 则2级组合合成阵C 2(B ) 是不可约的, 且是本原的;

(1) g . c . d (m , n ) =1, 1≤k ≤n , 1≤l ≤m ;

(2) g . c . d (m , n ) =p ≥2, k =p -l , l =p ;

(3) m ≥1, n ≥2, k =n -1, l =m .

看来, 讨论复杂布尔矩阵A 的组合合成C r (A ) 的组合性质, 还有许多工作可做。我们期望有更多的矩阵类(例如循环矩阵) 的组合合成被探讨。

4　对称布尔矩阵的组合合成

设A 是对称布尔矩阵, 则D (A ) 的每条弧都有反向弧, 故可用一个无向图G (A ) 来代替D (A ) 。类似地, 对应于A 的r 级组合合成(C r (A ) , 可定义无向图G 的r 级合成G r 。对应于命题1和3, 我们有

命题4　设A 是对称布尔矩阵, 则A 不可约当且仅当图G (A ) 连通。

命题5　设A 是对称布尔矩阵, 则C r (A ) 也是对称布尔矩阵, 且G (C r (A ) ) =(G (A ) ) r . 由此可见, 对称布尔矩阵A 的组合合成C r (A ) 的不可约问题转化为考察合成图(G (A ) ) r 的连通性。容易证明, 若无向图G 不连通, 则它的r 级合成图G r 不连通。但是, 有例子表明, 图G 连通还不是G r 连通的充分条件。文[7]仅考察了2级合成图在什么条件下才是连通的, 得到了下述结果。

定理20　设C n 是长n 的无向圈, 则当n 为奇数时2级合成图(C n ) 2的连通; 当n 为偶数是(C n ) 2不连通, 仅有两个分支。

定理21　(1) 若G 是连通的二分图, 则2级合成图G 2不连通;

32数学理论与应用　　　　　　　　　　　　　　　　　第26卷　

(2) 若G 是2-连通图, 且含有奇圈(即G 不是二分图) , 则2级合成图G 2连通。上述两个定理表明, G 含有奇圈是G 2连通的必要条件。但是, 有例子表明, G 的2-连通性不是G 2连通的必要条件。

用图论方法考察对称布尔矩阵A 的2级合合成C 2(A ) , 文[7]还有如下结果。定理22　设A 是对称布尔矩阵, 对角元皆为零, 有2e 个非零元, 则C 2(A ) 恰有e 个非零对角元。

定理23　设A 是n 阶对称布尔矩阵, G (A ) 为2-连通图且含有奇圈, 则2-级组合合成阵C 2(A ) 是不可约的和本原的, 且本原指数Χ(C 2(A ) ) ≤n 2-2n -1.

最后指出, 虽然组合合成阵的结构复杂, 难以考察。但这也为大家提供了丰富的研究领域, 期望有更好的方法和更多的成果出现。

参考文献

[1]　柳柏濂1组合矩阵论[M ]1北京:科学出版社, 19961

[2]　R ichard A . B rualdi , H erbert J . R yser . Com b inato rial atrix []. b U n iversity P ress , 1991.

[3]　R ichard A . B rualdi , L i Q iao . O b atrix [J ]. M ath R es &Expo siti on , 1988, 1:153-162.

[4]　G . J . Zuo . b of p ri m itive m atrix [M ]. Com b inato rics and Graph T heo ry 95-100, pub lished by o Scien tific , Singapo r , 1993.

[5]　左光纪1组合合成阵的本原指数[J ]1应用数学, 1996(增刊) , 86-1011

[6]　左光纪1组合合成阵的不可约性[J ]1青海师大学报, 1998(3) :25-301

[7]　左光纪1对称布尔矩阵的组合合成[J ]1青海师大学报, 2000(2) , 1-41

[8]　左光纪1带弦有向圈的2级合成[J ]1数学研究, 2000(4) :379-3851

[9]　左光纪1置换矩阵的组合合成及其图表示[J ]1数学研究, 2001(1) , 100-1041

[10]　左光纪1组合合成阵本原指数的一个上界[J ]1数学研究, 2005(1) , 89-931