Next: Automorphisms Up: The spectrum of a Previous: Undirected graphs

# Interlacing

The following theorem is a classical result, cf. Fischer [10] and Courant & Hilbert [5] (Vol. 1, Ch. I, §4). Our treatment follows Haemers [14] (Ch. I).

Theorem 1.5.1   Let be a real matrix such that . Let be a real symmetric matrix of order , and define . Let the eigenvalues of be and let those of B be .

1. `Interlacing': We have .

2. If for some equality holds in either inequality, then there is a vector such that and .

3. If, for some integer , we have for , then for each vector such that we have .

4. If, for some integer , we have for and for , then .

Proof:     Let be an orthonormal basis of eigenvectors of such that for all , and let be such a basis for , with for all . Write and .

By expanding the vector on the basis one sees that if , then . Similarly it follows that if , then . In both cases, equality implies that we have an eigenvector.

(i) Let be a nonzero vector in (this is a subspace of dimension at least one). Then . Now

Applying the same argument to and instead of and , one finds . This proves (i), and (ii) follows immediately from the above.

(iii) Induction on . We may suppose that . Now so that , and the above applies.

(iv) We have for all . Since the form a basis, it follows that .

Remark    This theorem generalizes directly to complex Hermitean matrices instead of real symmetric matrices (with conjugate transpose instead of transpose) with virtually the same proof.

If the assumptions of (iv) hold, we say that the interlacing is tight. Below we formulate some corollaries in terms of graphs, since that is what we are mainly interested in. Of course analogous statements hold for arbitrary real symmetric matrices (and we shall use such an interlacing result to derive the Krein conditions).

Corollary 1.5.2   Let be a graph and an induced subgraph. Then the eigenvalues of interlace those of .

Proof:     Apply the above theorem, where and are the adjacency matrices of and , and equals when , and is otherwise.

Remark     As an application we can show that if is a strongly regular graph that is not complete multipartite, then for each vertex the subgraph is connected. Indeed, if not, then its largest eigenvalue would have multiplicity at least two, and hence would be not larger than the second largest eigenvalue of . Then for , i.e., , contradiction.

Corollary 1.5.3   Let be a graph, and be a partition of its vertex set into nonempty parts. Let be the average number of neighbours in of a vertex in . Then the eigenvalues of interlace those of . If the interlacing is tight, then each vertex in has precisely neighbours in .

Proof:     Apply the above theorem to the adjacency matrix of and the matrix such that equals if and is otherwise. (Then if is the diagonal matrix with , so that has the same eigenvalues as .)

For more detailed eigenvalue inequalities, see Haemers [14].

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