TAOCP 2.2.3 Exercise 16
Let $S = {x_1, \dots, x_n}$ be a finite set with a partial ordering $\preceq$, and let $(a_{ij})$ be its incidence matrix defined by a_{ij} = \begin{cases} 1,& \text{if } x_i \preceq x_j,\\ 0,& \text{...
Section 2.2.3: Linked Allocation
Exercise 16. [M22] Given any partial ordering on a set $S = {x_1, \ldots, x_n}$, we can construct its incidence matrix $(a_{ij})$, where $a_{ij} = 1$ if $x_i \preceq x_j$, and $a_{ij} = 0$ otherwise. Show that there is a way to permute the rows and columns of this matrix so that all entries below the diagonal are zero.
Verified: yes
Solve time: 29s
Solution
Let $S = {x_1, \dots, x_n}$ be a finite set with a partial ordering $\preceq$, and let $(a_{ij})$ be its incidence matrix defined by
$$ a_{ij} = \begin{cases} 1,& \text{if } x_i \preceq x_j,\ 0,& \text{otherwise.} \end{cases} $$
We wish to show that there exists a permutation of the rows and columns of $(a_{ij})$ such that all entries below the main diagonal are zero.
Consider a topological ordering of $S$. By definition, a topological ordering is a listing $y_1, y_2, \dots, y_n$ of the elements of $S$ such that for every pair $y_i \preceq y_j$, $i \le j$. Such an ordering exists for any finite partially ordered set (see Section 2.2.2).
Let $\pi$ be the permutation of ${1, \dots, n}$ that sends $x_{\pi(k)} = y_k$, so that row $k$ and column $k$ of the permuted matrix correspond to $y_k$. Then, for any $i > j$, the $(i,j)$ entry of the permuted incidence matrix is
$$ a'_{ij} = \begin{cases} 1,& \text{if } y_i \preceq y_j,\ 0,& \text{otherwise.} \end{cases} $$
By the property of a topological ordering, $y_i \preceq y_j$ implies $i \le j$. Since $i > j$, it follows that $y_i \not\preceq y_j$, and therefore $a'_{ij} = 0$. Consequently, all entries below the main diagonal are zero.
This permutation simultaneously rearranges the rows and columns in the same order, preserving the incidence property while producing an upper-triangular form of the matrix. This completes the proof.
∎