proof of rearrangement inequality

We first prove the rearrangement inequality for the case $n=2$. Let $x_1,x_2,y_1,y_2$ be real numbers such that $x_1\le x_2$ and $y_1\le y_2$. Then

$$(x_2-x_1)(y_2-y_1)\ge 0,$$

and therefore

$$x_1{y}_1+x_2{y}_2\ge x_1{y}_2+x_2{y}_1.$$

Equality holds iff $x_1=x_2$ or $y_1=y_2$.

For the general case, let $x_1,x_2,\mathrm{\dots },x_n$ and $y_1,y_2,\mathrm{\dots },y_n$ be real numbers such that $x_1\le x_2\le \mathrm{\cdots }\le x_n$. Suppose that $(z_1,z_2,\mathrm{\dots },z_n)$ is a permutation (rearrangement) of $\{y_1,y_2,\mathrm{\dots },y_n\}$ such that the sum

$$x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n$$

is maximized. If there exists a pair with $z_i>z_j$, then $x_i{z}_j+x_j{z}_i\ge x_i{z}_i+x_j{z}_j$ (the $n=2$ case); equality holds iff $x_i=x_j$. Therefore, $x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n$ is not maximal unless $z_1\le z_2\le \mathrm{\cdots }\le z_n$ or $x_i=x_j$ for all pairs such that $z_i>z_j$. In the latter case, we can consecutively interchange these pairs until $z_1\le z_2\le \mathrm{\cdots }\le z_n$ (this is possible because the number of pairs with $z_i>z_j$ decreases with each step). So $x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n$ is maximized if

$$z_1\le z_2\le \mathrm{\cdots }\le z_n.$$

To show that $x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n$ is minimal for a permutation $(z_1,z_2,\mathrm{\dots },z_n)$ of $\{y_1,y_2,\mathrm{\dots },y_n\}$ if $z_1\ge z_2\ge \mathrm{\cdots }\ge z_n$, observe that $-(x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n)=x_1(-z_1)+x_2(-z_2)+\mathrm{\cdots }+x_n(-z_n)$ is maximized if $-z_1\le -z_2\le \mathrm{\cdots }\le -z_n$. This implies that $x_1{z}_1+x_2{z}_2+\mathrm{\cdots }+x_n{z}_n$ is minimized if

$$z_1\ge z_2\ge \mathrm{\cdots }\ge z_n.$$

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