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 $S$ be a real $n \times m$ matrix such that $S^\top S = I$. Let $A$ be a real symmetric matrix of order $n$, and define $B = S^\top A S$. Let the eigenvalues of $A$ be $\theta_1 \ge \theta_2 \ge ... \ge \theta_n$ and let those of B be $\eta_1 \ge \eta_2 \ge ... \ge \eta_m$.

1. `Interlacing': We have $\theta_j \ge \eta_j \ge \theta_{n-m+j}$ $(1 \le j \le m)$.

2. If for some $j$ equality holds in either inequality, then there is a vector $v$ such that $Bv = \eta_j v$ and $ASv = \eta_j Sv$.

3. If, for some integer $l \ge 1$, we have $\eta_j = \theta_j$ for $1 \le j \le l$, then for each vector $v$ such that $Bv = \eta_l v$ we have $ASv = \eta_l Sv$.

4. If, for some integer $l$, we have $\eta_j = \theta_j$ for $1 \le j \le l$ and $\eta_j = \theta_{n-m+j}$ for $l + 1 \le j \le m$, then $SB = AS$.

Proof:     Let $u_1 , ... , u_n$ be an orthonormal basis of eigenvectors of $A$ such that $Au_i = \theta_i u_i$ for all $i$, and let $v_1 , ... , v_m$ be such a basis for $B$, with $Bv_j = \eta_j v_j$ for all $j$. Write $U_i = \langle u_1 , ... , u_i \rangle$ and $V_j = \langle v_1 , ... , v_j \rangle$.

By expanding the vector $v$ on the basis $\{v_1 , ... , v_m \}$ one sees that if $v \in V_j$, then $v^\top B v \ge \eta_j v^\top v$. Similarly it follows that if $u \in {U_{j-1}}^{\perp}$, then $u^\top A u \le \theta_j u^\top u$. In both cases, equality implies that we have an eigenvector.

(i) Let $v$ be a nonzero vector in $V_j \cap (S^\top U_{j-1} )^{\perp}$ (this is a subspace of dimension at least one). Then $Sv \in {U_{j-1}}^{\perp}$. Now

$$\eta_j \le {{ v^\top B v } \over { v^\top v }} = {{ v^\top S^\top A S v } \over { v^\top S^\top S v }} \le \theta_j .$$

Applying the same argument to $-A$ and $-B$ instead of $A$ and $B$, one finds $\eta_j \ge \theta_{n-m+j}$. This proves (i), and (ii) follows immediately from the above.

(iii) Induction on $l$. We may suppose that $\eta_l \ne \eta_{l-1}$. Now $U_{l-1} = S V_{l-1}$ so that $v \in V_l \cap {V_{l-1}}^{\perp} = V_l \cap (S^\top U_{l-1} )^{\perp}$, and the above applies.

(iv) We have $SBv_j = \eta_j Sv_j = ASv_j$ for all $j$. Since the $v_j$ form a basis, it follows that $SB = AS$. $\Box$

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 $\Gamma$ be a graph and $\Delta$ an induced subgraph. Then the eigenvalues of $\Delta$ interlace those of $\Gamma$.

Proof:     Apply the above theorem, where $A$ and $B$ are the adjacency matrices of $\Gamma$ and $\Delta$, and $S_{ \alpha \beta }$ equals $1$ when $\alpha = \beta \in \Delta$, and is $0$ otherwise. $\Box$

Remark     As an application we can show that if $\Gamma$ is a strongly regular graph that is not complete multipartite, then for each vertex $\gamma \in \Gamma$ the subgraph $\Gamma_2 ( \gamma )$ is connected. Indeed, if not, then its largest eigenvalue $k - \mu$ would have multiplicity at least two, and hence would be not larger than the second largest eigenvalue $r$ of $\Gamma$. Then $x^2 + ( \mu - \lambda ) x + \mu - k \le 0$ for $x = k - \mu$, i.e., $(k - \mu )(k - \lambda - 1) \le 0$, contradiction.

Corollary 1.5.3   Let $\Gamma$ be a graph, and $\Pi = \{ X_1 , ... , X_m \}$ be a partition of its vertex set into nonempty parts. Let $B_{ij}$ be the average number of neighbours in $X_j$ of a vertex in $X_i$. Then the eigenvalues of $B$ interlace those of $\Gamma$. If the interlacing is tight, then each vertex in $X_i$ has precisely $B_{ij}$ neighbours in $X_j$.

Proof:     Apply the above theorem to the adjacency matrix $A$ of $\Gamma$ and the matrix $S$ such that $S_{ \gamma i }$ equals $\vert X_i \vert^{-1/2}$ if $\gamma \in X_i$ and is $0$ otherwise. (Then $S^\top A S = D^{-1} B D$ if $D$ is the diagonal matrix with $D_{ii} = \vert X_i \vert^{1/2}$, so that $B$ has the same eigenvalues as $S^\top A S$.) $\Box$

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