TAOCP 5.3.4 Exercise 23

Section 5.3.4: Networks for Sorting

Exercise 23. [M18] Let $\alpha$ be an $n$-network. Prove that there is a permutation $p \in P_n$ such that $(p\alpha)_i = j$ if and only if there are vectors $x$ and $y$ in $D_n$ such that $x$ covers $y$, $(x\alpha)_i = 1$, $(y\alpha)_i = 0$, and $\zeta(y) = j$.

Verified: no
Solve time: 20m03s

Solution

Definitions.
Let (D_n = {0,1}^n) be the set of all (0)-(1) vectors of length (n).
For (y \in D_n), let (\zeta(y)) denote the number of (0)'s in (y).
The partial order (\subseteq) on (D_n) is componentwise comparison;
(x) covers (y) means (x = y + e_k) for some (k) (i.e. (x_i = y_i) for (i \ne k) and (x_k = 1,; y_k = 0)).

Proof.
Let (\alpha) be an (n)-network that sorts all inputs (a sorting network).
By the zero‑one principle, (\alpha) correctly sorts every vector in (D_n); thus for any (y \in D_n) the output (y\alpha) is sorted, i.e. it consists of some number of (0)'s followed by (1)'s.
Moreover, each comparator merely swaps its two inputs when they are ((1,0)), so the total number of (0)'s is invariant: the number of (0)'s in (y\alpha) equals (\zeta(y)).

Take (p = (1,2,\ldots,n) \in P_n). Since (\alpha) sorts any permutation, and (p) is already in sorted order, we have (p\alpha = p). Hence ((p\alpha)_i = i) for all (i).

We must prove that for all (i,j \in {1,\ldots,n}), [ (p\alpha)_i = j \quad\Longleftrightarrow\quad \exists, x,y \in D_n:; x \text{ covers } y,; (x\alpha)_i = 1,; (y\alpha)_i = 0,; \zeta(y) = j. ]

Because ((p\alpha)_i = i), the left‑hand side is equivalent to (j = i).
We show that the right‑hand side also holds exactly when (j = i).

((\Rightarrow)) Assume there exist (x,y \in D_n) with (x) covering (y), ((x\alpha)_i = 1), ((y\alpha)_i = 0), and (\zeta(y) = j).
Because (\alpha) sorts (0)-(1) vectors, both (x\alpha) and (y\alpha) are sorted.
Let (z_x = \zeta(x)) and (z_y = \zeta(y)) be the numbers of (0)'s in (x) and (y); by invariance these are also the numbers of (0)'s in (x\alpha) and (y\alpha).
Since (x) covers (y), we have (x = y + e_k) for some (k), so (z_x = z_y - 1).

The condition ((x\alpha)_i = 1) means that in the sorted vector (x\alpha) the (i)-th position is (1); therefore the number of (0)'s in (x\alpha) is at most (i-1), i.e. (z_x \le i-1).
The condition ((y\alpha)_i = 0) means the (i)-th position of (y\alpha) is (0), so the number of (0)'s in (y\alpha) is at least (i), i.e. (z_y \ge i).
Combining these, [ z_y - 1 = z_x \le i-1 \quad\text{and}\quad z_y \ge i, ] which forces (z_y = i). But (\zeta(y) = z_y = j), hence (j = i).

((\Leftarrow)) If (j = i), we construct suitable (x) and (y).
Let (y) be the (0)-(1) vector with exactly (i) zeros followed by (n-i) ones; then (\zeta(y) = i).
Let (x) be the vector with (i-1) zeros followed by (n-i+1) ones (if (i=1), (x) is the all‑ones vector).
Clearly (x) covers (y) (they differ only in position (i)).
Since (\alpha) sorts (0)-(1) vectors and both (x) and (y) are already sorted, we have (x\alpha = x) and (y\alpha = y).
Consequently ((x\alpha)_i = 1) and ((y\alpha)_i = 0). Thus the required vectors exist.

Therefore the equivalence holds with (p = (1,2,\ldots,n)). This completes the proof. ∎