Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Inequalities > Inequality Methods > Rearrangement Inequality

The Rearrangement Inequality

Let (x) = x1,x2,...,xn and (y) = y1,y2,...,yn be two sequences of positive real numbers.  Then the sum

x1y1+x2y2+...+xnyn 

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, xi > xj ==> yi ≥ yj and yi > yj ==> xi ≥ xj,
or equivalently, for all i,j, xi ≤ xj or yi ≥ yj.

Two sequences, (x) and (y), are defined as ordered oppositely if for any i,j, xi > xj ==> yi ≤ yj and yi > yj ==> xi ≤ xj,
or equivalently, for all i,j, xi ≥ xj or yi ≥ yj.

Proof

When n=2, (x2-x1)(y2-y1) ≥ 0 is equivalent to x1y1+x2y2 ≥ x1y2+x2y1, and (x2-x1)(y2-y1) ≤ 0 is equivalent to x1y1+x2y2 ≤ x1y2+x2y1.
(x2-x1)(y2-y1) ≥ 0 iff (x) and (y) are ordered the same way, (x2-x1)(y2-y1) ≤ 0 iff (x) and (y) are ordered oppositely, and (x2-x1)(y2-y1) = 0 if x2=x1 or y2=y1.  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 = x1y1+x2y2+...+xnyn 

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

T = x1z1+x2z2+...+xnzn 

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 xi > xj and zi < zj.  In this case, xizi+xjzj < xizj+xjzi (the n=2 case with strict inequality), so interchanging zi and zj 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, yi=zi, 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 (mirror)

PlanetMath: Rearrangement Inequality and its proof.

Related pages in this website

The rearrangement inequality is used to prove the Chebyshev Sum Inequality.

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 this Math Help site is Graeme McRae.