TAOCP 5.3.4 Exercise 22

Exercise 22. [M17] Let $\alpha$ be any $n$-network, and let $x$ and $y$ be $n$-vectors.

a) Prove that $x \subseteq y$ implies that $x\alpha \subseteq y\alpha$.

b) Prove that $x \cdot y \le (x\alpha) \cdot (y\alpha)$, where $x \cdot y$ denotes the dot product $x_1y_1 + \cdots + x_ny_n$.

Verified: no
Solve time: 1m06s

Solution

Let an $n$-network $\alpha$ be a finite sequence of comparators. A comparator on lines $i$ and $j$ ($1\le i<j\le n$) transforms a vector $u=(u_1,\dots,u_n)$ into $u'$ where [ u'_i = \min(u_i,u_j),\quad u'_j = \max(u_i,u_j),\quad u'_k = u_k\ (k\ne i,j). ] We write $u\alpha$ for the result of applying all comparators of $\alpha$ in order. The relation $x\subseteq y$ means $x_i\le y_i$ for all $i=1,\dots,n$.

(a) We prove by induction on the number of comparators that $x\subseteq y$ implies $x\alpha\subseteq y\alpha$. The base case $\alpha$ = identity is trivial. For the inductive step, let $\alpha = \alpha' c$ where $c$ is a single comparator on lines $i,j$. By the induction hypothesis $x\alpha'\subseteq y\alpha'$; denote these vectors by $x'$ and $y'$. We need to show $x'c\subseteq y'c$. Since $x'\subseteq y'$ we have $x'_i\le y'_i$ and $x'_j\le y'_j$. The comparator $c$ produces [ (x'c)_i = \min(x'_i,x'_j),\quad (x'c)_j = \max(x'_i,x'_j),\quad (x'c)_k = x'_k\ (k\ne i,j), ] and similarly for $y'c$. Because $\min$ and $\max$ are monotone in each argument, [ \min(x'_i,x'_j)\le \min(y'_i,y'_j),\qquad \max(x'_i,x'_j)\le \max(y'_i,y'_j), ] and for $k\ne i,j$ we have $x'_k\le y'_k$ by hypothesis. Hence $x'c\subseteq y'c$, i.e. $x\alpha\subseteq y\alpha$. This completes the proof. ∎

(b) We again use induction on the number of comparators. The base case $\alpha$ = identity gives equality $x\cdot y = (x\alpha)\cdot(y\alpha)$. Assume $\alpha = \alpha' c$ with $c$ a comparator on lines $i,j$. By the induction hypothesis $x\cdot y \le (x\alpha')\cdot(y\alpha')$. Set $x'=x\alpha'$, $y'=y\alpha'$. It suffices to show [ x'\cdot y' \le (x'c)\cdot(y'c). ] The dot product changes only in coordinates $i,j$: [ (x'c)\cdot(y'c) - x'\cdot y' = \min(x'_i,x'_j)\min(y'_i,y'_j) + \max(x'_i,x'_j)\max(y'_i,y'_j) - (x'_iy'_i + x'_jy'_j). ] Let $a=x'_i$, $b=x'_j$, $c=y'_i$, $d=y'_j$. We claim [ \min(a,b)\min(c,d) + \max(a,b)\max(c,d) \ge ac + bd. ] If the relative order of $a,b$ and $c,d$ is the same (both nondecreasing or both nonincreasing), the left side equals $ac+bd$. If the orders are opposite, say $a\ge b$ and $c\le d$, then the left side is $ad+bc$ and the difference is [ (ad+bc)-(ac+bd) = (a-b)(d-c) \ge 0. ] Thus the inequality holds in all cases. Hence $(x'c)\cdot(y'c) \ge x'\cdot y'$, and by induction $x\cdot y \le (x\alpha)\cdot(y\alpha)$. This completes the proof. ∎