Next: Undirected graphs Up: The spectrum of a Previous: Perron-Frobenius Theory

# The spectrum of a graph

Let be a (possibly directed) finite graph on vertices. The adjacency matrix of is the matrix with rows and columns indexed by and entries of edges from to .

(We may consider as a linear transformation on the vector space of maps from into , where is some field such as or . Now it is meaningful to consider what happens with when we choose a different basis in .)

The spectrum of is by definition the spectrum of , that is, its set of eigenvalues together with their multiplicities. (Formally, a multiset.)

The characteristic polynomial of is that of , that is, the polynomial defined by .

Example    Let be the path with three vertices and two edges. Assigning some arbitrary order to the three vertices of , we find that the adjacency matrix becomes one of or or . The characteristic polynomial is . The spectrum is , 0, . Eigenvectors:

(Here, for an eigenvector , we write as a label at the vertex ; one has if and only if .)

Example    Let be the tournament with adjacency matrix . Then has characteristic polynomial and spectrum 1, , , where is a primitive cube root of unity.

Example    Let be the directed graph with two vertices and a single directed edge. Then with and spectrum (multiplicity written as exponent). The eigenvalue 0 has geometric multiplicity 1 and algebraic multiplicity 2.

By Perron-Frobenius theory, we know something about the largest eigenvalue of a graph.

Proposition 1.4.1   Each graph has a real eigenvalue with nonnegative real corresponding eigenvector, and such that for each eigenvalue we have .

If is strongly connected, then has multiplicity 1.

If is primitive (strongly connected, and such that not all cycles have a length that is a multiple of some integer ), then for all eigenvalues different from .

The function decreases when vertices or edges are removed from .

Exercise     Let be a tournament, that is, a directed graph in which there is precisely one edge between any two distinct vertices, in other words, of which the adjacency matrix satisfies .

(i) Show that all eigenvalues have real part not less than .

(ii) The tournament is called regular when each vertex has the same number of out-arrows. Clearly, when there are vertices, this number of out-arrows is . Show that all eigenvalues have real part at most , and that occurs if and only if is regular (and then ).

(iii) Show that either has full rank or has rank , and that has full rank when is regular.

Hint: for a vector , consider the expression .

Subsections

Next: Undirected graphs Up: The spectrum of a Previous: Perron-Frobenius Theory
Andries Brouwer 2003-09-30