圍長為2的本原無限布爾方陣類的本原指數集

張德全,李修清

(桂林航天工業高等?？茖W校計算機系,廣西桂林 541004)

圍長為2的本原無限布爾方陣類的本原指數集

張德全,李修清

(桂林航天工業高等專科學校計算機系,廣西桂林 541004)

研究了圍長為2的無限布爾方陣的本原性,通過無限有向圖D(A)的直徑給出了這類矩陣的本原指數的上確界,最后證明了直徑小于等于d且圍長為2的本原無限布爾方陣所構成的矩陣類的本原指數集為={2,3,…,3d}.

無限布爾方陣;本原指數;有向圖;直徑

1 引言

設β={0,1}是由兩個元素所組成的布爾代數,具有布爾加法:a+b=max{a,b}和布爾乘法:a·b=min{a,b},這里β={0,1}中約定0＜1.定義在β={0,1}上的具有無限行和無限列的矩陣稱為無限布爾方陣.按通常矩陣的加法、數量乘法和矩陣乘法,我們給出無限布爾方陣的加法,數量乘法和乘法的定義.

定義1設A=(aij),B=(bij)都是無限布爾方陣,λ∈β,

由無限布爾方陣的乘法定義,無限布爾方陣的冪運算是有意義的,設A是一個無限布爾方陣,若存在有限的正整數k,使Ak＞0(即Ak中的每個元素均為1),則稱A是本原無限布爾方陣(簡稱本原的),使Ak＞0成立的最小正整數k稱為A的本原指數,記作γ(A)=k.設A=(aij)是一個無限布爾方陣,則A可自然地對應一個無限階有向圖D(A)=(V,E),其中V={v1,…,vn,…}是頂點集,E是弧集,aij=1當且僅當有弧(vi,vj)∈E(i,j=1,2,… ),稱為A的伴隨有向圖,顯然有向圖D(A)=(V,E)中可以有自環,但沒有重復弧.

無限布爾方陣的本原性可以自然地用圖的語言表述,設D是一個無限階有向圖(圖中允許有自環,但不允許有重復弧),若存在有限的正整數k,使得任取圖中兩點i,j,對于任意一個≥k的正整數m,都有點i到點j長為m的途徑,且圖D中存在兩點u,v,使得點u到點v沒有長為k?1的途徑,則稱D是本原有向圖,且稱k為D的本原指數,記作γ(D)=k.顯然,A是本原無限布爾方陣的充分必要條件是A的伴隨有向圖D(A)為本原有向圖,且γ(A)=γ(D(A))；因此研究無限布爾方陣的本原性及其本原指數集就完全等同于研究相應的伴隨有向圖的本原性及其指數集.

若A=(aij)是一個無限布爾方陣,且主對角線上的元素均為零且至少有一對非零對稱元,則A對應的伴隨有向圖D(A)=(V,E)是一個沒有自環且最小圈長為2的無限階有向圖,我們將一個圖的最小圈長稱為這個圖的圍長,這樣主對角線上的元素均為零且至少有一對非零對稱元的無限布爾方陣的伴隨有向圖是一個圍長為2的無限階有向圖,反之一個圍長為2的無限階有向圖的鄰接矩陣也是一個主對角線上的元素均為零且至少有一對非零對稱元的無限布爾方陣.

通過D(A)的直徑估計本原矩陣A的本原指數是一個十分有意義的課題,關于n階本原矩陣的本原指數,文[2]給出了n階對稱本原矩陣本原指數的上界估計:γ(D)≤2d,文[3]給出了一般的n階本原矩陣的本原指數上界估計:γ(A)≤d2+1,其中d為D(A)的直徑.但對于無限布爾方陣A通過D(A)的直徑來估計A的本原指數及本原指數集等問題的研究還很不深入,文[1]中研究了含有非零對角元的無限布爾方陣,通過D(A)的直徑給出了其本原指數的上界估計,并給出了這類矩陣的本原指數集的刻劃,文[4]中研究了對稱無限布爾方陣,并通過D(A)的直徑給出了對稱本原無限布爾方陣的本原指數集的刻劃.本原指數研究的另一個方面是對各種特殊的本原矩陣類的本原指數以及本原指數集的研究.本文研究主對角線上的元素均為零且至少有一對非零對稱元的一類無限布爾方陣,即伴隨有向圖D(A)的圍長為2的一類無限布爾方陣,記這類方陣的集合為B0,即B0={A|A是無限布爾方陣,且伴隨有向圖D(A)的圍長為2};本文研究這類無限階布爾方陣的本原性,通過伴隨有向圖D(A)的直徑給出本原指數的上確界,最后給出直徑小于等于d的圍長為2的本原無限布爾方陣所構成的矩陣類的本原指數集的刻劃.

2 B0中無限布爾方陣為本原陣的一個充分必要條件

設D是一個無限階有向圖,i,j是圖中的兩個頂點,k是一個正整數,若從頂點i到頂點j有長為m≥k(其中m是大于或等于k的任意一個正整數)的途徑,但從頂點i到頂點j沒有長為k?1的途徑,則稱k為頂點i到頂點j的局部本原指數,記作γ(i,j)=k;由以上對無限階有向圖D的本原性以及圖D的本原指數的定義,顯然可得:

命題2設D是一個無限階有向圖,則D是本原的當且僅當集合{γ(i,j)|i,j∈V(D)}是有限集,且當D是本原圖時有γ(D)=max{γ(i,j)|i,j∈V(D)}.

設D(A)=(V,E)是無限布爾方陣A的伴隨有向圖,i,j是圖中的任意兩個頂點(這兩點可以相同也可以不同),若既有從頂點i到頂點j的長度有限的途徑,也有從頂點j到頂點i的長度有限的途徑,則稱圖D(A)是強連通圖,稱A為不可約無限布爾方陣(簡稱不可約的);本文用d(i,j)表示頂點i到頂點j的距離,若集合{d(i,j)|i,j∈V(D)}是有界集,則稱D(A)具有有限的直徑,并稱max{d(i,j)|i,j∈V(D)}為D(A)的直徑,記作d(D(A));為了方便我們將有向圖D(A)具有有限直徑也稱為A具有有限的直徑,將D(A)的直徑也稱為A的直徑;用RD(A)表示D(A)的所有有限圈(有限圈:即長度有限的圈)的長度的集合,即RD(A)={r|r為D(A)中有限圈的長度}.

下面給出B0中無限布爾方陣為本原陣的一個等價刻劃.首先給出Schur的一個引理.

引理1[5](Schur)設k≥2,ri(i=1,2,…,k)是正整數,且gcd(r1,r2,…,rk)=1,則存在僅與r1,r2,…,rk有關的非負整數N(r1,r2,…,rk),當n≥N(r1,r2,…,rk)時,方程r1x1+…+rkxk=n有非負整數解.

我們把使引理1成立的最小的非負整數N(r1,r2,…,rk)記作φ(r1,r2,…,rk),稱為r1,r2,…,rk的Frobenius數,特別當k=2時有:φ(r1,r2)=(r1?1)(r2?1).

設R={r1,r2,…,rk}?RD是無限階有向圖D中k個不同的圈長,且gcd(r1,r,…,rk)= 1,D中從頂點i到頂點j且和長度分別為r1,r2,…,rk的圈都接觸(只要和一個長為r的圈有公共點就稱為接觸了長為r的圈)的最短途徑長記為dR(i,j),稱為從頂點i到頂點j的相應于R的廣義相對距離,記φR為r1,r2,…,rk的Frobenius數,即φR=φ(r1,r2,…,rk),則顯然頂點i到頂點j有長為m的途徑,其中m大于等于dR(i,j)+φR的任意一個正整數,從而由局部本原指數的定義有:γ(i,j)≤dR(i,j)+φR.即

引理2設R={r1,r2,…,rk}?RD是無限階有向圖D中k個不同的圈長,且gcd(r1,r2, …,rk)=1,任取D中i,j兩點,則頂點i到頂點j有長為m≥dR(i,j)+φR的途徑,從而有γ(i,j)≤dR(i,j)+φR.

文[1]中給出了無限布爾方陣為本原陣的一個等價刻劃.

定理1[1]設A是一個無限布爾方陣,D(A)是A的伴隨有向圖,RD={D(A)中所有有限圈的長度},則A是本原陣的充分必要條件為:

(i)D(A)是強連通有向圖;

(ii)D(A)有有限直徑,存在RD中的有限元素r1,r2,…,rk且滿足gcd(r1,r2,…,rk)=1.

由定理1,我們易給出B0中的無限布爾方陣為本原陣的一個充分必要條件.

定理2設A∈B0,D(A)是A的伴隨有向圖,則A是本原陣的一個充分必要條件為:

(i)D(A)是強連通有向圖;

(ii)D(A)具有有限的直徑,且D(A)含有奇圈.

3 PB0中直徑為d的無限布爾方陣的本原指數的上確界

情形1若y1和y2中至少有一個為0,不妨設y1=0,則有x1+k0≡2k0?y1≡0(mod 2),即x1+k0＜2k0且為偶數,由上述討論知在圖D(A)中存在一條u0點到u2點的長度為x1+k0的偶途徑,矛盾.

情形2若y1和y2均為1,則x1+x2≡2k0?(y1+y2)≡0(mod 2),即x1+x2是一個小于2k0的偶數,則同樣u0點到u2點存在一條長度為x1+x2的偶途徑,矛盾.

于是我們就證明了假設是錯誤的,故定理結論成立.

定理3設A∈PB0,且D(A)的直徑為d,則γ(A)≤3d,并且上界是可以達到的.

證明因為A∈PB0,由定理2知D(A)具有有限的直徑,設D(A)的直徑為d,由A∈PB0知,D(A)是一個沒有自環且至少含有一個2圈的本原圖,設D(A)的一個2圈為Γ2,且設Γ2上的兩個點為i,j,則i,j點在圖D(A2)中均有自環,由引理3知D(A2)的直徑≤d,于是圖D(A2)中i點或j點到圖D(A2)中的任何一點都有長度恰為d的途徑,從而在圖D(A)中i點和j點到圖D(A)中的任何一點都分別有長度恰為2d的途徑;在圖D(A)中任取兩點u,v,由于D(A)的直徑為d,易知從u點用長度恰為m≥d(m是不小于d的任意一個正整數)的途徑可以到達圖D(A)中的i點或j點,而i點或j點又可用長度恰為2d的途徑到達圖D(A)中的v點,于是對于圖D(A)的任意兩點u,v,u點到v點都存在長度恰為m+2d(m≥d是任意一個正整數)的途徑,于是由局部本原指數的定義得:γ(u,v)≤3d,注意到u,v兩點的任意性得γ(A)≤3d;上界的可達性證明由下一節給出.

4 無限布爾方陣類PB0的本原指數集的刻劃

定理4={2,3,…,3d}(d≥3).

本文我們使用下列記號:設D是一個無限階有向圖,用(i,j)表示頂點i到頂點j的一條弧,[i,j]表示頂點i到頂點j之間的雙向連通邊,即一個2圈.

定理5{2,3,…,d+1,d+2}?(d≥3).

證明(1)設3≤k≤d(d≥3),考慮下列無限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),(2,3),…,(k?2,k?1),[k?1,k];(k,1),(k,2),…,(k,k?2); [k,k+1],[k,k+2],[k,k+3],…}.易知,圖D=D(V,E)強連通,沒有自環,有2圈和3圈,且直徑≤d,即D=D(V,E)的鄰接無限布爾方陣A∈P;取圖D=D(V,E)中圈長為2和3的集合R={2,3},則由引理1知,Frobenius數φR=2,考慮圖中1點和k+1點,顯然dR(1,k+1)=k,于是由引理2知γ(1,k+1)≤k+2,但1點到k+1點顯然沒有長為k+1的途徑,故有γ(1,k+1)=k+2,另一方面易知dR(i,j)≤k(i,j=1,2,3,…),于是有γ(i,j)≤k+2(i,j=1,2,3,…),故有γ(D)=k+2(3≤k≤d),即{5,6,…,d+1,d+2}?;

(2)考慮主對角線上的元素均為零,其余元素均為1的無限布爾方陣A,易知γ(A)= 2即2∈;

(3)考慮下列無限有向圖D=D(V,E),其中E={[1,2],(3,1);[i,j](i/=j且i,j= 2,3,…)},V={1,2,…,d,…}.顯然D=D(V,E)強連通,沒有自環,有2圈和3圈,且直徑為2,則D所對應的鄰接無限布爾方陣A∈P;易驗證A和A2都不是全1矩陣,而A3是全1矩陣,于是γ(A)=3即γ(D)=3,所以3∈

(4)考慮下列無限有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];[2,3],[2,4],[2,5],…;[3,4]}.顯然圖D=D(V,E)強連通,沒有自環,有2圈和3圈,且直徑為2,即所對應的無限布爾方陣A∈P;取圖D=D(V,E)中圈長的集合R={2,3},考慮圖中1點和5點,顯然dR(1,5)=2,Frobenius數φR(2,3)=2,于是γ(1,5)≤4,但顯然1點到5點沒有長為3的途徑,故有γ(1,5)=4,另一方面顯然dR(i,j)≤2(i,j=1,2,3,…),于是有γ(i,j)≤4(i,j=1,2,3,…),故γ(D)=4,即4∈.

定理6{d+3,d+4,…,2d}?(d≥3).

證明設3≤k≤d(d≥3),考慮下列無限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={[1,2],[2,3],[3,4],…;[k?2,k?1],[k?1,k];(k,k+1),(k+1,k+2),…,(d?1,d),(d,d+1);(d+1,1);(3,1),(4,2),…,(k,k?2);[2,d+2],[2,d+3],[2,d+4],…}.易知,圖D= D(V,E)強連通,沒有自環,有2圈和3圈,且直徑=d,即D=D(V,E)的鄰接無限布爾方陣A∈P;取圖D=D(V,E)中圈長為2和3的集合R={2,3},則Frobenius數φR=2,考慮圖中k+1點和d+1點,顯然dR(k+1,d+1)=(d?k)+(d+1),由引理2知,γ(k+1,d+1)≤2d?k+3,顯然k+1點到d+1點沒有長為2d?k+2的途徑,故有γ(k+1,d+1)=2d?k+3;另一方面顯然dR(i,j)≤2d?k+1(i,j=1,2,3,…),于是有γ(i,j)≤2d?k+3(i,j=1,2,3,…),故有γ(D)=2d?k+3(3≤k≤d),即{d+3,d+4,…,2d}?,(d≥3).

定理7當d為奇數時,{2d+1,2d+2,…,3d}?,(d≥3).

證明(1)設4≤k≤d+2(d≥3),考慮下列無限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),[2,3],(3,4);[4,5],[5,6],…,[k?2,k?1];(k?1,k),(k,k+1), (k+1,k+2),…,(d,d+1),(d+1,d+2);(1,3),(2,4);(d+2,1);[3,3+d],[3,d+4],[3,d+ 5],…;(d+3,1),(d+4,1),(d+5,1),…}.易知,圖D=D(V,E)強連通,沒有自環,有2圈和只有長為d+2的奇圈,且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長為2和d+2的集合R={2,d+2},則由引理2知,Frobenius數φR=d+1,考慮圖中k點和d+2點,顯然dR(k,d+2)=(d+2?k)+(d+1),于是由引理2知γ(k,d+2)≤3d?k+4,易知k點到d+2點沒有長為3d?k+3的途徑,故有γ(k,d+2)=3d?k+4,另一方面易證dR(i,j)≤2d?k+3(i,j=1,2,3,…),于是有γ(i,j)≤3d?k+4(i,j=1,2,3,…),故有γ(D)=3d?k+4(4≤k≤d+2),即{2d+2,2d+3,…,3d}?,(d≥3);

(2)考慮下列無限階有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];(2,3), (3,4),…,(d?1,d),(d,d+1);(d+1,1);[2,d+2],[2,d+3],[2,d+4],…;[1,d+2],[1,d+3],[1,d+ 4],…}.易知,圖D=D(V,E)強連通,沒有自環,有2圈和3圈,且直徑=d,即D=D(V,E)的鄰接無限布爾方陣A∈P;取圖D=D(V,E)中圈長的集合R={2,3},則Frobenius數φR= 2,考慮圖中3點和d+1點,顯然dR(3,d+1)=(d?2)+(d+1),于是γ(3,d+1)≤2d+1,且易知3點到d+1點沒有長為2d的途徑,故有γ(3,d+1)=2d+1,另一方面易證dR(i,j)≤2d?1(i,j=1,2,3,…),于是有γ(i,j)≤2d+1(i,j=1,2,3,…),故有γ(D)=2d+1,即2d+1∈(d≥3);綜合(1),(2)就證明了,當d為奇數時{2d+1,2d+2,…,3d}?,(d≥3且為奇數).

定理8當d為偶數時,{2d+1,2d+2,…,3d}?,(d≥3).

證明(1)4≤k≤d+2(d≥3),考慮下列無限階有向圖D=D(V,E),其中V= {1,2,…,d,…},E={(1,2),[2,3],(3,4);[4,5],[5,6],…,[k?2,k?1];(k?1,k),(k,k+1),…,(d, d+1),(d+1,d+2);(1,3),(2,4);(d+2,1);[3,d+3],[3,d+4],[3,d+5],…;(d+3,1),(d+ 4,1),(d+5,1),…}.易知,圖D=D(V,E)強連通,沒有自環,有2圈,且只有長為d+1的奇圈且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長為2和d+1的集合R={2,d+1},則Frobenius數φR=d,考慮圖中k點和d+2點,顯然dR(k,d+2)=(d+2?k)+(d+1),于是γ(k,d+2)≤3d?k+3,且易知k點到d+2點沒有長為3d?k+2的途徑,故有γ(k,d+2)=3d?k+3,另一方面易證dR(i,j)≤3d?k+3(i,j= 1,2,3,…),于是有γ(i,j)≤3d?k+3(i,j=1,2,3,…),故有γ(D)=3d?k+3(4≤k≤d+2),即{2d+1,2d+2,…,3d?1}?,(d≥3).

(2)考慮下列無限階有向圖D=D(V,E),其中V={1,2,…,d,…},E={[1,2];(2,3), (3,4),…,(d?1,d),(d,d+1),(d+1,d+2);(1,3);(d+2,1),(d+2,2);[2,d+3],[2,d+4],[2,d+ 5],…;(d+3,3),(d+4,3),…;(d+2,d+3),(d+2,d+4),(d+2,d+5),…}.易知,圖D= D(V,E)強連通,沒有自環,有2圈,且只有長為d+1的奇圈,且直徑=d,即D=D(V,E)的鄰接方陣A∈P;取圖D=D(V,E)中圈長的集合R={2,d+1},則Frobenius數φR=d,考慮圖D=D(V,E)中3點和d+2點,顯然dR(3,d+2)=(d?1)+(d+1),于是γ(3,d+2)≤3d,且易知3點到d+2點沒有長為3d?1的途徑,故有γ(3,d+2)=3d,另一方面易證dR(i,j)≤2d(i,j=1,2,3,…),于是有γ(i,j)≤3d(i,j=1,2,3,…),故有γ(D)=3d,即3d?,(d≥3).(且d為偶數);

綜合(1)、(2)就證明了,當d為偶數時,{2d+1,2d+2,…,3d}?(d≥3且d為偶數).綜合定理5到定理8我們就證明了定理4的結論成立.

[1]李修清,王敏.一類本原無限布爾方陣的本原指數集的刻劃[J].數學的實踐與認識,2007,37(1):100-103.

[2]Delorme C,Sole P.Diameter,covering index,covering radius and eigenvalues[J].Europ.J.Combinatorics, 1991,12:93-108.

[3]Jian Shen.Proof of a conjecture about the exponent of primitive matrices[J].Linear Algebra Appl.,1995, 216:185-203.

[4]李修清,王敏.對稱無限布爾方陣的本原指數集的刻劃[J].系統科學與數學,2008,28(12):1478-1485

[5]柳柏濂.組合矩陣論[M].北京:科學出版社,1996.

On primitive exponent set for the class of primitive infinite Boolean matrices with girth 2

ZHANG De-quan,LI Xiu-qing
(Department of Computer Science,Guilin College of Aerospace Technology,Guilin541004,China)

This paper studies the primitiveness of infinite Boolean matrices with girth 2.And it offers the least upper bound of the primitive exponent through the diameter of the infinite digraph D(A).In the end we completely determine the primitive exponent set of the matrices which are class of primitive infinite Boolean matrices with girth 2 and whose diameters are not more than d is={2,3,…,3d}.

infinite Boolean matrices,primitive exponent,digraph,diameter

O157.5

A

1008-5513(2009)03-0464-06

2008-12-30.

廣西區教育廳科研項目(桂教科研[2006]26號).

張德全(1959-),副教授,研究方向：組合數學.

2000MSC:05C50