一类（0，1）矩阵的秩

朱雪芳

（台州广播电视大学高职学院，浙江台州318000）

0 引 言

如果矩阵A的元素是0和1，称A为（0，1）矩阵．（0，1）矩阵在组合矩阵论和图论中有广泛的应用［1－4］．很多文献已研究过（0，1）矩阵秩的问题［3，5－6］，本文主要研究线和（即行和与列和）为2的（0，1）矩阵的秩．

全文引入以下记号：记S（n，k）表示线和为k（1≤k≤n－1）的n阶（0，1）矩阵的集合，n和k是正整数，R（n，k）表示属于S（n，k）的矩阵秩的集合．

一个无向图G＝（V，E），其中V为顶点集，E为无向边集．若A＝（aij）表示一个迹为零的n阶对称矩阵，则矩阵A的图用G（A）表示，若G是一个图，则用A（G）＝（aij）表示图G的邻接矩阵，图G中与顶点v关联的边数称为v的度，若图G的每个顶点为k度，则G称为k－正则图．记Cn表示一个循环图，若它的顶点集V＝｛x1，x2，…，xn｝，则它的边仅由｛xi，xi＋1｝（1≤i≤n－1）和｛xn，x1｝连成．

记G（n，k）⊂S（n，k）表示迹为零的对称（0，1）矩阵的集合，r（n，k）表示属于G（n，k）的矩阵秩的集合．

以下先研究R（n，2）．

1 S（n，2）和R（n，2）

引理1［1］令矩阵

则

引理2 若A∈S（n，2），则存在置换矩阵Q和R，使

证明 采用数学归纳法．当n＝2时，结论显然成立．假设当A∈S（r，2），3≤r≤n－1时结论成立．下证当A为n阶矩阵时结论也成立．令A＝（aij）∈S（n，2），由矩阵A的第一行（或第一列）有两个非零元，可以通过置换使矩阵的元素a11＝a12＝a21＝1，而其它的元素a1i＝ai1＝0，i≥3，如果a22＝1，那么存在置换矩阵Q′、R′使

其中A′∈S（n－2，2），根据归纳假设知结论成立；否则如果a22＝0，那么再通过置换使矩阵A的元素a23＝a32＝1，如此不断置换后若ajj＝1，3≤j≤n－2，则存在置换矩阵Q″、R″使

其中A″∈S（n－j，2），根据归纳假设知结论成立；若ajj＝0，则再通过置换使矩阵成为以上情形之一，如此不断置换后an－1，n－1＝1或0，假设an－1，n－1＝1，那么矩阵第n行的行和不为2，这与已知矛盾，所以an－1，n－1＝0，则根据归纳假设知an－1，n＝an，n－1＝1，从而an，n＝1．证毕．

推论1 若A∈S（n，2），则n∈R（n，2），n≥5．

证明 若n是奇数，则矩阵An非奇异，秩（An）＝n，所以n∈R（n，2）．若n是偶数，分两种情形讨论：

情形1n＝2k，k是偶数，令

情形2n＝2k，k是奇数，令

定理1R（2，2）＝｛1｝，R（3，2）＝｛3｝，R（4，2）＝｛2，3｝，R（5，2）＝｛4，5｝，R（6，2）＝｛3，4，5，6｝，R（7，2）＝｛5，6，7｝，R（8，2）＝｛4，5，6，7，8｝，R（9，2）＝｛6，7，8，9｝，R（10，2）＝｛5，6，7，8，9，10｝，R（11，2）＝｛7，8，9，10，11｝，R（12，2）＝｛6，7，8，9，10，11，12｝，R（13，2）＝｛8，9，10，11，12，13｝，R（14，2）＝｛7，8，9，10，11，12，13，14｝，R（15，2）＝｛9，10，11，12，13，14，15｝．

证明 由引理2和推论1易知结论成立，证明略．

定理2

证明 当n（≥6）是偶数时，由引理2和推论1易知结论成立．

下面研究n是奇数及k≥2的情形，当k＝1时，由定理1知结论成立．

若n＝8k＋1，由引理2知最小的R（8k＋1，2）为4k＋2，因8k＋1＝（8k－2）＋3，而R（8k－2，2）＝｛4k－1，4k，…，8k－2｝，所以R（8k＋1，2）＝｛4k＋2，4k＋3，…，8k＋1｝．

若n＝8k＋3，由引理2知最小的R（8k＋3，2）为4k＋3，因8k＋3＝（8k）＋3，而R（8k，2）＝4k｛，4k＋1，…，8k｝，所以R（8k＋3，2）＝｛4k＋3，4k＋4，…，8k＋3｝．

若n＝8k＋5，由引理2知最小的R（8k＋5，2）为4k＋4，因8k＋5＝（8k＋2）＋3，而R（8k＋2，2）＝｛4k＋1，4k＋2，…，8k＋2｝，所以R（8k＋5，2）＝｛4k＋4，4k＋5，…，8k＋5｝．

若n＝8k＋7，由引理2知最小的R（8k＋7，2）为4k＋5，因8k＋7＝（8k＋4）＋3，而R（8k＋4，2）＝｛4k＋2，4k＋3，…，8k＋4｝，所以R（8k＋7，2）＝｛4k＋5，4k＋6，…，8k＋7｝．

下面再研究r（n，2）．

2 G（n，2）和r（n，2）

引理3［2，4］若G＝（V，E）是正则度为2的连通图，则G和Cn同构．

推论2［2，4］若G＝（V，E）是一个2－正则图，则G是圈的集合．

引理4［1］令Cn（n≥3）表示以下矩阵

则

推论3 若C∈G（n，2），则n∈r（n，2），n≥5．

证明 若n是奇数，则矩阵Cn非奇异，秩（Cn）＝n，所以n∈r（n，2）；若n是偶数，分两种情形讨论：

情形1n＝2k，k是偶数，令

情形2n＝2k，k是奇数，令

定理3r（3，2）＝｛3｝，r（4，2）＝｛2｝，r（5，2）＝｛5｝，r（6，2）＝｛6｝，r（7，2）＝｛5，7｝，r（8，2）＝｛4，6，8｝，

r（9，2）＝｛7，9｝，r（10，2）＝｛8，10｝，r（11，2）＝｛7，9，11｝，r（12，2）＝｛6，8，10，12｝．

证明 由引理4和推论3易知结论成立，证明略．

定理4

证明 若n＝8k，由推论3，可知最小的r（8k，2）是4k，而8k＝4×2k，所以r（8k，2）＝｛4k，4k＋2，…，8k｝．

若n＝8k＋2，由推论3，可知最小的r（8k＋2，2）是4k＋4，而8k＋2＝（8k－8）＋10，因r（8k－8，2）＝｛4k－4，4k－2，…，8k－8｝，所以r（8k＋2，2）＝｛4k＋4，4k＋6，…，8k＋2｝．

其余的证明类似，证明略．

［1］Fallat S，Driessche P D．Maximum determinant of（0，1）matrices with certain constant row and column sums［J］．Linear and Multilinear Algebra，1997，42（4）：303－318．

［2］Brualdi R A，Ryser H J．Combinatorial matrix theory［M］．London：Cambridge University Press，1991：23－38．

［3］Berman A，Plemmons R J．Nonnegative matrices in the mathematical sciences［M］．London：Academic Press，1978：98－105．

［4］West D B．Introduction to graph theory［M］．Upper Saddle River：Prentice Hall，1996：78－90．

［5］Hu Qi，Li Yaqin，Zhan Xingzhi．Possible numbers of ones in 0－1matrices with given rank［J］．Linear and Multilinear Algebra，2005，53（6）：435－443．

［6］Sierksma G，Sterken E．The structure matrix of（0，1）matrices：its rank，trace，and eigenvalues．An application to econometnic models［J］．Linear Algebra Appl，1986，83：151－166．