
Let (x) = x_{1},x_{2},...,x_{n} and (y) = y_{1},y_{2},...,y_{n} be two sequences of positive real numbers. Then the sum
x_{1}y_{1}+x_{2}y_{2}+...+x_{n}y_{n}
is maximized when (x) and (y) are ordered the same way (e.g. both in ascending order or both in descending order), and the sum is minimized when (x) and (y) are ordered oppositely, with equality iff (x) is constant or (y) is constant.
Definitions
Two sequences, (x) and (y), are defined as ordered the same way if for
any i,j, x_{i} > x_{j} ==> y_{i} ≥ y_{j}
and y_{i} > y_{j} ==> x_{i} ≥ x_{j},
or equivalently, for all i,j, x_{i} ≤ x_{j} or y_{i}
≥ y_{j}.
Two sequences, (x) and (y), are defined as ordered oppositely if for
any i,j, x_{i} > x_{j} ==> y_{i} ≤ y_{j}
and y_{i} > y_{j} ==> x_{i} ≤ x_{j},
or equivalently, for all i,j, x_{i} ≥ x_{j} or y_{i}
≥ y_{j}.
Proof
When n=2, (x_{2}x_{1})(y_{2}y_{1}) ≥ 0 is
equivalent to x_{1}y_{1}+x_{2}y_{2} ≥ x_{1}y_{2}+x_{2}y_{1},
and (x_{2}x_{1})(y_{2}y_{1}) ≤ 0 is equivalent
to x_{1}y_{1}+x_{2}y_{2}
≤ x_{1}y_{2}+x_{2}y_{1}.
(x_{2}x_{1})(y_{2}y_{1}) ≥ 0 iff (x) and (y)
are ordered the same way, (x_{2}x_{1})(y_{2}y_{1})
≤ 0 iff (x) and (y) are ordered oppositely, and (x_{2}x_{1})(y_{2}y_{1})
= 0 if x_{2}=x_{1} or y_{2}=y_{1}. This
completes the proof of the n=2 case.
When n>2, suppose (x) and (y) are ordered the same way, but the sum,
S = x_{1}y_{1}+x_{2}y_{2}+...+x_{n}y_{n}
is not maximized. Then a permutation, (z), of (y) exists such that the sum,
T = x_{1}z_{1}+x_{2}z_{2}+...+x_{n}z_{n}
is maximal, with T larger than S. If (x) and (z) were not ordered the same way, then an i,j would exist such that x_{i} > x_{j} and z_{i} < z_{j}. In this case, x_{i}z_{i}+x_{j}z_{j} < x_{i}z_{j}+x_{j}z_{i} (the n=2 case with strict inequality), so interchanging z_{i} and z_{j} would result in a larger sum, contradicting maximality, so (x) and (z) are ordered the same way.
Now we have (x) and (y) ordered the same way, giving a sum of S, and (x) and (z) ordered the same way, giving a larger sum of T>S. But since (y) is a permutation of (z) and (y) and (z) are ordered the same way, so for all i, y_{i}=z_{i}, and thus T=S.
The Rearrangement Inequality, by K. Wu, South China Normal University, China and and Andy Liu, University of Alberta, Canada (mirror)
PlanetMath: Rearrangement Inequality and its proof.
The rearrangement inequality is used to prove the Chebyshev Sum Inequality.
The AMGM Inequality: the Arithmetic Mean of positive numbers is always greater than the Geometric Mean. This is proved using Jensen's Inequality.
The webmaster and author of this Math Help site is Graeme McRae.