随机算法 (Fall 2011)/Graph Spectrum

From EtoneWiki
Jump to: navigation, search

The adjacency matrix of an -vertex graph , denoted , is an matrix where is the number of edges in between vertex and vertex . Because is a symmetric matrix with real entries, due to the Perron-Frobenius theorem, it has real eigenvalues , which associate with an orthonormal system of eigenvectors with . We call the eigenvalues of the spectrum of the graph .

The spectrum of a graph contains a lot of information about the graph. For example, supposed that is -regular, the following lemma holds.

Lemma
  1. for all .
  2. and the corresponding eigenvector is .
  3. is connected if and only if .
  4. If is bipartite then .
Proof.
Let be the adjacency matrix of , with entries . It is obvious that for any .
  • (1) Suppose that , and let be an entry of with the largest absolute value. Since , we have
and so
Thus .
  • (2) is easy to check.
  • (3) Let be the nonzero vector for which , and let be an entry of with the largest absolute value. Since , we have
Since and by the maximality of , it follows that for all that . Thus, if and are adjacent, which implies that if and are connected. For connected , all vertices are connected, thus all are equal. This shows that if is connected, the eigenvalue has multiplicity 1, thus .
If otherwise, is disconnected, then for two different components, we have and , where the entries of and are nonzero only for the vertices in their components components. Then . Thus, the multiplicity of is greater than 1, so .
  • (4) If if bipartite, then the vertex set can be partitioned into two disjoint nonempty sets and such that all edges have one endpoint in each of and . Algebraically, this means that the adjacency matrix can be organized into the form
where is a permutation matrix, which has no change on the eigenvalues.
If is an eigenvector corresponding to the eigenvalue , then which is obtained from by changing the sign of the entries corresponding to vertices in , is an eigenvector corresponding to the eigenvalue . It follows that the spectrum of a bipartite graph is symmetric with respect to 0.