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
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.
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 .