 Equitable quotient matrix

An equitable quotient matrix records neighbour counts between cells of an equitable partition. For cells $C_1,\dots ,C_k$ of a finite simple graph, its entryis independent of the chosen vertex $v$ within $C_i$. Rows refer to the starting cell; columns refer to the cell containing a neighbour. This is a count per vertex, not the total number of edges between the two cells. Equitability is the property that makes these entries well-defined.^[ref]

For an original example, partition a four-vertex star graph into its centre and its three leaves. ThenThe centre has three leaf neighbours, while each leaf has one centre neighbour. The graph is undirected but its equitable quotient matrix is not a symmetric matrix. If $D=\mathrm{diag}(|C_1|,\dots ,|C_k|)$, counting each edge from both ends givesConsequently $D^{1/2}B{D}^{-1/2}$ is symmetric. For the star it is $\left(\begin{array}{cc}0& \sqrt{3}\\ \sqrt{3}& 0\end{array}\right)$. Thus an equitable quotient matrix of an undirected graph has real eigenvalues, despite its potentially asymmetric appearance.

The relation to the full adjacency matrix $A$ is exact. Let $S_{vi}=1$ when $v\in C_i$, and zero otherwise. Equitability gives $AS=SB$, as proved in equitable partition. Induction then givesSince entries of $A^r$ count occurrences of a walk in a graph between specified endpoints, $(B^r{)}_{ij}$ counts length-$r$ walks from any fixed vertex in $C_i$ to all vertices in $C_j$. In the star example, $B^2=3I$: from a leaf there are three two-step walks ending somewhere in the leaf cell, although only one returns to that particular leaf.

Compression retains the dynamics of vectors constant on each cell. It need not retain every eigenvalue or distinguish all vertices. The star's full adjacency matrix has eigenvalues $\sqrt{3},-\sqrt{3},0,0$, whereas $B$ has only $\sqrt{3},-\sqrt{3}$. Vectors taking leaf values whose sum is zero give the omitted zero-eigenvalue directions. This explains both the utility and the information loss of the quotient.