Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.