凱萊圖的單特征值

張 蕾,王 燕,楊玉軍

(煙臺大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 山東 煙臺 264005)

在圖論中, 圖的特征值和特征向量通常指的是其鄰接矩陣的特征值和特征向量[1-2]. 眾所周知, 連通k-正則圖(任意點的度是k)的任一特征值λ滿足|λ|≤k, 而且k是單特征值. 相似地, 連通k-正則二部圖的任一特征值μ滿足|μ|≤k, 而且k和-k都是單特征值. 點傳遞圖是一類正則圖. 那么, 一個點傳遞圖除了它的度數(shù)之外還有沒有單特征值? 或者說, 如何確定一個點傳遞圖除去它的度數(shù)之外的單特征值? 在文獻(xiàn)[3]中, PETERSDORF和SACHS給出了點傳遞圖單特征值的范圍, 但是對于具體的點傳遞圖還需要根據(jù)圖本身的特點來確定它的單特征值. 本文研究了一類特殊的點傳遞圖-凱萊圖的單特征值. 假定G是有限群,S是G的子集. 如果S不含單位元, 逆封閉, 并且可以生成G, 則稱S是G的一個凱萊子集. 此時,G關(guān)于S的凱萊圖記作Cay(G,S), 其中,Cay(G,S)的點集是G中的元素; 任意兩點g,h(g,h∈G)相鄰當(dāng)且僅當(dāng)hg-1∈S[4-6]. 本文重點討論了循環(huán)群凱萊圖(循環(huán)圖)和二面體群凱萊圖的單特征值. 在第2、3 節(jié)中, 分別給出了循環(huán)群和二面體群凱萊圖的單特征值需要滿足的必要條件. 一般來說, 這些必要條件不是充分條件, 針對這一情況給出了一些例子.

1 基礎(chǔ)知識

定義1(右循環(huán)矩陣)R=(rst)n×n是一個n×n矩陣,如果R的第s行是R的第一行向右平移s-1步得到的, 那么稱R是右循環(huán)矩陣. 也就是說,R中的元素滿足rst=r1,t-s+1. 其中,R的下標(biāo)屬于{1,2,…,n}且模n運算. 為了在以后的敘述中更加方便, 用[r1,r2,…,rn]R表示R, 其中,rm(1≤m≤n)是R的第一行元素.

定義2(左循環(huán)矩陣)L=(lst)n×n是一個n×n矩陣, 如果L的第s行是L的第一行向左平移s-1步得到的, 那么稱L是左循環(huán)矩陣. 也就是說,L中的元素滿足lst=l1,s+t-1. 其中,L的下標(biāo)屬于{1,2,…,n}且模n運算. 為了在以后的敘述中更加方便, 用[l1,l2,…,ln]L表示L, 其中,lm(1≤m≤n)是L的第一行元素.

注意:在圖論中, 循環(huán)矩陣通常指的是右循環(huán)矩陣. 在本文中, 為區(qū)分這2種平移方式得到的矩陣, 分別定義了左循環(huán)矩陣和右循環(huán)矩陣. 然而, 這2種循環(huán)矩陣之間也有一定的聯(lián)系.

引理1 令L是左循環(huán)矩陣, 那么L2是右循環(huán)矩陣.

證明令L=(lst)n×n,L2=(ast)n×n. 那么

已知, 右循環(huán)矩陣的特征值可以用其矩陣的元素表示出來.

引理3令R=[r0,r1,…,rn-1]R是右循環(huán)矩陣,那么R的特征值為

其中, i是復(fù)數(shù), i2=-1.

在文獻(xiàn)[3]中,作者給出了點傳遞圖單特征值的一個描述.

引理4令Γ是連通k度點傳遞圖,λ是Γ的單特征值. 如果Γ有奇數(shù)個頂點, 那么λ=k; 如果Γ有偶數(shù)個頂點, 那么λ=2α-k. 其中, 0≤α≤k.

由于連通正則圖的度一定是它的單特征值,而且連通正則二部圖的負(fù)度數(shù)也是單特征值,而點傳遞圖都是正則圖,所以根據(jù)引理4, 我們只需要確定偶數(shù)個頂點的點傳遞圖的單特征值.

2 循環(huán)圖的單特征值

在圖論中, 循環(huán)圖通常定義為鄰接矩陣是循環(huán)矩陣的圖. 實際上循環(huán)圖也可以定義為循環(huán)群的凱萊圖. 因此, 循環(huán)圖是點傳遞圖.

令G=是2n階循環(huán)群,S是G的凱萊子集. 假設(shè)A是Cay(G,S)的鄰接矩陣, 那么A=[0,a1,…,a2n-1]R是右循環(huán)矩陣, 其中對任意1≤j≤ 2n-1,aj=1當(dāng)且僅當(dāng)gj∈S. 否則為0. 由凱萊子集的定義知,aj=a2n-j.

定理1 令G=是階為2n的循環(huán)群,S是G的凱萊子集且|S|=k. 假設(shè)A=[0,a1,…,a2n-1]R是Cay(G,S)的鄰接矩陣. 如果λ是A的單特征值并且λ≠k, 那么λ=2α-k.其中，當(dāng)n是偶數(shù)時,α=2(a2+a4+…+an-2)+an. 當(dāng)n是奇數(shù)時,α=2(a2+a4+…+an-1). 進(jìn)一步說, 在這2種情況下,α≠k.

證明根據(jù)引理3,A的特征值可以表示為:

也就是說

ancos(tπ),0≤t≤2n-1.

(1)

易知, 對任意的1≤j≤n,λj=λ2n-j. 因此, 只有λ0和λn可能是單特征值. 通過進(jìn)一步計算可知,λ0=k,λn=-2a1+2a2+…+2an-1cos(n-1)π+ancosnπ. 因此, 當(dāng)n是偶數(shù)時,λn=2[2(a2+a4+…+an-2)+an]-k, 此時α=2(a2+a4+…+an-2)+an; 當(dāng)n是奇數(shù)時,λn=2[2(a2+a4+…+an-1)]-k. 此時α=2(a2+a4+…+an-1).

注1根據(jù)定理1, 階為2n的循環(huán)群, 除去它的度外至多有1個單特征值. 然而, 一般情況下無法確定一個圖在什么情況下一定含有2個單特征值, 因為λn可能與某些λi(i≠n)相同.現(xiàn)在把公式(1)分成以下4種情況.

推論1在定理1中,如果對任意的1≤j≤n-1, 我們要求aj=an-j, 那么當(dāng)n是奇數(shù)時, 循環(huán)圖Cay(G,S)恰有1個單特征值(也就是它的度).

證明由定理1和注1中的第4個公式可知.

推論2在定理1中,如果n是大于3的素數(shù)并且至少存在一個j(1≤j≤n-1), 使得aj≠an-j, 那么該循環(huán)圖有2個單特征值.

推論3在定理1中,如果n是不能被3整除的奇數(shù), 并且對任意的1≤j≤n-1, 有an≠an-j, 那么該循環(huán)圖有2個單特征值.

下面將選取幾個階為2n的循環(huán)群的凱萊子集, 解釋單特征值的復(fù)雜性.

例1令G=是階為2n的循環(huán)群.如果n是偶數(shù),取S={g,g2,g3,g-1,g-2,g-3},那么循環(huán)群Cay(G,S)恰有1個單特征值,也就是它的度6.

通過相似的證明方式,給出下面的例子.

例2令G=是階為2n的循環(huán)群.

(1)如果n是不能被3和4整除的偶數(shù),取S={g,g2,g-1,g-2}, 那么循環(huán)群Cay(G,S)有2個單特征值.

(2)如果n是3的倍數(shù), 取S={g,g2,g-1,g-2}, 那么循環(huán)群Cay(G,S) 恰有1個單特征值.

(3)如果n是奇數(shù)且是3的倍數(shù), 但它不是9的倍數(shù), 取S={g,g3,g-1,g-3}, 那么循環(huán)群Cay(G,S)有2個單特征值.

3 二面體群凱萊圖的單特征值

令Dn={θ,τ|θn=τ2=1,τθτ=θ-1}是階為2n的二面體群. 根據(jù)Dn凱萊子集選取的不同, 把這一節(jié)分成2種情況討論.

情況1令S={τ,τθu,τθv,…,τθw}是Dn的凱萊子集,S中有k個元素, 易知凱萊圖Cay(Dn,S)是一個二部圖. 因此,Cay(Dn,S)的鄰接矩陣可記作

(2)

其中,A1,A2和2個零矩陣都是階為n的方陣. 當(dāng)1≤r≤n,n+1≤s≤ 2n時, 若θr-1與τθs-n-1相鄰, 那么(A1)rs為1, 否則為0. 當(dāng)n+1≤r≤ 2n,1≤s≤n時, 若τθr-n-1與τθs-1相鄰, 那么(A2)rs為1, 否則為0. 易知A1=A2并且它們都是左循環(huán)矩陣. 記A1=A2=B=[b0,b1,…,bn-1]L，那么，

(3)

|λI-A|=|λI-B||λI+B|=|λ2I-B2| .

那么A的特征值是由B和-B的特征值組成的. 或者說, 如果知道B2的特征值, 就可以得到A的特征值.由引理3知,B2的特征值是

如果n是奇數(shù), 那么B2只有一個單特征值μ0=c0+c1+…+cn-1. 由引理2知μ0=k2. 由于k是凱萊圖的度, 可知當(dāng)n是奇數(shù)時,A有2個單特征值k和-k.

如果把它寫成2α-k的形式, 那么

與定理1的證明類似, 如果c0-c1+c2-c3+…-cn-1=k2, 那么可以得到b0=b2=…=bn-2=0或者b1=b3=…=bn-1=0. 無論哪種情況, 所得凱萊子集都無法生成整個群. 因此, 2α-k≠±k.

例3令Dn={θ,τ|θn=τ2=1,τθτ=θ-1},

情況2取S為Dn的凱萊子集, 如果τθi∈S, 那么τθn-i∈S. 考慮Cay(Dn,S)的鄰接矩陣P, 把P分成4塊

(4)

其中,Pi(1≤i≤ 4)是階為n的方陣. 當(dāng)1≤s,t≤n時, 若θs-1與θt-1相鄰, 則(P1)st=1, 否則為0; 當(dāng)1≤s≤n,n+1≤t≤ 2n時, 若θs-1與τθ2n-t+1相鄰, 則(P2)st=1, 否則為0; 當(dāng)n+1≤s≤ 2n,1≤t≤n時, 若τθ2n-s+1與θt-1相鄰, 則(P3)st=1,否則為0; 當(dāng)n+1≤s,t≤ 2n時, 若τθ2n-s+1與τθ2n-t+1相鄰, 則(P4)st=1, 否則為0.

由凱萊圖的鄰接關(guān)系可知, 在P1中2個點θs-1和θt-1相鄰當(dāng)且僅當(dāng)θs-t∈S. 易知這一鄰接關(guān)系與在P4中相同, 也就是說P1=P4. 相似的,P2=P3. 進(jìn)一步說, 容易證得這4個塊都是右循環(huán)矩陣. 因此, 把P記作

(5)

其中,A=[0,a1,…,an-1]R,B=[b0,b1,…,bn-1]R都是(0,1)—矩陣. 由凱萊子集S選取的要求可知, 對1≤k,m≤n-1, 有ak=an-k,bm=bn-m.

P的特征多項式為

|λI-(A+B)|·|λI-(A-B)| ,

(6)

因此,P的特征值是由A+B和A-B的特征值組成的.如果想得到P的單特征值,就只需要求得A+B和A-B的單特征值. 由于A+B和A-B都是右循環(huán)矩陣, 其中,A+B=[b0,a1+b1,…,an-1+bn-1]R,A-B=[-b0,a1-b1,…,an-1-bn-1]R. 那么由引理3, 可以得到接下來的引理5.

引理5由上文給出的定義得到Dn,S和P.如果把A+B和A-B的特征值記作λt和μt(1≤t≤n), 那么P(或凱萊圖Cay(Dn,S))的特征值為

…+(an-1+bn-1)ωtn-1,

以及

…+(an-1-bn-1)ωtn-1,

(i)當(dāng)n是奇數(shù)時,

(ii)當(dāng)n是偶數(shù)時,

其中, 0≤t≤n-1.

證明已知,Cay(G,S)的單特征值形如2α-k(1≤α≤k). 由引理5知:

當(dāng)n是奇數(shù)時, 易知對任意的1≤t≤n-1, 有λt=λn-t,μt=μn-t. 那么在這種情況下,λ0=k和μ0=-b0+(a1-b1)+(a2-b2)+…+(an-1+bn-1)是Cay(G,S)的2個單特征值. 可以求得,α=k或a1+a2+…+an-1.

注3在定理3中, 只給出了λ是單特征值的必要條件, 但它未必是充分條件.

例4令Dn={θ,τ|θn=τ2=1,τθτ=θ-1}是二面體群.

(2)如果n是不能被3和4整除的偶數(shù), 取S={θ,θ-1,τθ3,τθ-3,τθ5,τθ-5}, 那么對應(yīng)的凱萊圖有4個單特征值.

注4 對于一般的二面體群, 如果不對它的凱萊子集加任何條件, 就沒有好的辦法求出它對應(yīng)的凱萊子集的單特征值.

接下來, 通過一個簡單的例子來說明一般情況下的單特征值的復(fù)雜性.

例5令D5={θ,τ|θ5=τ2=1,τθτ=θ-1},取S={θ,θ4,τ,τθ,τθ2}, 那么Cay(D5,S1)恰有一個單特征值, 也就是它的度5. 取S2={θ,θ4,τ}, 那么Cay(D5,S2)除去它的度3外還有一個單特征值1.

4 結(jié)束語

本文通過循環(huán)圖特征值的算法以及H.SACHS和M.PETERSDORF對點傳遞圖特征值的歸納, 給出了循環(huán)群和兩類二面體群單特征值求得的必要條件, 并給出了該必要條件不是充分條件的一些例子.