朱雪芳

（臺州廣播電視大學高職學院，浙江臺州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是正整數(shù)，R（n，k）表示屬于S（n，k）的矩陣秩的集合．

一個無向圖G＝（V，E），其中V為頂點集，E為無向邊集．若A＝（aij）表示一個跡為零的n階對稱矩陣，則矩陣A的圖用G（A）表示，若G是一個圖，則用A（G）＝（aij）表示圖G的鄰接矩陣，圖G中與頂點v關聯(lián)的邊數(shù)稱為v的度，若圖G的每個頂點為k度，則G稱為k－正則圖．記Cn表示一個循環(huán)圖，若它的頂點集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，使

證明 采用數(shù)學歸納法．當n＝2時，結(jié)論顯然成立．假設當A∈S（r，2），3≤r≤n－1時結(jié)論成立．下證當A為n階矩陣時結(jié)論也成立．令A＝（aij）∈S（n，2），由矩陣A的第一行（或第一列）有兩個非零元，可以通過置換使矩陣的元素a11＝a12＝a21＝1，而其它的元素a1i＝ai1＝0，i≥3，如果a22＝1，那么存在置換矩陣Q′、R′使

其中A′∈S（n－2，2），根據(jù)歸納假設知結(jié)論成立；否則如果a22＝0，那么再通過置換使矩陣A的元素a23＝a32＝1，如此不斷置換后若ajj＝1，3≤j≤n－2，則存在置換矩陣Q″、R″使

其中A″∈S（n－j，2），根據(jù)歸納假設知結(jié)論成立；若ajj＝0，則再通過置換使矩陣成為以上情形之一，如此不斷置換后an－1，n－1＝1或0，假設an－1，n－1＝1，那么矩陣第n行的行和不為2，這與已知矛盾，所以an－1，n－1＝0，則根據(jù)歸納假設知an－1，n＝an，n－1＝1，從而an，n＝1．證畢．

推論1 若A∈S（n，2），則n∈R（n，2），n≥5．

證明 若n是奇數(shù)，則矩陣An非奇異，秩（An）＝n，所以n∈R（n，2）．若n是偶數(shù)，分兩種情形討論：

情形1n＝2k，k是偶數(shù)，令

情形2n＝2k，k是奇數(shù)，令

定理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易知結(jié)論成立，證明略．

定理2

證明 當n（≥6）是偶數(shù)時，由引理2和推論1易知結(jié)論成立．

下面研究n是奇數(shù)及k≥2的情形，當k＝1時，由定理1知結(jié)論成立．

若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同構(gòu)．

推論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是奇數(shù)，則矩陣Cn非奇異，秩（Cn）＝n，所以n∈r（n，2）；若n是偶數(shù)，分兩種情形討論：

情形1n＝2k，k是偶數(shù)，令

情形2n＝2k，k是奇數(shù)，令

定理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易知結(jié)論成立，證明略．

定理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．