Rearrangement inequality

Many important inequalities can be proved by the rearrangement inequality, such as the arithmetic mean – geometric mean inequality, the Cauchy–Schwarz inequality, and Chebyshev's sum inequality.

Here is a particular consequence for all real numbers ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$: By applying (1) with ${\displaystyle y_{i}:=x_{i}}$ for all ${\displaystyle i=1,\ldots ,n,}$ it follows that

$${\displaystyle x_{1}x_{n}+\cdots +x_{n}x_{1}\leq x_{1}x_{\sigma (1)}+\cdots +x_{n}x_{\sigma (n)}\leq x_{1}^{2}+\cdots +x_{n}^{2}}$$

for every permutation ${\displaystyle \sigma }$ of ${\displaystyle 1,\ldots ,n.}$

The rearrangement inequality is actually very intuitive. Imagine there is a heap of $10 bills, a heap of $20 bills and one more heap of $100 bills. You are allowed to take 7 bills from a heap of your choice and then the heap disappears. In the second round you are allowed to take 5 bills from another heap and the heap disappears. In the last round you may take 3 bills from the last heap. In what order do you want to choose the heaps to maximize your profit? Obviously, the best you can do is to gain ${\displaystyle 7\cdot 100+5\cdot 20+3\cdot 10}$ dollars. This is exactly what the upper bound of the rearrangement inequality (1) says for the sequences ${\displaystyle 3<5<7}$ and ${\displaystyle 10<20<100.}$ It is also an application of a greedy algorithm.

Assume that ${\displaystyle 0<x_{1}<\cdots <x_{n}}$ and ${\displaystyle 0<y_{1}<\cdots <y_{n}.}$ Consider a rectangle of width ${\displaystyle x_{1}+\cdots +x_{n}}$ and height ${\displaystyle y_{1}+\cdots +y_{n},}$ subdivided into ${\displaystyle n}$ columns of widths ${\displaystyle x_{1},\ldots ,x_{n}}$ and the same number of rows of heights ${\displaystyle y_{1},\ldots ,y_{n},}$ so there are ${\displaystyle \textstyle n^{2}}$ small rectangles. You are supposed to take ${\displaystyle n}$ of these, one from each column and one from each row. The rearrangement inequality (1) says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.

The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to

$${\displaystyle -y_{n}\leq \cdots \leq -y_{1}.}$$

Therefore, it suffices to prove the upper bound in (1) and discuss when equality holds. Since there are only finitely many permutations of ${\displaystyle 1,\ldots ,n,}$ there exists at least one ${\displaystyle \sigma }$ for which the middle term in (1)

$${\displaystyle x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}}$$

is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers ${\displaystyle i}$ from ${\displaystyle \{1,\ldots ,n\}}$ satisfying ${\displaystyle y_{i}=y_{\sigma (i)}.}$

We will now prove by contradiction, that ${\displaystyle \sigma }$ has to keep the order of ${\displaystyle y_{1},\ldots ,y_{n}}$ (then we are done with the upper bound in (1), because the identity has that property). Assume that there exists a ${\displaystyle j\in \{1,\ldots ,n-1\}}$ such that ${\displaystyle y_{i}=y_{\sigma (i)}}$ for all ${\displaystyle i\in \{1,\ldots ,j-1\}}$ and ${\displaystyle y_{j}\neq y_{\sigma (j)}.}$ Hence ${\displaystyle y_{j}<y_{\sigma (j)}}$ and there has to exist a ${\displaystyle k\in \{j+1,\ldots ,n\}}$ with ${\displaystyle y_{j}=y_{\sigma (k)}}$ to fill the gap. Therefore,

${\displaystyle x_{j}\leq x_{k}\qquad {\text{and}}\qquad y_{\sigma (k)}<y_{\sigma (j)},}$

(2)

which implies that

${\displaystyle 0\leq (x_{k}-x_{j})(y_{\sigma (j)}-y_{\sigma (k)}).}$

(3)

Expanding this product and rearranging gives

${\displaystyle x_{j}y_{\sigma (j)}+x_{k}y_{\sigma (k)}\leq x_{j}y_{\sigma (k)}+x_{k}y_{\sigma (j)}\,,}$

(4)

which is equivalent to (3). Hence the permutation

$${\displaystyle \tau (i):={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,k\},\\\sigma (k)&{\text{for }}i=j,\\\sigma (j)&{\text{for }}i=k,\end{cases}}}$$

which arises from ${\displaystyle \sigma }$ by exchanging the values ${\displaystyle \sigma (j)}$ and ${\displaystyle \sigma (k),}$ has at least one additional point which keeps the order compared to ${\displaystyle \sigma ,}$ namely at ${\displaystyle j}$ satisfying ${\displaystyle y_{j}=y_{\tau (j)},}$ and also attains the maximum in (1) due to (4). This contradicts the choice of ${\displaystyle \sigma .}$

If ${\displaystyle x_{1}<\cdots <x_{n},}$ then we have strict inequalities in (2), (3), and (4), hence the maximum can only be attained by permutations keeping the order of ${\displaystyle y_{1}\leq \cdots \leq y_{n},}$ and every other permutation ${\displaystyle \sigma }$ cannot be optimal.

As above, if suffices to treat the upper bound in (1). For a proof by mathematical induction, we start with ${\displaystyle n=2.}$ Observe that

$${\displaystyle x_{1}\leq x_{2}\quad {\text{ and }}\quad y_{1}\leq y_{2}}$$

implies that

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

(5)

which is equivalent to

${\displaystyle x_{1}y_{2}+x_{2}y_{1}\leq x_{1}y_{1}+x_{2}y_{2},}$

(6)

hence the upper bound in (1) is true for ${\displaystyle n=2.}$ If ${\displaystyle x_{1}<x_{2},}$ then we get strict inequality in (5) and (6) if and only if ${\displaystyle y_{1}<y_{2}.}$ Hence only the identity, which is the only permutation here keeping the order of ${\displaystyle y_{1}<y_{2},}$ gives the maximum.

As induction hypothesis assume that the upper bound in the rearrangement inequality (1) is true for ${\displaystyle n-1}$ with ${\displaystyle n\geq 3}$ and that in the case ${\displaystyle x_{1}<\cdots <x_{n-1}}$ there is equality only when the permutation ${\displaystyle \sigma }$ of ${\displaystyle 1,\ldots ,n-1}$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n-1}.}$

Consider now ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$ and ${\displaystyle y_{1}\leq \cdots \leq y_{n}.}$ Take a ${\displaystyle \sigma }$ from the finite number of permutations of ${\displaystyle 1,\ldots ,n}$ such that the rearrangement in the middle of (1) gives the maximal result. There are two cases:

• If ${\displaystyle \sigma (n)=n,}$ then ${\displaystyle y_{n}=y_{\sigma (n)}}$ and, using the induction hypothesis, the upper bound in (1) is true with equality and ${\displaystyle \sigma }$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n-1},y_{n}}$ in the case ${\displaystyle x_{1}<\cdots <x_{n}.}$
• If ${\displaystyle k:=\sigma (n)<n,}$ then there is a ${\displaystyle j\in \{1,\dots ,n-1\}}$ with ${\displaystyle \sigma (j)=n.}$ Define the permutation
  $${\displaystyle \tau (i)={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,n\},\\k&{\text{for }}i=j,\\n&{\text{for }}i=n,\end{cases}}}$$

  
  which arises from ${\displaystyle \sigma }$ by exchanging the values of ${\displaystyle j}$ and ${\displaystyle n.}$ There are now to subcases:

1. If ${\displaystyle x_{k}=x_{n}}$ or ${\displaystyle y_{k}=y_{n},}$ then this exchange of values of ${\displaystyle \sigma }$ has no effect on the middle term in (1) because ${\displaystyle \tau }$ gives the same sum, and we can proceed by applying the first case to ${\displaystyle \tau .}$ Note that in the case ${\displaystyle x_{1}<\cdots <x_{n},}$ the permutation ${\displaystyle \tau }$ keeps the order of ${\displaystyle y_{1},\ldots ,y_{n}}$ if and only if ${\displaystyle \sigma }$ does.
2. If ${\displaystyle x_{k}<x_{n}}$ and ${\displaystyle y_{k}<y_{n},}$ then ${\displaystyle 0<(x_{n}-x_{k})(y_{n}-y_{k}),}$ which is equivalent to ${\displaystyle x_{k}y_{n}+x_{n}y_{k}<x_{k}y_{k}+x_{n}y_{n}}$ and shows that ${\displaystyle \sigma }$ is not optimal, hence this case cannot happen due to the choice of ${\displaystyle \sigma .}$

• Hardy–Littlewood inequality
• Chebyshev's sum inequality