兩類本原不可冪定號有向圖基的界?

胡紅萍

(中北大學(xué) 理學(xué)院,山西 太原 030051)

0 引 言

元素取自于集合 {+,-,0}的矩陣稱為符號模式矩陣,簡稱符號模式.Qn表示所有 n×n的符號模式的集合.設(shè) A=(aij)∈Qn,則 A的定性矩陣類定義為 Q(A)={B∈Mn(R)|sgn(B)=A}.類似于普通矩陣的運算,符號模式矩陣也具有相應(yīng)的運算,都歸結(jié)為元素的運算,即+,-,0的運算形式;但當(dāng)“+”加“-”時,會出現(xiàn)“未定元”,記作#.稱集合Γ={+,-,0,#}為廣義符號集,元素取自于集合Γ的矩陣稱為廣義符號模式矩陣,簡稱廣義符號模式.

設(shè) A=(aij)∈ Qn是 n階符號模式,頂點集為 V={1,2,… ,n}和弧集為 E={(i,j)|aij≠0}的有向圖稱為 A的伴隨有向圖(可能有環(huán)),記為 D(A).將 D(A)中每條弧(i,j)賦予 aij得到的圖稱為 A的伴隨定號有向圖,記為 S(A).反過來,給出一個 n階定號有向圖 S,一定存在 n階符號模式矩陣 A,使得 A的伴隨定號有向圖是 S.因此符號模式矩陣和定號有向圖之間存在一一對應(yīng)的關(guān)系.

設(shè) D是有向圖,若(i0,i1),(i1,i2),… ,(ik-1,ik)是 D的弧,則弧的序列(i0,i1),(i1,i2),… ,(ik-1,ik)稱為 D的一條途徑,記為 W：(i0,i1),(i1,i2),…,(ik-1,ik).k稱為途徑的長度,記為 l(W).

關(guān)于 D(A)的有關(guān)概念也可以運用到矩陣 A=(aij)中,這樣 A的途徑 W定義為形式 ai0,i1ai1,i2,…,aik-1,ik,其中每一項都是非零的.類似地,可以定義 A的閉途徑,簡單圈的概念和長度及符號的概念.

設(shè) S是定號有向圖,若兩條途徑 W1和 W2有相同的起點,有相同的終點和相同的長度,但有不同的符號,則稱 W1和 W2是 SSSD途徑對.

設(shè) a1,a2,… ,ak是正整數(shù),定義 Froaenius集合

由 Schur引理可知,若 g.c.d(a1,a2,… ,an)=1,那么 S(a1,a2,… ,an)包含了所有充分大的正整數(shù).

Froaenius數(shù)h(a1,a2,… ,an)定義是最小的正整數(shù) h,使得任何整數(shù) m≥h都有 m∈ S(a1,a2,… ,an)成立.顯然由此定義有 h(a1,a2,… ,an)-1? S(a1,a2,… ,an).若 a,b是正整數(shù),且 g.c.d(a,b)=1,則h(a,b)=(a-1)(b-1).

設(shè) A是廣義符號模式矩陣,若存在某個正整數(shù) k,使得 Ak中含# 元素,則稱 A是不可冪的.

設(shè) A是 n階廣義符號模式矩陣,考慮序列 A1=A,A2,A3,因為僅有 4n2個不同的 n階廣義符號模式矩陣,所以在這個序列中一定有重復(fù)的.設(shè) Al是第一個被重復(fù)的矩陣,記 Al=Al+p,其中 p＞0是最小的,則稱 l為 A的基(記為 l(A)),p稱為 A的周期(記為 p(A)).

為了方便起見,人們也對定號有向圖定義相應(yīng)的概念.設(shè) S是 n階定號有向圖,則一定存在 n階符號模式矩陣 A,使得其定號有向圖 S(A)是 S.若 A是不可冪的,則 S是不可冪的.也將 A的基和周期的概念定義為 S的基和周期.

設(shè) B是非負矩陣,若存在正整數(shù) k,使得 Bk＞0,則稱 B是本原矩陣.k的最小值稱為 B的本原指數(shù),記為 exp(B).設(shè) A是廣義符號模式,將 A的每個非零元素用+ 代替之后得到的非負矩陣記為|A|.若|A|是本原的,則稱|A|是本原的,在此情形下定義 exp(A)=exp(|A|).

設(shè)有向圖 D,若存在正整數(shù) k,使得 D的任何兩個頂點 x和 y(不必不同)在 D中都存在從頂點 x到頂點 y的長為 k的途徑,則稱 D為本原有向圖,k的最小值稱為 D的本原指數(shù),記為 exp(D).眾所周知,有向圖 D是本原的,當(dāng)且僅當(dāng) D是強連通的,且 D的所有圈長的最大公因式等于 1.由矩陣與圖之間的關(guān)系,有矩陣 A是不可約的,當(dāng)且僅當(dāng) D(A)是強連通的;A是本原矩陣,當(dāng)且僅當(dāng)是本原有向圖.此時,exp(A)=exp(D).

設(shè) R={l1,l2,… ,,lr}是本原有向圖 D的圈長的集合,且 g.c.d(l1,l2,… ,lr)=1,x,y是 D的兩個頂點,d(x,y)表示從頂點 x到頂點 y的距離,dR(x,y)表示至少接觸長為 li(i=1,2,…,r)的圈一次的最短途徑的長度.設(shè) hR=h(l1,l2,… ,lr)是 Froaenius數(shù),則

和

本文主要研究兩類特殊本原不可冪的定號有向圖(其基礎(chǔ)有向圖分別為 Ds,t和 Ds,t,q(分別見圖 1和圖 2)的基的界,其中：圖 1中 s＞t和 2≤m≤s,圖 2中 s,t,q中有兩個相同.

圖1 有向圖 Ds,t(s＞t)Fig.1 Digraph Ds,twhere s＞t

圖2 有向圖 Ds,t,qFig.2 Dig raph Ds,t,q

1 引 理

引理 1[2]若 S是本原的定號有向圖,則 S是不可冪的,當(dāng)且僅當(dāng) S包含的一對圈 C1和 C2(圈長分別為 p1和 p2)滿足 p1是奇數(shù),p2是偶數(shù),且 sgn C2=-;或者 p1和 p2是奇數(shù),且 sgn C1=-sgn C2.

滿足引理 1的圈對 C1和 C2稱為“異圈對”.若 C1和 C2是長分別為 p1和 p2的異圈對,則閉圈對 W1=p2C1和 W2=p1C2有相同的長度 p1,p2,但有不同的符號

引理 2[2]設(shè) S是本原不可冪的定號有向圖,則

1)存在整數(shù) k,使得 S的任兩個頂點 x和 y之間存在長為 k的 SSSD途徑對;

2)若 S的任兩個頂點 x和 y之間存在長為 k的 SSSD途徑對,則 S的任兩個頂點 x和 y之間存在長為 k+1的 SSSD途徑對;

3)k的最小值是 S的基,即 l(S).

2 主要結(jié)論

定理 1 設(shè) S是 n=t+m-1階本原不可冪的定號有向圖,其中 Ds,t(s＞t)(見圖 1)是 S的基礎(chǔ)有向圖,則 l(S)=2st-t+(m-1).

證明 首先證明 S中從頂點 1到頂點 m-1不存在長為 k=2st-t+(m-2)的 SSSD途徑對.設(shè) P是從頂點 1到頂點 m-1的路,假設(shè) W1和 W2是從頂點 1到頂點 m-1的長為 k的途徑,顯然每條途徑Wi(i=1,2)是路 P和幾個圈的“并”.因為 k＞m-2,所以每個“并”至少含一個圈 Cs.取 Wi=P+aiCi+biCs(bi≥ 1,ai≥ 0,i= 1,2), 有 k=l(Wi)=(m-2)+ tai+ sbi(bi≥ 1,ai≥ 0,i= 1,2), 故(b2-b1)s=(a1-a2)t.因為 s和 t的最大公因式為 1,所以記 a1-a2=sx,則有 b2-b1=tx,一定有 x=0.若 x≥ 1,則b2=b1+tx≥1+t,且 k=(m-2)+ta2+sb2=(m-2)+ta2+ [b2-(1+t)]s+(1+t)s.因為 S是本原的,且 Cs,Ct是 S中長分別為 s,t的僅有的兩個圈,所以 h(s,t)-1=a2t+ [b2-(1+t)]s∈ S(s,t)與Froaenius數(shù)h(s,t)的定義矛盾.類似地,若 x≤-1,也得到一個矛盾,因此一定有 x=0,故 a1=a2,b1=b2且 sgn(W1)=sgn(W2),l(S)≥2st-t+(m-1).

證明對于 S的任意兩個頂點 i和 j(1≤i,j≤n),在 S中都存在從頂點 i到頂點 j長不超過 2st-t+(m-1)的 SSSD途徑對.先證明從頂點 s到頂點 m存在長為 st-(s-m)的 SSSD途徑對.設(shè) Q1和 Q2分別是 S中從頂點 s到頂點 m的長為 t+m-s和 m的路,設(shè) Cs和 Ct分別是 S中長為 s和 t的圈.取W1=Q1+(s-1)Ct和 W2=Q2+(t-1)Cs,設(shè) P′是 S中從頂點 m 到頂點 s的唯一的路,則 W1+P′=sCt和 W2+P′=tCs.因為 S是不可冪的,且 Cs和 Ct是 S中僅有的兩個圈,所以由引理 1可知 Cs和 Ct一定是異圈對,則由式(3)可知 tCs和 sCt有不同的符號.因此 W1和 W2也有不同的符號,故 W1和 W2是從頂點 s到頂點 m 的長 rs,m=st-(s-m)的 SSSD途徑對.設(shè) P″是從頂點 i到頂點 s的長為 l=l(P″)的路,Q是從頂點 m到頂點 j的長為 expD(m)的途徑,則 0≤l≤s-1.取 W3=P″+W1+Q和 W4=P″+W2+Q.顯然 l(W3)=l(W4)=l+st-(s-m)+expD(m),且 W3和 W4是從頂點 i到頂點 j的 SSSD途徑對.由式(1)可得

結(jié)合上述兩個公式,可得 l(S)=2 st-t+(m-1).

定理 2 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中 Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 q=t,k≥2和 m≥k,則 1)若 S的長為 t的圈有不同的符號,則

2)若 S的長為 t的圈有相同的符號,則

和l(S)≤max{s-1,t+s-p-1}+2st-2s+k-t+ 1+max{s-1,t+m-1-k}.

證明 1)在圖 2中 ,設(shè) Q1=P(p→t+m)+P(t+m→k)+P(k→m)和 Q2=P(p→s)+P(s→s+1)+P(s+1→m)分別是S中從頂點 p到頂點 m的兩條長為 t-(p-m)的路.若 S的長為 t的圈有不同的符號,則 sgn(Q1)=-sgn(Q2),即 Q1和 Q2是從頂點 p到頂點 m的 SSSD途徑對.在 S中任取兩個頂點 i和 j,設(shè) T是從頂點 i到頂點 p的路,H是從頂點m到頂點 j的長為 expD(m)的途徑.顯然,W1=T+Q1+H和 W2=T+Q2+H是從頂點 i到頂點 j的 SSSD途徑對.由定號有向圖的基的定義,可得

2)若 S的長為 t的圈有相同的符號,則 sgn(Q1)=sgn(Q2).類似于定理 1的證明,若 s＜t,可以證明在 S中不存在從頂點 s+1到頂點 t+m-1長為 2st+t-2s+m-2的 SSSD途徑對和不存在從頂點t+m到頂點 2t+m-2+k-p的長為 2st+t-s+k-p-2的 SSSD途徑對,因此 l(S)≥max{2st+t-2s+m-1,2st+t-s+k-p-1}.若 s＞t,可以證明在 S中不存在從頂點 1到頂點 k-1的長為 2 st+k-t-1的 SSSD途徑對,因此 l(S)≥2st+k-t-1.故

因為定號有向圖 S是不可冪的,且 S的唯一的三個圈中有兩個圈長為 t,一個圈長為 s,所以由定理1長為 t的每個圈與長為 s的圈形成了一個異圈對.所以由式(3)可知 tCs和 sCt有不同的符號.現(xiàn)在設(shè)P1=P(s→ 1)+p(1→ k) 和 P2=P(s→ t+m-1)+P(t+m-1→ m)+P(m→ p)+P(p→ t+m)+P(t+m→k)分別是從頂點s到頂點 k的長為 k和 2t+k-s的兩條路.設(shè) P=P(k→s)是從頂點 k到頂點 s的唯一路.令 W1=P1+(t-1)Cs和 W2=P2+(s-2)Ct.顯然,W1和 W2是從頂點 s到頂點 k的途徑,則W1+P=tCs和 W2+P=sCt,所以 W1和 W2是從頂點 s到頂點 k的長為 st-(s-k)的 SSSD途徑對.

在定號有向圖 S中任取兩個頂點 i和 j,設(shè) T是從頂點 i到頂點 s的最短路,H是從頂點 k到頂點j的長為 expD(k)的途徑.顯然,W3=T+W1+H和 W4=T+W2+H是從頂點 i到頂點 j的 SSSD途徑對.由定號有向圖的基的定義可得 l(S)≤max{s-1,t+s-p-1}+ 2st-2s+k-t+1+ max{s-1,t+m-1-k}.

類似于定理 2的證明,可以得到定理 3～定理 7.

定理 3 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中 Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 s=q和 m≥k,則 1)若 S的兩個長為 s的圈有不同的符號,則

2)若 S的兩個長為 s的圈有相同的符號,則

和

定理 4 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中 Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 s=t和 m≥k,則 1)若 S的兩個長為 s的圈有不同的符號,則

2)若 S的兩個長為 s的圈有相同的符號,則

和

定理 5 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中 Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 q=t和 m≤k,則 1)若 S的兩個長為 t的圈有不同的符號,則

2)若 S的兩個長為 t的圈有相同的符號,則

和

定理 6 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中 Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 s=q和 m≤k,則 1)若 S的兩個長為 s的圈有不同的符號,則

2)若 S的兩個長為 s的圈有相同的符號,則

和

定理 7 設(shè) S是 n=q+t+m-2+k-p階本原不可冪的定號有向圖,其中Ds,t,q(見圖 2)是 S的基礎(chǔ)有向圖.若 s=t和 m≤k,則 1)若 S的兩個長為 s的圈有不同的符號,則

l(S)≤max{s- 1,q-1+s-p}+m+sq-s-q+ 1+ max{s-1,q-1+k-m}.

2)若 S的兩個長為 s的圈有相同的符號,則

和

[1]Li Z S,Hall F,Eschenbach C.On the period and base of a sign pattern matrix[J].Linear Algebra and Its Applications,1994,212/213：101-120.

[2]You L H,Shao J Y,Shan H Y.Bounds on the basis of irreducible generalized sign pattern atrices[J].Linear Algebra and Its Applications,2007,427：285-300.

[3]Liu B L,You L H.Bounds on the base of primitive nearly reducible sign pattern matrices[J].Linear Algebra and Its Applications,2006,418：863-881.

[4]Shao J Y.On the exponent of a primitive digraph[J].Linear Algebra and Its Applications,1985,64：21-31.