Induced Subgraphs and Principal Submatrices
The adjacency matrix records which pairs of vertices are joined by edges. When we pass to an induced subgraph, we keep a chosen set of vertices and every edge whose two endpoints lie in that set. Algebraically, this operation selects the corresponding rows and columns of the original adjacency matrix. The selected matrix is a principal submatrix, and its eigenvalues are constrained by the eigenvalues of the full matrix.
All graphs in this tutorial are finite and simple. For a graph \(G\), its adjacency matrix \(\mathbf A(G)\) has entry \(1\) in position \(u,v\) when \(uv\in E(G)\), and entry \(0\) otherwise. It is a real symmetric matrix, so its eigenvalues are real. Write them in nonincreasing order, including repetitions: \(\lambda_1(G)\ge\lambda_2(G)\ge\cdots\ge\lambda_n(G)\), where \(n=|V(G)|\).
Order the vertices of \(G\) by listing the vertices in \(S\) first. With this ordering, the upper-left block of \(\mathbf A(G)\) is exactly \(\mathbf A(G[S])\): for any \(u,v\in S\), the adjacency entry is unchanged. Thus \(\mathbf A(G[S])\) is a principal submatrix. A different ordering merely permutes rows and the corresponding columns together, which does not change eigenvalues.
The Interlacing Inequalities
Here “interlace” means that each eigenvalue of the smaller matrix lies between two specified eigenvalues of the larger matrix. The bounds are weak: equality is allowed, including when eigenvalues are repeated. We prove the theorem using Rayleigh quotients. For a nonzero real vector \(x\), the Rayleigh quotient of a real symmetric matrix \(A\) is \(R_A(x)=x^{\mathsf T}Ax/(x^{\mathsf T}x)\).
Proof. By the spectral theorem, choose an orthonormal eigenbasis \(q_1,\dots,q_n\), with \(Aq_j=\lambda_jq_j\). On the span of \(q_1,\dots,q_k\), every nonzero vector has Rayleigh quotient at least \(\lambda_k\), and \(q_k\) has quotient exactly \(\lambda_k\). Therefore the minimum quotient on this particular \(k\)-dimensional space is \(\lambda_k\). For any other \(k\)-dimensional subspace \(U\), its dimension and the dimension \(n-k+1\) of \(\operatorname{span}(q_k,\dots,q_n)\) sum to \(n+1\); hence the two spaces have a nonzero vector in common. That vector has quotient at most \(\lambda_k\), so the minimum on \(U\) is at most \(\lambda_k\). Taking the maximum over \(U\) proves the first formula.
For the second formula, the space \(\operatorname{span}(q_k,\dots,q_n)\) has dimension \(n-k+1\), and its maximum Rayleigh quotient is \(\lambda_k\). Any subspace \(W\) of dimension \(n-k+1\) intersects \(\operatorname{span}(q_1,\dots,q_k)\) nontrivially, since their dimensions sum to \(n+1\). A nonzero vector in that intersection has quotient at least \(\lambda_k\), so the maximum on \(W\) is at least \(\lambda_k\). Taking the minimum over \(W\) proves the second formula. \(\square\)
Proof of the theorem. Identify vectors indexed by \(S\) with vectors in \(\mathbb R^n\) that are zero outside \(S\). These vectors form a coordinate subspace \(L\) of dimension \(m\). For every such vector \(x\), the quotient computed using \(\mathbf A(G)\) is the same as the quotient computed using the principal submatrix \(\mathbf A(H)\): all coordinates outside \(S\) are zero, so only entries with both indices in \(S\) contribute.
Fix \(i\) with \(1\le i\le m\). The first variational formula for \(H\) maximizes over \(i\)-dimensional subspaces contained in \(L\). These are among the \(i\)-dimensional subspaces of \(\mathbb R^n\), over which the first formula for \(G\) maximizes. Therefore \(\lambda_i(H)\le\lambda_i(G)\). For the other bound, use the second formula for \(H\): its subspaces have dimension \(m-i+1\) and are contained in \(L\). The second formula for \(G\), at index \(k=i+n-m\), minimizes over all subspaces of dimension \(n-k+1=n-(i+n-m)+1=m-i+1\). Minimizing over only those subspaces contained in \(L\) cannot give a smaller value than minimizing over all such subspaces. Hence \(\lambda_i(H)\ge\lambda_{i+n-m}(G)\). The index is valid because \(1\le i+n-m\le n\). Both inequalities follow. \(\square\)
Worked Examples
Worked Example: An Induced Triangle in \(K_4\)
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Take \(S=\{1,2,3\}\). Then \(H=G[S]\) has edges \(12,13,23\), so \(H=K_3\).
For \(K_r\), the all-ones vector is an eigenvector with eigenvalue \(r-1\), since each row has \(r-1\) ones. Every vector whose coordinates sum to zero is mapped to its negative, so the remaining \(r-1\) eigenvalues are \(-1\). Thus \(G\) has eigenvalues \(3,-1,-1,-1\), while \(H\) has eigenvalues \(2,-1,-1\).
Here \(n-m=1\). The three interlacing checks are \(3\ge2\ge-1\), \(-1\ge-1\ge-1\), and \(-1\ge-1\ge-1\). The second and third checks attain equality throughout.
Check: The adjacency matrices have traces \(0\), as expected for loopless graphs. Their squared-eigenvalue sums are \(3^2+(-1)^2+(-1)^2+(-1)^2=12\) and \(2^2+(-1)^2+(-1)^2=6\). These also equal the traces of the squared adjacency matrices: each is twice the number of edges, namely \(2\cdot6=12\) and \(2\cdot3=6\).
Worked Example: Three Consecutive Vertices of a Cycle
Let \(G=C_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34,41\}\). Choose \(S=\{1,2,3\}\). The induced subgraph \(H=G[S]\) has edges \(12,23\), so it is the path \(P_3\).
The eigenvalues of \(G\) are \(2,0,0,-2\). For instance, its adjacency matrix has eigenvectors \((1,1,1,1)\), \((1,0,-1,0)\), \((1,-1,1,-1)\), and \((0,1,0,-1)\), with respective eigenvalues \(2,0,-2,0\); ordering these gives the stated list. For \(H\), the adjacency matrix is $$ \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}. $$ Its characteristic polynomial is \(-x(x^2-2)\), so its ordered eigenvalues are \(\sqrt2,0,-\sqrt2\).
Since \(n-m=1\), the inequalities are \(2\ge\sqrt2\ge0\), \(0\ge0\ge0\), and \(0\ge-\sqrt2\ge-2\). Each holds, including the middle equality.
Check: The squared-eigenvalue sum for \(G\) is \(2^2+0^2+0^2+(-2)^2=8\), which is twice its four edges. For \(H\), it is \((\sqrt2)^2+0^2+(-\sqrt2)^2=4\), twice its two edges. The values also follow directly from the characteristic polynomial for \(H\).
Worked Example: An Induced Set of Leaves
Let \(G=K_{1,3}\), with \(V(G)=\{c,1,2,3\}\) and \(E(G)=\{c1,c2,c3\}\). Take \(S=\{1,2,3\}\). The induced subgraph \(H=G[S]\) has no edges: every edge of \(G\) uses the centre \(c\), which is not in \(S\).
The eigenvalues of \(H\) are \(0,0,0\), since its adjacency matrix is the zero matrix. For \(G\), the vector \((\sqrt3,1,1,1)\), with the centre coordinate first, has eigenvalue \(\sqrt3\): the centre receives the sum \(3\), and each leaf receives \(\sqrt3\). The vector \((-\sqrt3,1,1,1)\) has eigenvalue \(-\sqrt3\). Two independent vectors supported on the leaves with leaf coordinates summing to zero, for example \((0,1,-1,0)\) and \((0,1,0,-1)\), have eigenvalue \(0\). Thus the ordered spectrum of \(G\) is \(\sqrt3,0,0,-\sqrt3\).
With \(n-m=1\), interlacing gives \(\sqrt3\ge0\ge0\), \(0\ge0\ge0\), and \(0\ge0\ge-\sqrt3\). These hold, with equality at several bounds.
Check: The sum of the four eigenvalues is \(\sqrt3+0+0-\sqrt3=0\), and the sum for \(H\) is also \(0\). Their squared-eigenvalue sums are \(3+0+0+3=6\) and \(0\), respectively. The first equals twice the three edges of \(G\); the second equals twice the zero edges of \(H\).
Reading and Using the Inequalities
The index shift \(n-m\) matters. When \(H\) has order \(m\), its \(i\)-th largest eigenvalue is bounded above by the \(i\)-th eigenvalue of \(G\), and below by the eigenvalue \(n-m\) places later in \(G\)'s ordered list. The full list need not contain the smaller graph’s eigenvalues. For example, in the \(C_4\) example, \(\sqrt2\) is an eigenvalue of the induced \(P_3\), but it is not an eigenvalue of \(C_4\).
The result applies to every induced vertex set, whether or not the resulting graph is connected. If \(m=n\), the inequalities become \(\lambda_i(G)\ge\lambda_i(H)\ge\lambda_i(G)\), so the ordered eigenvalues agree, as expected when all vertices are retained. If \(S=\varnothing\), the adjacency matrix of \(G[S]\) has order zero and has no eigenvalues to compare; the assertion has no indices and is vacuous.
Common Pitfall
A tempting but incorrect claim is that the eigenvalues of an induced subgraph must themselves occur in the full graph’s spectrum. The \(C_4\) example disproves this: the induced \(P_3\) has eigenvalue \(\sqrt2\), while the eigenvalues of \(C_4\) are \(2,0,0,-2\). Interlacing gives the correct comparison. In particular, for \(i=1\), it gives \(2\ge\sqrt2\ge0\). Omitting the index shift in the lower bound would incorrectly demand \(\sqrt2\ge2\). The principal-submatrix relation gives inequalities, not spectral inclusion.
Interlacing is useful because it converts information about a smaller induced graph into constraints on the ordered eigenvalues of the original graph, and conversely. The argument depends on the subgraph being induced: its adjacency matrix must be the principal submatrix on the chosen vertex set. A subgraph on the same vertices that omits some edges does not in general give that principal submatrix, so this theorem cannot be applied to it on that basis.
Check Your Understanding
Use the theorem and its proof to answer the following questions.
- If \(G\) has order \(8\) and \(G[S]\) has order \(5\), which eigenvalue of \(G\) is the lower bound for \(\lambda_2(G[S])\)?
- Why does ordering the vertices of \(S\) first show that \(\mathbf A(G[S])\) is a principal submatrix?
- For \(C_4\) and its induced path on \(\{1,2,3\}\), verify the lower interlacing bound for the third eigenvalue.
- In the variational proof of the upper bound, why does maximizing over subspaces contained in the coordinate subspace give a value no larger than maximizing over all subspaces?
- What does interlacing say when \(S=V(G)\), and why is that consistent with the two graphs being the same?