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 maximalunless $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 consecutivelyinterchange these pairs until $z_1\le z_2\le \mathrm{\cdots }\le z_n$ (this ispossible because the number of pairs with $z_i>z_j$ decreaseswith 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 apermutation $(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.$$