= Equitable quotient matrix
{title2=$B=(b_{ij})$}
An <equitable quotient matrix> records neighbour counts between cells of an <equitable partition>. For cells $C_1,\ldots,C_k$ of a finite <simple graph>, its entry
$$
B_{ij}=|N(v)\cap C_j|\qquad(v\in C_i)
$$
is 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.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Section 3.1, equitable neighbour counts]{ref}
For an original example, partition a four-vertex <star graph> into its centre and its three leaves. Then
$$
B=\begin{pmatrix}0&3\\1&0\end{pmatrix}.
$$
The 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=\operatorname{diag}(|C_1|,\ldots,|C_k|)$, counting each edge from both ends gives
$$
DB=B^TD.
$$
Consequently $D^{1/2}BD^{-1/2}$ is <symmetric>. For the star it is $\begin{pmatrix}0&\sqrt3\\\sqrt3&0\end{pmatrix}$. 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 gives
$$
A^rS=SB^r\qquad(r=0,1,2,\ldots).
$$
Since 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 $\sqrt3,-\sqrt3,0,0$, whereas $B$ has only $\sqrt3,-\sqrt3$. 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.
Back to article page
