矩陣對角化在圖譜理論中的應用

杜志斌

摘 要 矩陣對角化是高等代數中的一個重要內容，其在矩陣研究中起著非常重要的作用。圖譜理論主要運用線性代數方法來研究圖的各種性質。本文將給出矩陣對角化在圖譜理論中的一個應用。

關鍵詞 矩陣對角化 圖譜 特征值重數

中圖分類號：O151.21 文獻標識碼：A DOI：10.16400/j.cnki.kjdkx.2015.07.027

Application of Diagonalization of Matrices in Spectral Graph Theory

DU Zhibin

（School of Mathematics and Statistics， Zhaoqing University， Zhaoqing， Guangdong 526061）

Abstract Diagonalization of matrices is an important part in higher algebra， which plays an important role in the research of matrices. Spectral graph theory mainly uses the methods related to linear algebra to study various properties of graphs. In this paper， we will present an application of diagonalization of matrices in spectral graph theory.

Key words diagonalization of matrices; spectra of graphs; multiplicity of eigenvalues

0 引言

記為階單位矩陣。對于任意實對稱陣，若是的一個特征值，則記（）為的（代數）重數。此外，若不是的特征值，則習慣上記作（） = 0。

矩陣對角化是高等代數中的一個重要內容，其在矩陣研究中起著非常重要的作用。特別地，若階矩陣可對角化，則對于任意常數，總有

秩（） = （） ? ?（1）

參見[1]。

本文將給出矩陣對角化在圖譜理論中的一個應用。所謂圖譜理論，它主要運用線性代數方法來研究圖的各種性質。

作為數與形相互結合的一個典范，圖與矩陣有著緊密的聯系。給定一個圖，可定義出一些相應的矩陣，如鄰接矩陣、Laplacian矩陣等。通過研究這些由圖所導出的矩陣的特征多項式、特征值、特征向量等，學者們得到了一大批精彩的新理論和結果，并由此建立了圖譜理論。

在圖譜理論的研究中，研究的核心內容之一是基于圖所導出的各類矩陣的特征值，其中以圖的鄰接矩陣的研究尤為突出。

本文所考慮的圖皆為無向簡單圖。圖的鄰接矩陣（）定義為[2]：

圖的鄰接矩陣的特征值簡稱為圖的特征值，由這些特征值所組成的多重集稱為圖的鄰接譜。

顯然圖的鄰接矩陣是一個實對稱陣，從而它可對角化。于是，我們很自然地提出一個問題：矩陣對角化的知識是否可運用到圖的鄰接譜的研究中。答案是肯定的。本文將給出矩陣對角化在計算圖的鄰接譜中的一個應用。

1 矩陣對角化在計算圖的鄰接譜中的應用

現有圖以及階方陣 = （）。若將圖的點集劃分為個點子集，，…，，且使得中的每個點都與中的個點相鄰，其中， = 1，2，…，，則稱為圖的因子（divisor）。特別地，若為圖的因子，根據[2，定理4.5]，的特征值同時也是圖的鄰接矩陣（）的特征值。

下面我們將運用矩陣對角化（即式子（1））來計算一些具有低階因子（即因子階數為 = 2，3）的圖的鄰接譜。特別地，對于因子階數為 = 2的情形，我們定義了一類圖——完全分割圖（complete split graph），而對于因子階數為 = 3的情形，我們定義了另一類圖——廣義完全分割圖。

記為行列零矩陣，且記為一個行列矩陣，其中每個元素皆為1。特別地，若 = ，則將簡記為，而將簡記為。

1.1 完全分割圖的鄰接譜

所謂完全分割圖（，）即為 ，其中表示個點的完全圖，表示個點的空圖，而 表示中的每個點與中的每個點皆為相鄰的。例如，圖1所示即為完全分割圖（5，2）。

圖1 完全分割圖（5，2）

我們不妨將（，）中的點劃分為兩部分，，其中是（，）的頭個點，對應著完全圖，而剩余的個點記作，對應著空圖。此外，為了方便起見，令 = （（，））。

易見，圖存在一個2階因子

即該矩陣的2個特征值亦為的特征值。對于剩余的個特征值，我們將利用式子（1）來求得。

首先，根據完全分割圖（，）的構造及其點的編號，可知其鄰接矩陣的結構如下：

顯然有秩（0） = 秩（） = + 1。現根據（1），可得（0） = 。

另一方面，由于

從而有秩（ + ） = + 1。現根據（1），可得（） = 。

綜上所述，我們可求得完全分割圖（，）的鄰接矩陣的所有特征值。

1.2 廣義完全分割圖的鄰接譜

所謂廣義完全分割圖（，，）即為 （∩），其中與分別表示個點與個點的完全圖，表示個點的空圖，而 表示中的每個點與∪中的每個點皆為相鄰的，∪表示與點不交的并。例如，圖2所示即為廣義完全分割圖（8，2，3）。

圖2 廣義完全分割圖（8，2，3）

我們不妨將（，，）中的點劃分為三部分，，，其中是（，，）的頭個點，對應著完全圖，是（，，）的第 + 1個到第 + 個點，對應著完全圖，而剩余的個點記作，對應著空圖。此外，為了方便起見，令 = （（，，））。

易見，圖存在一個3階因子

即該矩陣的3個特征值亦為的特征值。對于剩余的個特征值，我們將利用式子（1）來求得。

首先，根據廣義完全分割圖（，，）的構造及其點的編號，可知其鄰接矩陣的結構如下：

顯然有秩（0） = 秩（） = + + 1。現根據（1），可得（0） = 。

另一方面，由于

從而有秩（ + ） = + 2。現根據（1），可得（） = + 。

綜上所述，我們可求得廣義完全分割圖（，，）的鄰接矩陣的所有特征值。

1.3 總結

上文介紹了如何運用矩陣對角化來計算完全分割圖與廣義完全分割圖的鄰接譜。特別地，完全分割圖具有一個2階因子，而廣義完全分割圖具有一個3階因子。事實上，對于其它具有因子的圖，我們亦可類似地求得其鄰接譜。

此外，在圖譜理論的研究中，圖的Laplacian矩陣[4]、無符號Laplacian矩陣[5]、正規化Laplacian矩陣[6]、距離矩陣[7]等基于圖所導出的矩陣的譜也是關注的熱點。類似于上述方法，我們亦可求得這些基于圖所導出的矩陣的譜。

參考文獻

[1] 張和瑞，郝鈵新.高等代數[M]（第五版）.北京：高等教育出版社，2007.

[2] D.Cvetkovi， M. Doob， H. Sachs， Spectra of Graphs-Theory and Application[M]. New York： Academic Press，1980.

[3] A.E. Brouwer， W.H. Haemers， Spectra of graphs[M].New York： Springer，2012.

[4] R.Grone， R.Merris， The Laplacian spectrum of a graph II[J].SIAM J.Discrete Math.，1994.7：221-229.

[5] D.Cvetkovi， P. Rowlinson， S.K. Simi， Eigenvalue bounds for the signless Laplacian[J]. Publ. Inst. Math. （Beograd）， 2007.81：11-27.

[6] F. R. K. Chung， Spectral Graph Theory[M].Providence： American Math. Soc.， 1997.

[7] R. Merris， The distance spectrum of a tree[J].J. Graph Theory，1990.14：365-369.