# 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}\leq x_{2}$ and $y_{1}\leq y_{2}$. Then

 $(x_{2}-x_{1})(y_{2}-y_{1})\geq 0,$

and therefore

 $x_{1}y_{1}+x_{2}y_{2}\geq 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},\ldots,x_{n}$ and $y_{1},y_{2},\ldots,y_{n}$ be real numbers such that $x_{1}\leq x_{2}\leq\cdots\leq x_{n}$. Suppose that $(z_{1},z_{2},\ldots,z_{n})$ is a permutation (rearrangement) of $\{y_{1},y_{2},\ldots,y_{n}\}$ such that the sum

 $x_{1}z_{1}+x_{2}z_{2}+\cdots+x_{n}z_{n}$

is maximized. If there exists a pair $i with $z_{i}>z_{j}$, then $x_{i}z_{j}+x_{j}z_{i}\geq 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}+\cdots+x_{n}z_{n}$ is not maximal unless $z_{1}\leq z_{2}\leq\cdots\leq z_{n}$ or $x_{i}=x_{j}$ for all pairs $i such that $z_{i}>z_{j}$. In the latter case, we can consecutively interchange these pairs until $z_{1}\leq z_{2}\leq\cdots\leq z_{n}$ (this is possible because the number of pairs $i with $z_{i}>z_{j}$ decreases with each step). So $x_{1}z_{1}+x_{2}z_{2}+\cdots+x_{n}z_{n}$ is maximized if

 $z_{1}\leq z_{2}\leq\cdots\leq z_{n}.$

To show that $x_{1}z_{1}+x_{2}z_{2}+\cdots+x_{n}z_{n}$ is minimal for a permutation $(z_{1},z_{2},\ldots,z_{n})$ of $\{y_{1},y_{2},\ldots,y_{n}\}$ if $z_{1}\geq z_{2}\geq\cdots\geq z_{n}$, observe that $-(x_{1}z_{1}+x_{2}z_{2}+\cdots+x_{n}z_{n})=x_{1}(-z_{1})+x_{2}(-z_{2})+\cdots+% x_{n}(-z_{n})$ is maximized if $-z_{1}\leq-z_{2}\leq\cdots\leq-z_{n}$. This implies that $x_{1}z_{1}+x_{2}z_{2}+\cdots+x_{n}z_{n}$ is minimized if

 $z_{1}\geq z_{2}\geq\cdots\geq z_{n}.$
Title proof of rearrangement inequality ProofOfRearrangementInequality 2013-03-22 13:08:41 2013-03-22 13:08:41 pbruin (1001) pbruin (1001) 4 pbruin (1001) Proof msc 26D15 ChebyshevsInequality