# Counting equivalence classes in the transitive closure of two equivalence relations

Let $X$ be a finite set, and let $P_i$ and $Q_j$ be two partitions of $X$:

$$\bigsqcup_i P_i = \bigsqcup_j Q_j = X.$$

The finest partition which is nevertheless coarser than both $P$ and $Q$ is called their transitive closure''.

For the purposes of exposition, here is an example of two partitions of the set $X=\{1, 2,..., 8\}$.

$$X=\{1,2,3\} \sqcup \{4,5\} \sqcup \{6,7,8\}$$ $$X=\{1,3\} \sqcup \{2,4\} \sqcup \{5\} \sqcup \{6,7\} \sqcup \{8\}$$

We now form the incidence matrix of each partition. Each row in the incidence matrix corresponds to a part of the partition; each column corresponds to an element of $X$. The entry is a $1$ if the element is in the part, and $0$ otherwise:

$$T_P = \left( \begin{array}{cccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{array} \right)$$ $$T_Q = \left( \begin{array}{cccccccc} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)$$

Finally, we stack these two matrices in a block matrix:

$$T_{P \cup Q} = \left( \begin{array}{cccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right).$$

But now we notice that the left nullspace of $T_{P \cup Q}$ is spanned by two vectors:

$$N_{P \cup Q} = \left( \begin{array}{ccccccc} 0 & 0 & -1 & 0 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 & 1 & 0 & 0 \\ \end{array} \right)$$

and these vectors describe the parts of the transitive closure. In particular, the dimension of the nullspace is the number of parts in the transitive closure.

Does anyone know a name for this lemma? Does anyone have a reference?

-