In the previous post I looked at binary relations on finite sets; in this post I’m going to prove a few properties specific to the matrices giving partial orders on a finite set (I will equivalently call them poset matrices or incidence matrices). So let $(X,\leq)$ be a finite poset. By definition this means that $X$ is a finite set and the following 3 properties hold:
- reflexivity: $a \leq a$ for all $a \in X$
- antisymmetry: $\forall a, b \in X,$ $a\leq b \wedge b\leq a \implies a=b$
- transitivity: $\forall a,b,c\in X,$ $a\leq b \wedge b\leq c \implies a\leq c$.
This is distinguished from a total order by how it is not necessarily the case that any particular $a$ and $b$ in $X$ are comparable.
As a binary relation, the partial order is equivalent to a subset $R$ of $X \times X$, where $(a,b) \in R \iff a \leq b$, so $R$ collects the pairs of elements with one less than the other. Letting $\sigma : \{1,\dots,n\} \to X$ be a permutation, $X$ can be enumerated and $R$ represented via a binary matrix $A$ with
$$
A_{ij} = 1 \iff \sigma(i)\leq \sigma(j) \iff (\sigma(i), \sigma(j)) \in R.
$$
I’ll use $\mathcal R_n$ to denote the subset of $\{0,1\}^{n\times n}$ giving all valid poset matrices.
In this post I’m going to prove a few results about poset matrices, and then finish with an example. As discussed in my previous post, I know that different enumerations can lead to different poset matrices, but they are equivalent with respect to the equivalence relation $A\sim B \iff A=PBP^T$ for some permutation matrix $P$. My goal in this post is to better understand the equivalence classes of $\sim$ as well as to just practice working with posets a bit.
Upper triangular poset matrices
The first main result will be that every equivalence class of $\sim$ has an upper triangular matrix in it. I’ll build up to this by proving two helper lemmas. I’ll need the concept of maximality, where an $x \in X$ is defined to be maximal if for all $y \in X$ $x \leq y \implies x = y$, i.e. nothing is bigger than it.
Lemma 1: every non-empty finite poset has a maximal element.
Pf: Suppose not, so that $(X,\leq)$ is a non-empty poset with no maximal element. Let $x_1 \in X$. Then there exists an $x_2\in X$ with $x_2 \neq x_1$ such that $x_1 \leq x_2$. $x_2$ is also not maximal so there’s an $x_3\in X$ such that $x_2 \leq x_3$ and $x_3 \neq x_2$. This means $x_1\leq x_2 \leq x_3 \implies x_1\leq x_3$ by transitivity.
Suppose $x_3 \leq x_1$. Then by antisymmetry $x_1 = x_3$, which again by antisymmetry means $x_1 = x_2$. But $x_2 \neq x_1$ so this is a contradition. Therefore it cannot be that $x_3 \leq x_1$ so I have an increasing chain of $3$ distinct elements.
In general, suppose I have a chain of $k < n$ distinct elements (and I know I can have this, at least up to $k=3$). By assumption, $x_k$ is not maximal so there is an $x_{k+1} \in X$ such that $x_k \leq x_{k+1}$ and $x_k \neq x_{k+1}$. Suppose $x_{k+1}$ appears earlier in the chain. Then by transitivity I’d have $x_{k+1} \leq x_k$, and by antisymmetry this gives me $x_k = x_{k+1}$. That’s a contradiction so it must be that $x_{k+1}$ appears nowhere in the chain. This means that for any chain of length $k < n$ I can produce a chain of length $k + 1$, so I can continue this process until I have enumerated all of $X$. Then $x_n$, the last element in the chain, is greater than every other element of the chain, and therefore $X$, which makes it maximal. This contradicts my original assumption that there exists a poset with no maximal element, so it must be that every non-empty finite poset has a maximal element.
$\square$
This feels very Zorn-like: Zorn’s lemma says that if every chain in a poset has an upper bound then there is a maximal element. So let $C\subseteq X$ be a chain in $X$. Then because $X$ is finite $C$ has at most $n$ elements, so there’s no issue with finding the biggest element in $C$ which is an upper bound for it. Note how the finiteness of $X$ is key, as otherwise the chain could go forever and never have an upper bound in it (an example would be $\mathbb N$ with the usual order: every infinite subset is a chain with no upper bound in $\mathbb N$). So Zorn’s lemma could have been used, but I wanted to prove this more from first principles, and since the results here don’t depend on the axiom of choice I’d rather not invoke Zorn.
Lemma 2: any subset of a poset $(X, \leq)$ is a poset with respect to $\leq$.
Pf: Let $X$ be a poset and consider $Y\subseteq X$. If $Y=\emptyset$ then $Y$ is trivially a poset, as not being a poset would require the existence of an element which violates the conditions. So WLOG suppose $Y \neq \emptyset$ and let $a, b, c \in Y$. For all three properties, $Y\subseteq X$ means that $a,b,c \in X$ so by $X$ being a poset, it must be that $a\leq a$, $a\leq b \wedge b \leq a \implies a=b$, and $a\leq b \leq c \implies a\leq c$ in $X$, and therefore in $Y$.
$\square$
Now I’m ready to prove one of my main results:
Result 1: Any finite poset $(X,\leq)$ can be enumerated in such a way that $A$ is upper triangular.
Pf: let $M_0 = \{x \in X : x \text{ is maximal}\}$ and by Lemma 1 $M_0$ is not empty. Define $X_1 = X \backslash M_0$. If $X_1$ is empty, stop, or else take $M_1$ to be the maximal elements of $X_1$ (and by Lemma 2, $X_1\subseteq X$ means Lemma 1 also applies to $X_1$). Continue this process so $X_k = X_{k-1} \backslash M_{k-1}$.
Now I claim that this process will eventually terminate as some $X_k$ will be empty.
Suppose not. Then there will be at least $n+1$ $M_k$, and each one is non-empty and disjoint. $\cup_j M_j$ will therefore have at least $n+1$ elements, but this is a subset of $X$ which only has $n$ elements so this is a contradition. Therefore the process terminates eventually.
So I’ve got a collection $M_0,\dots,M_m$ that partitions $X$ into non-empty pieces. Let $\sigma$ be any permutation that first enumerates the elements of $M_m$ (in any order), then the elements of $M_{m-1}$, and so on, ending with enumerating the elements of $M_0$. $A$ will be the relation matrix for $\sigma$.
By definition
$$
A_{\sigma^{-1}(x),\sigma^{-1}(y)} = 1 \iff x \leq y.
$$
Let $x, y \in X$ and suppose $x \leq y$. The diagonal of $A$ is necessarily $1$ so WLOG take $x \neq y$.
If they are both in the same $M_k$ then both are maximal in the same $X_k$, but $x < y$ which is not possible, so it must be that instead $x \in M_k$ and $y \in M_j$ for $k \neq j$. If $j > k$ then $y \in X_k$ which means $y$ was considered when $x$ was found to be maximal. This can’t be true, so it must be that $j < k$, i.e. $y$ was already removed when $x$ was found to be maximal in $X_k$.
Now $\sigma$ was chosen to first enumerate $M_m$, then $M_{m-1}$, and etc. This means that every element of $\sigma^{-1}(M_k)$ is less than every element of $\sigma^{-1}(M_j)$ because $j < k$. In particular, this means $\sigma^{-1}(x) < \sigma^{-1}(y)$. Thus I have just shown that
$$
x \leq y \implies \sigma^{-1}(x) < \sigma^{-1}(y),
$$
or in other words $A$ can only have an entry of $1$ if the row index is less than (or equal to, in the case of diagonal elements) the column index. By definition this means $A$ is upper triangular.
$\square$
I can basically rephrase this into the following corollary:
Corollary 1: for any poset $(X, \leq)$ and enumeration with incidence matrix $A$, there is some upper triangular matrix $U$ such that $A \sim U$.
Pf: By Result 1 I know that there exists an enumeration of $X$ such that the incidence matrix, say $U$, is upper triangular. Then by Result 3 of my previous post on this subject, $U$ will be equivalent to the poset matrix of any other enumeration.
$\square$
Thus any enumeration’s poset matrix is equivalent to an upper triangular poset matrix, or in other words, every equivalence class of $\sim$ has at least one upper triangular element. So long as everything I care about does not depend on the particular enumeration, this lets me freely choose an upper triangular matrix to represent my poset.
Another consequence of Result 1 is Hasse diagrams. For two elements $x$ and $y$ in $X$ I’ll say $y$ covers $x$ if $x < y$ and there is no other $z$ such that $x < z < y$. A Hasse diagram visualizes a finite poset by a directed graph where there is an edge $x \to y$ iff $y$ covers $x$. In the language of the proof of Result 1, the “top” of the Hasse diagram will be the elements of $M_0$ as these are maximal so nothing covers them. It must be that every element of $M_1$ is covered by some element of $M_0$, as each element of $M_1$ is just one element shy of being maximal, so the elements of $M_1$ come next. Continuing on, any element $x \in M_k$ for $k > 1$ is necessarily covered by something in some $M_j$ with $j < k$, as $x$ is not maximal but $X$ being finite means there can’t always be a $z$ in between any $x$ and $y$ with $x < y$. So ultimately, the Hasse diagram captures the same notion of upper triangular-ness that Result 1 described, but in a permutation-free way because it’s working with sets, not indices. This gives an intuitive idea for why the Hasse diagram uniquely specifies a finite poset.
Comparison with a different equivalence relation
Moving on, I want to consider a different equivalence relation and see how it compares to $\sim$. Consider the function $f : \mathcal R_n \to \mathbb N$ defined by
$$
f(A) = \mathbf 1^TA\mathbf 1- n
$$
so $f$ counts the number of non-zero off-diagonal elements of $A$.I’m choosing to subtract $n$ so that $\min_{A \in \mathcal R_n} f(A) = 0$ rather than $-n$ (and the argminimum is the trivial partial order $I_n$), but it doesn’t really matter. I’ll say $A \sim_f B$ iff $f(A) = f(B)$. I know this is an equivalence relation because it corresponds to the partition given by the preimages of $f$.
Result 2: if $A \sim B$ then $f(A) = f(B)$, but $f(A)=f(B)$ does not necessarily imply $A\sim B$.
Pf: suppose $A\sim B$. Then $A =PBP^T$ so
$$
f(A) = f(PBP^T) = \mathbf 1^TPBP^T\mathbf 1 – n
$$
$$
= (P^T\mathbf 1)^TB(P^T\mathbf 1) – n.
$$
$\mathbf 1$ is an eigenvector of $P^T$ with eigenvalue $1$ (or in other words, it’s just itself when permuted) so $P^T\mathbf 1 = \mathbf 1$ and therefore $f(A) = f(B)$. Thus two equivalent matrices will always have the same number of non-zero elements, which makes sense. Permuting a matrix can’t change the values in it.
For the other direction, I want to think about how much a permutation can change a matrix. Suppose I have $PAP^T$ where $P$ encodes $\sigma$. $PA$ shuffles the rows, which leaves the column sums unchanged, and then $PAP^T$ shuffles the columns, so the unique column sums are unchanged although they appear in different spots now. So if I’m looking for two matrices with the sums of the column sums being the same, but the matrices are equivalent, then I should try to find two matrices with column sums that add to the same thing but are not permutations of each other. Trying to find an explicit example of $f(A)=f(B)$ with $A\not\sim B$, I’ll try having $(1,1,1,1,3)$ be the sorted column sums of $A$, and $(1,1,1,2,2)$ will be the sorted column sums of $B$.
Take
$$
A =\left(\begin{array}{ccccc}1&0&0&1&0 \\ 0&1&0&1&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&0&0&0&1\end{array}\right)
$$
and
$$
B =\left(\begin{array}{ccccc}1&0&0&1&0 \\ 0&1&0&0&1 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&0&0&0&1\end{array}\right).
$$
These are both valid poset matrices and $f(A) = f(B)$. But $A \not\sim B$ because conjugation with a permutation matrix leaves the unique column sums unchanged, yet $A$ has one column that sums to $3$ while $B$ does not, so it cannot be that they are equivalent.
$\square$
This then means that $\sim_f$ induces a partition, and $\sim$ exactly refines that, because every equivalence class of $\sim_f$ can be formed by combining some equivalence classes of $\sim$.
An example: vertices of a hypercube
At this point I want to think through an example. Consider the vertices of the $n$-dimensional hypercube $C := \{0,1\}^n$, and for two vertices $u$ and $v$ say $u\leq_C v$ if $v$ is on a path from $u$ to the apex vertex $(1,\dots, 1)$ where each step moves forward one vertex (so e.g. if $n=4$ $(0,1,1,0)\to(1,1,1,0)$ is a legal move but $(0,1,1,0)\to(1,0,1,0)$ is not because this did not just advance one step towards the apex from the origin). Note that this makes $(0,\dots,0)$ the unique minimal element and $(1,\dots,1)$ is the unique maximal element, and a path from the origin to the apex vertex consists of changing $0$s to $1$s one at a time in $(0,\dots,0)$ until all $n$ elements are $1$s. This example is actually just a specific example of a general type of poset formed by a DAG ordered by reachability, but I like the cube visual.
This is a valid partial order: let $u,v,w$ be vertices. Then certainly $u \leq_C u$ so this is reflexive. Next, suppose $u\leq_C v$ and $v\leq_C u$. Then this means $v$ is on a path from $u$ to the apex, and vice versa $u$ is on a path from $v$ to the apex. Each path never revisits a point so this is only possible if they are the same point, so $\leq_C$ is antisymmetric. Finally, suppose $u\leq_C v\leq_C w$. Then $w$ is on a path from $u$ so $u\leq_C w$ too.
In terms of Result 1 I have $M_0 = \{(1,\dots,1)\}$, and then the maximal elements of $C\backslash M_0$ are the $n$ vertices that are one step away from the apex vertex, which mean they are $(1,\dots,1)$ except with a single coordinate set to $0$. Continuing, $M_{2}$ will be the ${n \choose 2}$ elements with exactly two zeroes, so in general $M_k$ will have ${n \choose k}$ elements; the fact that these partition $C$, which has $2^n$ elements, is a way to see
$$
2^n = \sum_{k=0}^{n} {n \choose k}.
$$
By virtue of being a partition, $\{M_k\}$ gives an equivalence relation on $C$ where $u \sim_C v$ if and only if they are in the same $M_k$, which means they have the same number of zeroes, or equivalently $\|u\|_1 = \|v\|_1$. Thus the $M_k$ can be thought of as concentric circles around the origin with respect to $\|\cdot\|_1$ and this equivalence class collapses all points on a circle with the same radius. Once this happens it becomes a total order as each equivalence class can be identified with the number of non-zero values its elements have, so I’m left with basically the path graph $0\to\dots\to n$, or isomorphically, the segment $\{0,\dots,n\}$, since all the possible paths are collapsed to fundamentally one path that just advances one unit from the origin each step.
Result 3: $(C, \leq_C)$ is order isomorphic to $(2^n, \subseteq)$, i.e. the powerset of $\{1,\dots,n\}$ partially ordered by subset inclusion.
Pf: let $g : C \to 2^n$ be defined by
$$
g(u) = \{i : u_i = 1\}
$$
so I’m thinking of a vertex on the cube as being an indicator vector for a subset of $\{1,\dots,n\}$.
Let $S \in 2^n$. $C$ has every possible binary vector of length $n$, so in particular $(\mathbf 1_{1 \in S}, \mathbf 1_{2\in S}, \dots, \mathbf 1_{n \in S} ) \in C$ and this vector maps to $S$, so $g$ is surjective.
Now suppose $g(u) = g(v)$. Then for any $i \in \{1,\dots, n\}$, $i \in g(u) \iff i \in g(v)$, so $u_i = 1 \iff v_i =1$. Since $u_i, v_i \in \{0,1\}$ this means $u_i = v_i$. $i$ was arbitrary so $u = v$ and therefore $g$ is injective. This makes $g$ a bijection.
Now I just need to show that $g$ is order preserving. Suppose $u \leq_C v$. Then $u_i = 1 \implies v_i = 1$ since there is a path going towards the apex from $u$ through $v$. This means $j \in g(u) \implies j \in g(v)$, which exactly means $g(u)\subseteq g(v)$. Thus $g$ gives an order isomorphism between the path on the vertices of a hypercube and the power set of $\{1,\dots,n\}$ ordered by inclusion.
This can be visually confirmed by imagining the Hasse diagram for these isomorphic posets. In both cases, there is a single maximal element, $(1,\dots,1)$ in $C$ and $\{1,\dots,n\}$ in $2^n$. This is followed by $n$ elements in $M_1$, and so on, so the Hasse diagrams will be identical which confirms the isomorphism I just proved.
$\square$