The Rearrangement Inequality

Let (x) = x₁,x₂,...,x_n and (y) = y₁,y₂,...,y_n be two sequences of positive real numbers.  Then the sum

x₁y₁+x₂y₂+...+x_ny_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₂-x₁)(y₂-y₁) ≥ 0 is equivalent to x₁y₁+x₂y₂ ≥ x₁y₂+x₂y₁, and (x₂-x₁)(y₂-y₁) ≤ 0 is equivalent to x₁y₁+x₂y₂ ≤ x₁y₂+x₂y₁.
(x₂-x₁)(y₂-y₁) ≥ 0 iff (x) and (y) are ordered the same way, (x₂-x₁)(y₂-y₁) ≤ 0 iff (x) and (y) are ordered oppositely, and (x₂-x₁)(y₂-y₁) = 0 if x₂=x₁ or y₂=y₁.  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₁y₁+x₂y₂+...+x_ny_n 

is not maximized.  Then a permutation, (z), of (y) exists such that the sum,

T = x₁z₁+x₂z₂+...+x_nz_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_iz_i+x_jz_j < x_iz_j+x_jz_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.

Internet References

The Rearrangement Inequality, by K. Wu, South China Normal University, China and and Andy Liu, University of Alberta, Canada

PlanetMath: Rearrangement Inequality and its proof.

Related pages in this website

The AM-GM Inequality: the Arithmetic Mean of positive numbers is always greater than the Geometric Mean.  This is proved using Jensen's Inequality.

The Cauchy-Schwarz inequality

The Triangle Inequality

Puzzles

The Quadratic Formula

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]