proof of rearrangement inequality

We first prove the rearrangement inequality for the case n=2. Let x1,x2,y1,y2 be real numbers such that x1x2 and y1y2. Then


and therefore


Equality holds iff x1=x2 or y1=y2.

For the general case, let x1,x2,,xn and y1,y2,,yn be real numbers such that x1x2xn. Suppose that (z1,z2,,zn) is a permutation (rearrangement) of {y1,y2,,yn} such that the sum


is maximized. If there exists a pair i<j with zi>zj, then xizj+xjzixizi+xjzj (the n=2 case); equality holds iff xi=xj. Therefore, x1z1+x2z2++xnzn is not maximal unless z1z2zn or xi=xj for all pairs i<j such that zi>zj. In the latter case, we can consecutively interchange these pairs until z1z2zn (this is possible because the number of pairs i<j with zi>zj decreases with each step). So x1z1+x2z2++xnzn is maximized if


To show that x1z1+x2z2++xnzn is minimal for a permutation (z1,z2,,zn) of {y1,y2,,yn} if z1z2zn, observe that -(x1z1+x2z2++xnzn)=x1(-z1)+x2(-z2)++xn(-zn) is maximized if -z1-z2-zn. This implies that x1z1+x2z2++xnzn is minimized if

Title proof of rearrangement inequality
Canonical name ProofOfRearrangementInequality
Date of creation 2013-03-22 13:08:41
Last modified on 2013-03-22 13:08:41
Owner pbruin (1001)
Last modified by pbruin (1001)
Numerical id 4
Author pbruin (1001)
Entry type Proof
Classification msc 26D15
Related topic ChebyshevsInequality