Why Equitable Partitions Help
An adjacency matrix can be large even when a graph has a small number of repeated vertex roles. An equitable partition captures those roles: vertices in the same cell have identical counts of neighbours in every cell. The resulting quotient matrix records these counts and is often much smaller than the adjacency matrix. Its eigenvalues are genuine eigenvalues of the graph, which makes the quotient useful both for finding part of a spectrum and for organizing a full calculation.
Throughout, graphs are finite and simple. For a graph \(G=(V,E)\) with \(V=\{v_1,\dots,v_n\}\), its adjacency matrix \(\mathbf A(G)\) is the \(n\times n\) matrix whose \(i,j\) entry is \(1\) if \(v_iv_j\in E\), and \(0\) otherwise. An eigenvalue \(\lambda\) of a matrix \(M\) is a scalar for which there is a nonzero vector \(x\) satisfying \(Mx=\lambda x\).
The order of the cells matters for how the matrix is written, so we use the order \(V_1,\dots,V_k\) consistently. Each \(b_{ij}\) is a nonnegative integer. In particular, \(b_{ii}\) counts neighbours in the same cell; it is not the number of edges inside that cell. Each such edge contributes one to the count at each of its endpoints.
Why Quotient Eigenvalues Are Graph Eigenvalues
For each cell \(V_i\), form its indicator vector \(\mathbf 1_{V_i}\), which has entry \(1\) at vertices in \(V_i\) and \(0\) elsewhere. Put these \(k\) vectors into the columns of an \(n\times k\) matrix \(S\). The columns are linearly independent because the cells are nonempty and disjoint.
For a vertex \(v\in V_i\), the \(v\)-entry of \(\mathbf A(G)\mathbf 1_{V_j}\) counts the neighbours of \(v\) in \(V_j\). Equitability says that this entry is \(b_{ij}\), regardless of which \(v\in V_i\) is chosen. Thus the \(j\)-th column of \(\mathbf A(G)S\) is the vector whose value on each cell \(V_i\) is \(b_{ij}\). This gives the matrix identity below.
Proof. Let \(\lambda\) be an eigenvalue of \(B\), and choose a nonzero vector \(y\) such that \(By=\lambda y\). Since the columns of \(S\) are linearly independent, \(Sy\neq 0\): otherwise \(Sy=0\) would be a nontrivial linear relation among those columns. Using \(\mathbf A(G)S=SB\), we obtain \(\mathbf A(G)(Sy)=S(By)=S(\lambda y)=\lambda(Sy)\). So \(Sy\) is a nonzero eigenvector of \(\mathbf A(G)\) with eigenvalue \(\lambda\). \(\square\)
The theorem guarantees inclusion of eigenvalues, not equality of spectra. If the graph has \(n\) vertices and the partition has \(k<n\) cells, the quotient matrix has only \(k\) eigenvalues counted with algebraic multiplicity. The remaining eigenvalues must be found by other means. Also, although \(\mathbf A(G)\) is symmetric, \(B\) need not be symmetric: the number of neighbours a vertex in \(V_i\) has in \(V_j\) need not equal the reverse count.
A Symmetry Property of Quotient Matrices
For an undirected graph, the counts in opposite directions are related by counting edges between two cells. Write \(n_i=|V_i|\). The number of edges from \(V_i\) to \(V_j\), counted from their endpoints in \(V_i\), is \(n_i b_{ij}\). Counting the same edges from endpoints in \(V_j\) gives \(n_j b_{ji}\). Thus these quantities agree.
Proof. The edge count just described gives \(n_i b_{ij}=n_j b_{ji}\). Let \(D\) be the diagonal matrix with diagonal entries \(n_1,\dots,n_k\). All these entries are positive because the cells are nonempty. Define \(C=D^{1/2}BD^{-1/2}\). Its \(i,j\) entry is \(\sqrt{n_i/n_j}\,b_{ij}\). The edge-count identity implies \(\sqrt{n_i/n_j}\,b_{ij}=\sqrt{n_j/n_i}\,b_{ji}\), so \(C_{ij}=C_{ji}\). Therefore \(C\) is symmetric, and it is similar to \(B\), since \(C=D^{1/2}BD^{-1/2}\). Similar matrices have the same eigenvalues. By the standard spectral theorem for real symmetric matrices, all eigenvalues of \(C\), and hence of \(B\), are real. \(\square\)
Worked Quotient Calculations
Worked Example: The Spectrum of a Complete Bipartite Graph
Let \(G=K_{2,3}\) have vertex set \(V=\{a,b,x,y,z\}\) and edge set \(E=\{ax,ay,az,bx,by,bz\}\). Take the partition \(V_1=\{a,b\}\), \(V_2=\{x,y,z\}\). Each vertex in \(V_1\) has zero neighbours in \(V_1\) and three in \(V_2\); each vertex in \(V_2\) has two neighbours in \(V_1\) and zero in \(V_2\). The partition is equitable, with
The characteristic polynomial is \(\det(\lambda I-B)=\lambda^2-6\), so the quotient eigenvalues are \(\sqrt 6\) and \(-\sqrt 6\). For \(\lambda=\sqrt 6\), the vector \(y=(3,\sqrt 6)^{\mathsf T}\) satisfies \(By=(3\sqrt 6,6)^{\mathsf T}=\sqrt 6\,y\). Its lift \(Sy\) gives value \(3\) at \(a,b\) and value \(\sqrt 6\) at \(x,y,z\). For \(\lambda=-\sqrt 6\), \(y=(3,-\sqrt 6)^{\mathsf T}\) satisfies \(By=(-3\sqrt 6,6)^{\mathsf T}=-\sqrt 6\,y\), giving the other lifted eigenvector.
To find the other eigenvalues, consider vectors whose coordinate sums within each cell are zero. The vector with values \(1,-1\) at \(a,b\) and zero elsewhere is sent to zero by \(\mathbf A(G)\). Two independent vectors supported on \(\{x,y,z\}\) with coordinate sum zero are also sent to zero: their sums over \(V_2\) vanish, and their coordinates on \(V_1\) remain zero. For example, use values \((1,-1,0)\) and \((1,1,-2)\) on \(x,y,z\). These are three independent zero-eigenvectors. Along with the two lifted eigenvectors, there are five independent eigenvectors for a graph on five vertices.
Check: the spectrum is \(\sqrt 6,-\sqrt 6,0,0,0\). The quotient roots satisfy \((\sqrt 6)^2=6\) and \((-\sqrt 6)^2=6\); the three additional vectors are independent because they have separate cell supports or are independent within \(V_2\). This accounts for all five dimensions.
Worked Example: A Quotient Eigenvalue Can Reappear
Let \(G=K_3\) have vertex set \(V=\{1,2,3\}\) and edge set \(E=\{12,13,23\}\). Partition the vertices as \(V_1=\{1,2\}\) and \(V_2=\{3\}\). Each vertex in \(V_1\) has one neighbour in \(V_1\) and one in \(V_2\); the vertex in \(V_2\) has two neighbours in \(V_1\) and none in \(V_2\). Hence
The quotient eigenvalues are \(2\) and \(-1\). For \(\lambda=2\), the quotient eigenvector \((1,1)^{\mathsf T}\) lifts to \((1,1,1)^{\mathsf T}\). For \(\lambda=-1\), the quotient eigenvector \((1,-2)^{\mathsf T}\) lifts to \((1,1,-2)^{\mathsf T}\). There is also a vector \((1,-1,0)^{\mathsf T}\) with eigenvalue \(-1\): multiplying by the adjacency matrix sends it to \((-1,1,0)^{\mathsf T}\), which is its negative.
Check: the three independent vectors found have eigenvalues \(2,-1,-1\), so they give the full spectrum. This example shows that the quotient eigenvalue \(-1\) does not account for all occurrences of \(-1\) in the graph spectrum.
Using a Partition to Find the Full Spectrum
A helpful strategy is to use the vectors constant on each cell for the quotient calculation, then study vectors whose coordinates sum to zero within each cell. For an equitable partition of an undirected graph, these two spaces are orthogonal. In the example below, both spaces are preserved by the adjacency matrix, allowing the full spectrum to be computed in two small pieces.
Worked Example: The Spectrum of a Path from Two Two-Vertex Cells
Let \(G=P_4\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34\}\). Use cells \(V_1=\{1,4\}\) and \(V_2=\{2,3\}\). Each vertex in \(V_1\) has zero neighbours in \(V_1\) and one in \(V_2\). Each vertex in \(V_2\) has one neighbour in each cell. Thus this partition is equitable, with \(B=\begin{pmatrix}0&1\\1&1\end{pmatrix}\). Its characteristic polynomial is \(\lambda^2-\lambda-1\), so its eigenvalues are \((1+\sqrt5)/2\) and \((1-\sqrt5)/2\).
The vectors constant on each cell form the two-dimensional space spanned by \(\mathbf 1_{V_1}\) and \(\mathbf 1_{V_2}\). The theorem gives the two quotient eigenvalues as eigenvalues of \(G\). For the remaining two dimensions, set \(u=(1,0,0,-1)^{\mathsf T}\) and \(v=(0,1,-1,0)^{\mathsf T}\). Both have coordinate sum zero in each cell. Directly using the three edges, \(\mathbf A(G)u=v\) and \(\mathbf A(G)v=u-v\). In the ordered basis \(u,v\), the adjacency action on their span is therefore represented by \(\begin{pmatrix}0&1\\1&-1\end{pmatrix}\). Its characteristic polynomial is \(\lambda^2+\lambda-1\), with roots \((-1+\sqrt5)/2\) and \((-1-\sqrt5)/2\).
The two spaces together have dimension four: the cell-constant vectors have dimension two, and \(u,v\) are independent and orthogonal to both cell indicators. The four eigenvalues are consequently \((1+\sqrt5)/2\), \((1-\sqrt5)/2\), \((-1+\sqrt5)/2\), and \((-1-\sqrt5)/2\).
Check: the quotient roots satisfy \(\lambda^2-\lambda-1=0\), while the other two satisfy \(\lambda^2+\lambda-1=0\). These are the characteristic polynomials of the two displayed \(2\times2\) matrices, and the two invariant spaces have dimensions summing to \(4=|V|\).
Common Pitfall: Averaging Counts Is Not Enough
Equitability requires the neighbour counts to be the same for every vertex in a cell. For example, let \(G=P_4\) again, with edges \(12,23,34\), but now partition it into \(V_1=\{1,2\}\) and \(V_2=\{3,4\}\). Vertex \(1\) has counts \((1,0)\) into \((V_1,V_2)\), while vertex \(2\) has counts \((1,1)\). The partition is not equitable, so the theorem does not apply.
A tempting but incorrect calculation averages the counts in each cell and forms \(\begin{pmatrix}1&1/2\\1/2&1\end{pmatrix}\). Its eigenvalues are \(3/2\) and \(1/2\), but \(3/2\) is not an eigenvalue of \(P_4\). To check this directly, the adjacency matrix of this path has characteristic polynomial \(\lambda^4-3\lambda^2+1\); at \(3/2\) the value is \(81/16-27/4+1=-11/16\), which is nonzero. The correction is not to adjust the average: this partition has no quotient matrix with the required neighbour-count meaning. Choose an equitable partition, or use a method that does not rely on the equitable-partition theorem.
Equitable partitions are useful when they expose repeated structure, but they do not automatically determine the entire spectrum. First verify the counts for every cell and every vertex in it. Then use the quotient for the cell-constant eigenvectors, and account separately for any remaining dimensions before claiming a full spectrum.
Check Your Understanding
In each question, specify the cells or eigenvectors you use and show the calculations that support your conclusion.
- For \(K_{1,3}\), partition the center from the three leaves. Find the quotient matrix and its eigenvalues.
- Give an equitable partition of a triangle with one cell of size two. Verify each neighbour count and find the quotient eigenvalues.
- Explain why the quotient matrix of an equitable partition need not be symmetric, even though the graph’s adjacency matrix is symmetric.
- For the \(P_4\) partition in the worked example, verify directly that the vectors \(u\) and \(v\) have coordinate sum zero in each cell.
- For a non-equitable partition, explain why averaging the neighbour counts does not justify applying the quotient-spectrum theorem.