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

杜志斌

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

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

中圖分類號：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]：

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

顯然圖的鄰接矩陣是一個實對稱陣，從而它可對角化。于是，我們很自然地提出一個問題：矩陣對角化的知識是否可運用到圖的鄰接譜的研究中。……