算術結構拉普拉斯矩陣最大特征值的上界

，，

（湖南師范大學 數(shù)學系，湖南 長沙 410081）

1 研究背景

對于一個連通圖G，如果向量，則稱為G的算術結構；如果條件

A(G)=(aij)，i～j表示i與j相鄰；d、r都為列向量，所有的元素都是正整數(shù)，rT為向量r的轉置矩陣。

給定一個簡單圖G，其拉普拉斯矩陣為

圖的算術結構的概念，是Lorenzini研究代數(shù)幾何中退化曲線時，出現(xiàn)交矩陣而引入的[1]。近年來，關于算術結構的研究較多，如文獻[2]研究了完全圖、路和圈上算術結構的一些性質；文獻[3]研究了路和圈上算術結構的個數(shù)等。代數(shù)圖論是圖論的一大分支，它利用圖的關聯(lián)矩陣的代數(shù)性質來研究圖。特別地，圖譜理論主要研究它的鄰接矩陣、拉普拉斯矩陣的特征值和圖的性質之間的聯(lián)系[4]。

2 預備知識

為了證明本文將給出的有關結論，先介紹一些相關的知識和結論。

定義矩陣

因為L(G,d)是實對稱矩陣，它的特征值為實數(shù)，故可設為。

引理1[5]設A是一個n階任意矩陣，其特征值為λ1≥λ2≥…≥λn，為對應于特征值λk的特征向量，q為任意n維的列向量，則矩陣A+vqT的特征值為

定理1設G是一個n階連通圖，則B(G)的特征值為

證明由B(G)=L(G,d)+re可得，B(G)r=L(G,d)r+rer。

因向量r中每個元素都是正整數(shù)，G連通，矩陣B(G)非負不可約，所以由Perron-Frobenius定理知，er是B(G)的譜半徑，且r是其Perron向量，即

由引理1可以得到B(G)的特征值為

推論1設G是一個n階連通圖，(d,r)為G上的一個算術結構，則

3 算術結構的拉普拉斯矩陣特征值更精確的上界

引理2[8]設M(G)=(mij)是一個n階非負實對稱矩陣，若有一個對應于譜半徑的正特征向量，為M(G)的第二大特征值，則有

定理2設G是一個n階連通圖，為G上的一個算術結構，則

證明由知，，從而r是對應的正特征向量。

設

當i～j時，則

由式（6）和式（7）可得，

由引理2可知，

定理3設G是一個n階連通圖，(d,r)為G上的一個算術結構，則

證明令R=diag(r1,r2,…,rn)，定義矩陣，則C(G)的元素為

因為矩陣C(G)與L(G,d)相似，所以它們有相同的特征值，令x是矩陣C(G)對應于特征值的特征向量。

由上述2個等式可得

因為xj≤xk，xk≤xi，所以由式（10）得

設

其中

所以

因為L(G,d)r=0，所以C(G)eT=0，C(G)的秩等于L(G,d)的秩。因eT、x是C(G)不同特征值的特征向量，所以向量x與eT正交。而xi＞xj，因此

即L(G,d)最大特征值的上界為

推論2設G是一個n階連通圖，(d,r)為G上的一個算術結構，則

證明事實上

類似地可得

將上述兩式子代入

可得

即

所以，由式（8）可知

相比較而言，式（11）沒有（8）精確，但計算簡便一些，也可以作為判斷特征值上界的一個依據(jù)。

4 算例

例1拆分完全圖K4的邊v3,v4得到的一個圖S4，如圖1所示。在G的算術結構的拉普拉斯矩陣L(G,d)中，若d=(1,2,10,15,1)T，r=(15,10,3,2,5)T，試用本文的結論計算L(G,d)的最大特征值的上界。

圖1 圖S4Fig.1 Figure S4

解用式（2）（4）（8）（11）計算得到L(G,d)的最大特征值的上界分別為35,20,15.5,17，而矩陣L(G,d)的實際特征值有5個，分別為0,0.891 2,2.600 8,10.293 0,15.215 0。

顯然，由式（8）計算的結果為15.5，它與L(G,d)的實際最大特征值15.215 0相差非常小，所以式（8）更精確。

5 結語

本文得到了算術結構拉普拉斯矩陣L(G,d)的最大特征值的4個上界，分別如式（2）（4）（8）（11）所示，其中式（8）中的上界最精確，而式（11）中的上界計算較簡便。