# 随机算法 (Fall 2011)/Graph Spectrum

The adjacency matrix of an ${\displaystyle n}$-vertex graph ${\displaystyle G}$, denoted ${\displaystyle A=A(G)}$, is an ${\displaystyle n\times n}$ matrix where ${\displaystyle A(u,v)}$ is the number of edges in ${\displaystyle G}$ between vertex ${\displaystyle u}$ and vertex ${\displaystyle v}$. Because ${\displaystyle A}$ is a symmetric matrix with real entries, due to the Perron-Frobenius theorem, it has real eigenvalues ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$, which associate with an orthonormal system of eigenvectors ${\displaystyle v_{1},v_{2},\ldots ,v_{n}\,}$ with ${\displaystyle Av_{i}=\lambda _{i}v_{i}\,}$. We call the eigenvalues of ${\displaystyle A}$ the spectrum of the graph ${\displaystyle G}$.
The spectrum of a graph contains a lot of information about the graph. For example, supposed that ${\displaystyle G}$ is ${\displaystyle d}$-regular, the following lemma holds.
 Lemma ${\displaystyle |\lambda _{i}|\leq d}$ for all ${\displaystyle 1\leq i\leq n}$. ${\displaystyle \lambda _{1}=d}$ and the corresponding eigenvector is ${\displaystyle ({\frac {1}{\sqrt {n}}},{\frac {1}{\sqrt {n}}},\ldots ,{\frac {1}{\sqrt {n}}})}$. ${\displaystyle G}$ is connected if and only if ${\displaystyle \lambda _{1}>\lambda _{2}}$. If ${\displaystyle G}$ is bipartite then ${\displaystyle \lambda _{1}=-\lambda _{n}}$.
 Let ${\displaystyle A}$ be the adjacency matrix of ${\displaystyle G}$, with entries ${\displaystyle a_{ij}}$. It is obvious that ${\displaystyle \sum _{j}a_{ij}=d\,}$ for any ${\displaystyle j}$. (1) Suppose that ${\displaystyle Ax=\lambda x,x\neq \mathbf {0} }$, and let ${\displaystyle x_{i}}$ be an entry of ${\displaystyle x}$ with the largest absolute value. Since ${\displaystyle (Ax)_{i}=\lambda x_{i}}$, we have ${\displaystyle \sum _{j}a_{ij}x_{j}=\lambda x_{i},\,}$ and so ${\displaystyle |\lambda ||x_{i}|=\left|\sum _{j}a_{ij}x_{j}\right|\leq \sum _{j}a_{ij}|x_{j}|\leq \sum _{j}a_{ij}|x_{i}|\leq d|x_{i}|.}$ Thus ${\displaystyle |\lambda |\leq d}$. (2) is easy to check. (3) Let ${\displaystyle x}$ be the nonzero vector for which ${\displaystyle Ax=dx}$, and let ${\displaystyle x_{i}}$ be an entry of ${\displaystyle x}$ with the largest absolute value. Since ${\displaystyle (Ax)_{i}=dx_{i}}$, we have ${\displaystyle \sum _{j}a_{ij}x_{j}=dx_{i}.\,}$ Since ${\displaystyle \sum _{j}a_{ij}=d\,}$ and by the maximality of ${\displaystyle x_{i}}$, it follows that ${\displaystyle x_{j}=x_{i}}$ for all ${\displaystyle j}$ that ${\displaystyle a_{ij}>0}$. Thus, ${\displaystyle x_{i}=x_{j}}$ if ${\displaystyle i}$ and ${\displaystyle j}$ are adjacent, which implies that ${\displaystyle x_{i}=x_{j}}$ if ${\displaystyle i}$ and ${\displaystyle j}$ are connected. For connected ${\displaystyle G}$, all vertices are connected, thus all ${\displaystyle x_{i}}$ are equal. This shows that if ${\displaystyle G}$ is connected, the eigenvalue ${\displaystyle d=\lambda _{1}}$ has multiplicity 1, thus ${\displaystyle \lambda _{1}>\lambda _{2}}$. If otherwise, ${\displaystyle G}$ is disconnected, then for two different components, we have ${\displaystyle Ax=dx}$ and ${\displaystyle Ay=dy}$, where the entries of ${\displaystyle x}$ and ${\displaystyle y}$ are nonzero only for the vertices in their components components. Then ${\displaystyle A(\alpha x+\beta y)=d(\alpha x+\beta y)}$. Thus, the multiplicity of ${\displaystyle d}$ is greater than 1, so ${\displaystyle \lambda _{1}=\lambda _{2}}$. (4) If ${\displaystyle G}$ if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets ${\displaystyle V_{1}}$ and ${\displaystyle V_{2}}$ such that all edges have one endpoint in each of ${\displaystyle V_{1}}$ and ${\displaystyle V_{2}}$. Algebraically, this means that the adjacency matrix can be organized into the form ${\displaystyle P^{T}AP={\begin{bmatrix}0&B\\B^{T}&0\end{bmatrix}}}$ where ${\displaystyle P}$ is a permutation matrix, which has no change on the eigenvalues. If ${\displaystyle x}$ is an eigenvector corresponding to the eigenvalue ${\displaystyle \lambda }$, then ${\displaystyle x'}$ which is obtained from ${\displaystyle x}$ by changing the sign of the entries corresponding to vertices in ${\displaystyle V_{2}}$, is an eigenvector corresponding to the eigenvalue ${\displaystyle -\lambda }$. It follows that the spectrum of a bipartite graph is symmetric with respect to 0.
${\displaystyle \square }$