# document.write (document.title)

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