幂零布尔矩阵及其积和式的图论属性*

韦扬江，邢 悦，张小凤，周美江，陶冰雨

(南宁师范大学 数学与统计学院，广西 南宁 530100)

1 引言

布尔矩阵是仅由0和1组成的矩阵，它在计算机网络、通信工程、逻辑学、图论、布尔网络等领域有着广泛的应用.很多学者对布尔矩阵进行了多方面的研究.早在1982年，Kim在[1]中就收集了大量关于布尔矩阵的研究成果.文献[2-5]从代数和图论的角度研究了幂等布尔矩阵，文献[6，7]研究了布尔矩阵的平方根.但目前关于幂零布尔矩阵的研究结果较少，文献[8，9]用代数方法对交换反环上的幂零矩阵进行了若干研究.

本文在文献[8]的基础上进一步研究幂零布尔矩阵：给出了布尔矩阵的积和式为1图论刻画；根据幂零布尔矩阵的图结构获得其伴随矩阵对应的有向图，进而构造伴随矩阵，并得到了幂零布尔矩阵的伴随矩阵的一些性质；对[8]中的两个相关结论，在布尔矩阵的情形给出了较为简单的证明.

2 相关定义

半环是一个代数系统(S,+, ·)，其中(S,+)是以0为单位元的交换幺半群，(S, ·)是以1为单位元的幺半群.如果在S中由a+b=0可推出a=b=0，则称S是一个反环(antiring).在集合B={0,1}上定义二元运算“+”和“·”如下：0+0=0，1+1=1+0=0+1=1，1·1=1，0·0=0·1=1·0=0.易见(B,+, ·)是一个反环，称为布尔半环,其上的一个m×n矩阵称为布尔矩阵，这样的m×n矩阵的集合用Mm×n(B)表示.简记Mn×n(B)为Mn(B).用Aij或aij表示矩阵A=(aij)的(i,j)-元.布尔矩阵的运算与一般数域上的矩阵的运算相同，其区别在于布尔矩阵中规定1+1=1.如果存在正整数k使得布尔矩阵A满足Ak=0，则称A是幂零的.

令S为反环，对于矩阵A=(aij)∈Mn(S)，定义有向图D(A)=(V,E),其中顶点集V={1,2,…,n}，边集E={(i,j)|aij≠0}.若ai0i1≠0，ai1i2≠0,…,aim-1im≠0，则称P:i0→i1→…→im是一条长度为m的路；……