From a Vertex Partition to a Matrix
A partition groups vertices that we want to study together. Instead of keeping track of every vertex separately, we can record the average number of neighbors a vertex in one group has in another. This produces a smaller matrix. Its eigenvalues capture information about the adjacency matrix, but there is an important detail: for a general partition, the quotient matrix need not be symmetric. We will relate it to a symmetric matrix before applying eigenvalue interlacing.
Throughout, \(G=(V,E)\) is a finite simple graph of order \(n\ge 1\). Write \(\mathbf A\) for its adjacency matrix, which is real and symmetric. Let \(\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n\) be the eigenvalues of \(\mathbf A\), listed with multiplicity. Consider a partition of \(V\) into \(k\) nonempty, disjoint classes \(V_1,\ldots,V_k\), where \(1\le k\le n\). Put \(n_i=|V_i|\).
The denominator is the size of the row class \(V_i\). Consequently, even though the number of edges between two different classes is the same whichever class is counted from, the averages \(q_{ij}\) and \(q_{ji}\) can differ when \(n_i\ne n_j\). The quotient matrix is therefore not generally symmetric.
Why Quotient Eigenvalues Interlace
Let \(H\) be the \(n\times k\) matrix whose \(i\)th column is the indicator vector of \(V_i\), divided by \(\sqrt{n_i}\). The columns of \(H\) are orthonormal: columns for distinct classes have disjoint supports, and the squared length of column \(i\) is \(n_i/n_i=1\). The matrix \(B=H^{T}\mathbf A H\) is therefore a symmetric compression of \(\mathbf A\).
For classes \(V_i,V_j\), let \(e(V_i,V_j)\) denote the number of edges with one endpoint in each class when \(i\ne j\); for \(i=j\), let it denote the number of edges with both endpoints in \(V_i\). The sum of neighbor counts from \(V_i\) into \(V_j\) is \(e(V_i,V_j)\) if \(i\ne j\), and \(2e(V_i,V_i)\) if \(i=j\). In either case, this sum is the corresponding entry of \(H^T\mathbf A H\) after division by \(\sqrt{n_i n_j}\). In particular, with \(D=\operatorname{diag}(n_1,\ldots,n_k)\), we have $$ B_{ij}=\frac{1}{\sqrt{n_i n_j}}\sum_{v\in V_i}|N(v)\cap V_j| =\sqrt{\frac{n_i}{n_j}}\,q_{ij}, \qquad B=D^{1/2}QD^{-1/2}. $$
Here \(D\) is invertible because every class is nonempty. The displayed relation shows that \(B\) and \(Q\) are similar, so they have the same eigenvalues. Since \(B\) is real and symmetric, those eigenvalues are real. Write them in nonincreasing order as \(\mu_1\ge\cdots\ge\mu_k\).
We prove the interlacing using the variational principle for real symmetric matrices. For a nonzero vector \(x\), its Rayleigh quotient for \(\mathbf A\) is \(R(x)=x^T\mathbf A x/(x^Tx)\). The variational principle states that, for a real symmetric \(n\times n\) matrix with eigenvalues \(\lambda_1\ge\cdots\ge\lambda_n\), $$ \lambda_i=\max_{\dim L=i}\ \min_{0\ne x\in L}R(x) =\min_{\dim W=n-i+1}\ \max_{0\ne x\in W}R(x). $$ To recall why these formulas hold, take an orthonormal eigenbasis \(u_1,\ldots,u_n\). Every \(i\)-dimensional subspace intersects \(\operatorname{span}(u_i,\ldots,u_n)\) in a nonzero vector, whose Rayleigh quotient is at most \(\lambda_i\); choosing \(\operatorname{span}(u_1,\ldots,u_i)\) attains that bound. Likewise, every \((n-i+1)\)-dimensional subspace intersects \(\operatorname{span}(u_1,\ldots,u_i)\) nontrivially, giving a vector with quotient at least \(\lambda_i\); choosing \(\operatorname{span}(u_i,\ldots,u_n)\) attains the other bound.
Proof. Let \(U\) be the column space of \(H\), a \(k\)-dimensional subspace of \(\mathbb R^n\). Since \(H^TH=I\), the map \(y\mapsto Hy\) preserves lengths, and $$ \frac{y^TBy}{y^Ty}=\frac{(Hy)^T\mathbf A(Hy)}{(Hy)^T(Hy)}=R(Hy). $$ Thus the variational principle for \(B\) calculates \(\mu_i\) by using only subspaces contained in \(U\), with the same Rayleigh quotients as for \(\mathbf A\). For the upper inequality, maximizing over \(i\)-dimensional subspaces contained in \(U\) cannot exceed maximizing over all \(i\)-dimensional subspaces of \(\mathbb R^n\). Hence \(\mu_i\le\lambda_i\).
For the lower inequality, set \(r=i+n-k\), so \(1\le r\le n\), and let \(T=\operatorname{span}(u_1,\ldots,u_r)\), where \(u_1,\ldots,u_n\) is an orthonormal eigenbasis of \(\mathbf A\). The dimension formula gives $$ \dim(U\cap T)\ge \dim U+\dim T-n=k+r-n=i. $$ Choose an \(i\)-dimensional subspace \(L\subseteq U\cap T\). Every nonzero \(x\in T\) has Rayleigh quotient at least \(\lambda_r\), since it is a linear combination of eigenvectors with eigenvalues \(\lambda_1,\ldots,\lambda_r\). Therefore the minimum Rayleigh quotient on \(L\) is at least \(\lambda_r\). The variational formula for \(\mu_i\), restricted to subspaces of \(U\), now gives \(\mu_i\ge\lambda_r=\lambda_{i+n-k}\). Similarity of \(Q\) and \(B\) gives the same eigenvalues for \(Q\), proving the result. \(\square\)
Worked Calculations
Worked Example: A Nonsymmetric Quotient of a Path
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,25,34\}\). These edges form the path \(5-2-1-3-4\). Partition the vertices into \(V_1=\{1,2\}\) and \(V_2=\{3,4,5\}\). Compute the quotient matrix and check its interlacing inequalities.
For \(V_1\), vertex \(1\) has one neighbor in \(V_1\) and one in \(V_2\); vertex \(2\) also has one neighbor in each class. The two average counts are therefore \(1\) and \(1\). For \(V_2\), the internal neighbor counts for vertices \(3,4,5\) are respectively \(1,1,0\), so their average is \((1+1+0)/3=2/3\). Their counts into \(V_1\) are \(1,0,1\), whose average is \((1+0+1)/3=2/3\). Hence $$ Q=\begin{pmatrix}1&1\\[2pt]2/3&2/3\end{pmatrix}. $$ Its characteristic polynomial is \(\det(xI-Q)=x^2-\frac53x=x(x-\frac53)\), so its eigenvalues are \(\mu_1=5/3\) and \(\mu_2=0\).
To check the graph spectrum, the characteristic polynomials \(p_j(x)\) of paths on \(j\) vertices satisfy \(p_0=1\), \(p_1=x\), and \(p_j=xp_{j-1}-p_{j-2}\), by expanding the determinant along an endpoint. This gives \(p_2=x^2-1\), \(p_3=x^3-2x\), \(p_4=x^4-3x^2+1\), and \(p_5=x^5-4x^3+3x=x(x^2-1)(x^2-3)\). Thus the ordered adjacency eigenvalues are \(\sqrt3,1,0,-1,-\sqrt3\). For \(n=5,k=2\), interlacing requires \(\lambda_1\ge\mu_1\ge\lambda_4\) and \(\lambda_2\ge\mu_2\ge\lambda_5\). Indeed, \(\sqrt3\ge5/3\ge-1\), since \(3>(5/3)^2=25/9\), and \(1\ge0\ge-\sqrt3\).
Check: the trace of \(Q\) is \(1+2/3=5/3\), the sum of its eigenvalues. Its determinant is \(2/3-2/3=0\), the product of its eigenvalues.
Worked Example: A Quotient of a Cycle
Let \(G=C_5\), explicitly \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Use the classes \(V_1=\{1,2\}\) and \(V_2=\{3,4,5\}\). For vertices \(1,2\), the counts into the two classes are \((1,1)\) and \((1,1)\), so the first row is \((1,1)\). For vertices \(3,4,5\), the counts into \(V_1\) are \(1,0,1\), averaging to \(2/3\), while the counts into \(V_2\) are \(1,2,1\), averaging to \(4/3\). Therefore $$ Q=\begin{pmatrix}1&1\\[2pt]2/3&4/3\end{pmatrix}. $$ Its trace is \(7/3\), and its determinant is \(4/3-2/3=2/3\). Thus its characteristic polynomial is \(x^2-\frac73x+\frac23\), with roots \((7+5)/6=2\) and \((7-5)/6=1/3\).
For comparison, the characteristic polynomial of \(C_5\) is \((x-2)(x^2+x-1)^2\). Its ordered eigenvalues are \(2\), \((\sqrt5-1)/2\), \((\sqrt5-1)/2\), \((-1-\sqrt5)/2\), and \((-1-\sqrt5)/2\). For \(i=1\), the required bounds are \(\lambda_1=2\ge2\ge\lambda_4=(-1-\sqrt5)/2\). For \(i=2\), they are \(\lambda_2=(\sqrt5-1)/2\ge1/3\ge\lambda_5=(-1-\sqrt5)/2\). The left inequality follows from \(\sqrt5\ge5/3\), which holds because \(5\ge25/9\); the right inequality holds because \((-1-\sqrt5)/2<0<1/3\).
Check: the quotient eigenvalues sum to \(2+1/3=7/3\) and multiply to \(2/3\), agreeing with the trace and determinant computed directly.
Worked Example: Two Classes in a Complete Graph
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Take \(V_1=\{1\}\) and \(V_2=\{2,3,4\}\). Vertex \(1\) has no neighbor in \(V_1\) and three in \(V_2\), giving the first row \((0,3)\). Each vertex of \(V_2\) has one neighbor in \(V_1\) and two in \(V_2\), giving the second row \((1,2)\). Thus $$ Q=\begin{pmatrix}0&3\\1&2\end{pmatrix}. $$ The characteristic polynomial is \(x^2-2x-3=(x-3)(x+1)\), so the quotient eigenvalues are \(3\) and \(-1\).
The adjacency matrix of \(K_4\) is \(J-I\), where \(J\) is the all-ones matrix. The all-ones vector is an eigenvector with eigenvalue \(3\); every vector whose coordinates sum to zero is an eigenvector with eigenvalue \(-1\). Hence the ordered spectrum is \(3,-1,-1,-1\). With \(n=4,k=2\), interlacing says \(3\ge3\ge-1\) and \(-1\ge-1\ge-1\), both of which hold.
Check: the quotient eigenvalues have sum \(3+(-1)=2\), equal to the trace \(0+2=2\), and product \(-3\), equal to the determinant \(0\cdot2-3\cdot1=-3\).
Interpretation and a Common Mistake
Interlacing supplies bounds without requiring the entire adjacency spectrum to be computed. For example, a large graph may have a partition into a few classes, so its quotient has only a few eigenvalues. Each quotient eigenvalue is constrained between two adjacency eigenvalues, with the index shift determined by the number \(n-k\) of dimensions omitted. This makes the partition useful as a compact spectral summary, though the summary depends on the chosen classes.
Common mistake: treating \(Q\) as symmetric. In the first example, \(q_{12}=1\), whereas \(q_{21}=2/3\). It would be incorrect to replace the two entries by a single value or to apply a theorem requiring a symmetric matrix directly to \(Q\). The correct symmetric matrix is \(B=D^{1/2}QD^{-1/2}\). Here \(D=\operatorname{diag}(2,3)\), so $$ B=\begin{pmatrix}1&\sqrt{2/3}\\[2pt]\sqrt{2/3}&2/3\end{pmatrix}, $$ which is symmetric and similar to \(Q\). The interlacing theorem applies to \(B\), and similarity transfers its eigenvalues to \(Q\).
Common mistake: using total edge counts instead of averages. For the first example, the three vertices in \(V_2\) have internal neighbor counts \(1,1,0\), not \(1,2,0\). Their average is \((1+1+0)/3=2/3\). The counts into \(V_1\) are \(1,0,1\), also averaging to \(2/3\). These averages, rather than an unnormalised total, are the entries in the second row of the quotient matrix.
Check Your Understanding
For each question, keep the row-class denominator in the quotient definition and order eigenvalues nonincreasingly.
- For \(V_1=\{1,2\}\), \(V_2=\{3,4\}\), compute the quotient matrix of the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,13,24\}\). Is the quotient symmetric?
- Explain why quotient eigenvalues are real even when the quotient matrix is not symmetric.
- If a graph has order \(n=8\) and a partition has \(k=3\) classes, write the interlacing bounds for \(\mu_1,\mu_2,\mu_3\).
- For the quotient matrix \(\begin{pmatrix}0&2\\1&1\end{pmatrix}\), calculate its eigenvalues and check their sum and product against its trace and determinant.
- Why must every class in the partition be nonempty for the diagonal similarity \(B=D^{1/2}QD^{-1/2}\) used in the proof?