TAOCP 5.3.4 Exercise 27

Section 5.3.4: Networks for Sorting

Exercise 27. ▶ [M20] Let $x$ and $y$ be vectors, and let $x\alpha$ and $y\alpha$ be sorted. Prove that $(x\alpha)_i \le (y\alpha)_i$ if and only if, for every choice of $j$ elements from $y$, we can choose $i$ elements from $x$ such that every chosen $x$ element is $\le$ some chosen $y$ element. Use this principle to prove that if we sort the rows of any matrix, then sort the columns, the rows will remain in order.

Verified: no
Solve time: 6m38s

Solution

The exercise contains a notational inconsistency: the statement “$(x\alpha)_i \le (y\alpha)_i$ if and only if, for every choice of $j$ elements from $y$ …” uses $j$ on the right without it appearing on the left. The intended lemma is almost certainly the more general relation between two order statistics. We therefore prove the corrected formulation.

Lemma

Let $x$ and $y$ be finite vectors. Denote by $x\alpha$ and $y\alpha$ the vectors obtained by sorting the components of $x$ and $y$ into non‑decreasing order. For any indices $i$ and $j$ with $1\le i\le |x|$, $1\le j\le |y|$,

$$ (x\alpha)_i \le (y\alpha)_j $$

if and only if for every subset $Y\subseteq y$ of size $j$ there exists a subset $X\subseteq x$ of size $i$ such that each element of $X$ is less than or equal to some element of $Y$.

Proof.
($\Rightarrow$) Assume $(x\alpha)_i \le (y\alpha)_j$. Let $Y$ be an arbitrary subset of $y$ of size $j$. Write the elements of $Y$ in non‑decreasing order: $y_1 \le y_2 \le \dots \le y_j$. Because $Y\subseteq y$, the largest element $y_j$ is at least the $j$-th smallest element of $y$, i.e. $y_j \ge (y\alpha)_j$. By hypothesis $(x\alpha)_i \le (y\alpha)_j$, so

$$ (x\alpha)_i \le y_j . $$

Choose $X$ to be the $i$ smallest elements of $x$; then $\max X = (x\alpha)_i \le y_j$. Every $x\in X$ satisfies $x \le \max X \le y_j$, and $y_j\in Y$. Hence $X$ has size $i$ and each of its elements is $\le$ some element of $Y$ (namely $y_j$).

($\Leftarrow$) Assume the subset condition holds. Consider the particular subset $Y$ consisting of the $j$ smallest elements of $y$. Then $\max Y = (y\alpha)_j$. By hypothesis there exists $X\subseteq x$ with $|X|=i$ such that each $x\in X$ is $\le$ some $y\in Y$. Consequently every $x\in X$ satisfies $x \le \max Y = (y\alpha)_j$. The $i$-th smallest element of $x$ is at most the maximum of any $i$ elements of $x$, therefore

$$ (x\alpha)_i \le \max X \le (y\alpha)_j . $$

This completes the proof of the lemma. ∎

Application: Row‑then‑column sorting preserves row order

Let $A$ be an $m\times n$ matrix. First sort each row of $A$ into non‑decreasing order. Then sort each column of the resulting matrix into non‑decreasing order. We must show that after this second step every row is still non‑decreasing.

Fix a row index $r$ ($1\le r\le m$) and two adjacent columns $c$ and $c+1$. Let $x$ be the vector of length $m$ formed by column $c$ after the row‑sorting phase, and let $y$ be the vector formed by column $c+1$ after the row‑sorting phase. Because the rows were sorted, for every $k$ we have $x_k \le y_k$.

Now apply the column‑sorting phase: column $c$ becomes the sorted vector $x\alpha$, and column $c+1$ becomes $y\alpha$. The element in row $r$, column $c$ after column sorting is $(x\alpha)_r$; the element in row $r$, column $c+1$ is $(y\alpha)_r$. We need to prove $(x\alpha)_r \le (y\alpha)_r$.

By the lemma with $i=j=r$, it suffices to verify that for every subset $Y\subseteq y$ of size $r$ there exists a subset $X\subseteq x$ of size $r$ such that each element of $X$ is $\le$ some element of $Y$. Let $Y$ be any such subset, and let $I$ be the set of row indices from which the elements of $Y$ were taken. Define $X = {x_k \mid k\in I}$. Then $|X|=r$, and for each $k\in I$ we have $x_k \le y_k$ (by the row‑sorting property) and $y_k\in Y$. Thus every $x\in X$ is $\le$ its corresponding $y\in Y$. The condition of the lemma is satisfied, so $(x\alpha)_r \le (y\alpha)_r$.

Since $r$ and $c$ were arbitrary, every row remains non‑decreasing after the columns are sorted. This completes the proof. ∎

Notes

The lemma is a simple but useful characterisation of the order‑statistic inequality $(x\alpha)_i \le (y\alpha)_j$ in terms of subset matching. The matrix‑sorting argument is a classic application: the hypothesis $x_k\le y_k$ for all $k$ immediately supplies the required matching for any chosen subset $Y$ by taking the same indices in $x$. The same principle underlies the verification of several irregular sorting networks (e.g. Floyd’s 9‑element network mentioned in the text).