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?
