TAOCP 6.1 Exercise 14
Let \(x_1, x_2, \dots, x_n\) and \(y_1, y_2, \dots, y_n\) be two sequences of real numbers.
Section 6.1: Sequential Searching
Exercise 14. [M21] Given two sequences $\langle x_1,x_2,\ldots,x_n\rangle$ and $\langle y_1,y_2,\ldots,y_n\rangle$ of real numbers, what permutation $a_1a_2\ldots a_n$ of the subscripts will make $\sum_i x_i y_{a_i}$ a maximum? What permutation will make it a minimum?
Verified: no
Solve time: 2m07s
Solution
Let (x_1, x_2, \dots, x_n) and (y_1, y_2, \dots, y_n) be two sequences of real numbers.
We wish to find a permutation (a_1 a_2 \dots a_n) of ({1,2,\dots,n}) that maximizes or minimizes the sum
[ S(a) = \sum_{i=1}^n x_i y_{a_i}. ]
Rearrangement Inequality
Maximum. The sum (S(a)) is maximized when the two sequences are similarly ordered: if we sort the (x)'s in non‑decreasing order, the corresponding (y_{a_i}) must also be in non‑decreasing order.
Minimum. The sum (S(a)) is minimized when the sequences are oppositely ordered: if the (x)'s are sorted in non‑decreasing order, the corresponding (y_{a_i}) must be in non‑increasing order.
Proof by Exchange Argument
Let (a) be any permutation of the subscripts. Suppose there exist indices (i < j) such that
[ x_i < x_j \quad \text{and} \quad y_{a_i} > y_{a_j}. ]
Define a new permutation (a') by swapping the values at positions (i) and (j):
[ a'_i = a_j,\qquad a'_j = a_i,\qquad a'_k = a_k ;;(k \neq i,j). ]
The change in the sum is
[ \begin{aligned} S(a') - S(a) &= x_i y_{a_j} + x_j y_{a_i} - x_i y_{a_i} - x_j y_{a_j} \ &= (x_j - x_i)(y_{a_i} - y_{a_j}) ;>; 0. \end{aligned} ]
Thus the swap strictly increases the sum.
If a permutation is not similarly ordered, such a pair ((i,j)) exists. By repeatedly applying this exchange we strictly increase (S(a)) until no such inversion remains. Because there are only finitely many permutations, the process terminates at a permutation where the sequences are similarly ordered (i.e., no (i<j) with (x_i < x_j) and (y_{a_i} > y_{a_j})). This final permutation gives the maximum possible sum.
For the minimum, suppose there exist (i<j) with (x_i < x_j) and (y_{a_i} < y_{a_j}). Swapping them yields
[ S(a') - S(a) = (x_j - x_i)(y_{a_i} - y_{a_j}) < 0, ]
so the sum strictly decreases. Repeated elimination of such inversions leads to a permutation where the sequences are oppositely ordered, which gives the minimum sum.
If some elements are equal ((x_i = x_j) or (y_{a_i} = y_{a_j})), the exchange does not change the sum. Therefore any permutation that respects the required non‑decreasing/non‑increasing relations achieves the same extremal value.
Explicit Description of the Optimal Permutations
Let (\sigma) be a permutation that sorts the (x)'s in non‑decreasing order:
[ x_{\sigma(1)} \le x_{\sigma(2)} \le \cdots \le x_{\sigma(n)}. ]
Let (\tau) be a permutation that sorts the (y)'s in non‑decreasing order:
[ y_{\tau(1)} \le y_{\tau(2)} \le \cdots \le y_{\tau(n)}. ]
(If several elements are equal, any such sorting works.)
-
Maximum sum: Take (a) such that (a_{\sigma(i)} = \tau(i)) for (i=1,\dots,n).
Equivalently, (a = \tau \circ \sigma^{-1}). -
Minimum sum: Take (a) such that (a_{\sigma(i)} = \tau(n+1-i)) for (i=1,\dots,n).
Equivalently, (a = \text{rev} \circ \tau \circ \sigma^{-1}) where (\text{rev}(i) = n+1-i).
\boxed{ \begin{array}{l} \text{The maximum of } \sum_{i=1}^n x_i y_{a_i} \text{ is attained by any permutation that pairs the } x\text{'s and } y\text{'s in the same order} \ \text{(both non‑decreasing or both non‑increasing). The minimum is attained by any permutation that pairs them} \ \text{in opposite orders (one non‑decreasing, the other non‑increasing).} \end{array} }
This completes the proof. ∎
Notes
The exchange argument shows that the extremal permutations are exactly those that eliminate all “inversions” of the specified type. The result is the classical rearrangement inequality and applies to any real sequences; the proof remains valid when ties are present because equal elements can be swapped without affecting the sum.