Rearrangement Inequality

Two sequences that are both increasing or both decreasing are said to be similarly ordered. If one is increasing and the other is decreasing they are said to be inversely (or, oppositely) ordered. Given two sequences $x_i,$ $y_i,$ $i = 1, 2, \ldots, n,$ when it comes to evaluating $\displaystyle\sum_{i=1}^{n}x_iy_i,$ we can always assume that one of the sequences is monotone, say monotone increasing, whereas the other could be looked at as a permutation of a decreasing sequence $u_i,$ $i = 1, 2, \ldots, n,$ or a permutation of an increasing sequence $v_i,$ $i = 1, 2, \ldots, n.$ It is then possible to estimate

$\displaystyle\sum_{i=1}^{n}x_iu_i\le\sum_{i=1}^{n}x_iy_i\le\sum_{i=1}^{n}x_iv_i.$

First, we prove $\displaystyle\sum_{i=1}^{n}x_iy_i\le\sum_{i=1}^{n}x_iv_i.$ (To remind, we assume that $\{x_i\}$ and $\{v_i\}$ are both monotone increasing, with the latter being just a reodered sequence $\{y_i\}).$ The proof is by mathematical induction. The case $n = 1$ is vacuously true. The case $n=2$ follows from $(x_2-x_1)(y_1-y_2)\le 0$ which is equivalent to $x_1y_2+x_2y_1\le x_1y_1+x_2y_2.$

Suppose the case $n = k$ is true. Then for the case $n = k + 1,$ there are two possibilities: either $y_{k+1}=v_{k+1},$ i.e., $y_{k+1}$ is the largest element in the sequence, or $y_{k+1}\lt v_{k+1}.$ In the former case, there is nothing to prove because, the permutation $\sigma$ leaves $y_{k+1}$ fixed such that the passage from the case $n=k$ to the case $n=k+1$ consists in adding $x_{k+1}y_{k+1}$ to both sides of the inequality, true by the inductive hypothesis.

If $y_{k+1}\lt v_{k+1}$ then let $y_{k+1}=v_s.$ The sum $\displaystyle\sum_{i=1}^{k+1}x_iy_i$ contains two terms: for some $t,$ $x_tv_{k+1}+x_{k+1}v_s$ which may be compared to $x_tv_s+x_{k+1}v_{k+1}.$ As in the case of $n=2,$ we have $(x_{k+1}-x_t)(v_s-v_{k+1})\le 0,$ implying $x_tv_{k+1}+x_{k+1}v_s \le x_tv_s+x_{k+1}v_{k+1}.$ Let $\{y'_i\}$ be the sequence $\{y_i\},$ with $v_{k+1}$ and $v_s,$ swapped. We then get

$\displaystyle\sum_{i=1}^{k+1}x_iy_i\le\sum_{i=1}^{k}x_iy'_i+x_{k+1}v_{k+1}\le\sum_{i=1}^{k}x_iv_i+x_{k+1}v_{k+1}=\sum_{i=1}^{k+1}x_iv_i.$

The left inequality $\displaystyle\sum_{i=1}^{n}x_iu_i\le\sum_{i=1}^{n}x_iy_i$ is actually equivalent to the right one: the proof of one is obtained from the proof of the other by changing signs of all the terms in sequence $\{y_i\}.$

Let's derive the AM-GM inequality by rearrangement. We want to show that,for positive $\{a_i\},$

$\displaystyle\frac{1}{n}(a_1+a_2+\ldots+a_n)\ge\sqrt[n]{a_1\cdot a_2\cdot\ldots\cdot a_n}.$

Define $c=\sqrt[n]{a_1\cdot a_2\cdot\ldots\cdot a_n};$ $\displaystyle x_1=\frac{a_1}{c},$ $\displaystyle x_2=\frac{a_1a_2}{c^2},$ $\displaystyle x_3=\frac{a_1a_2a_3}{c^3},\ldots$ and $\displaystyle u_i=\frac{1}{x_i}.$ Note that $\displaystyle x_n=\frac{a_1\cdot\ldots\cdot a_n}{c^n}=1$ and so too $\displaystyle u_n=\frac{1}{x_n}=1.$ The sequences $\{x_i\}$ and $\{u_i\}$ are oppositely ordered, therefore,

$x_1u_1+x_2u_2+\ldots+x_nu_n\le x_1u_n+x_2u_{n-1}+\ldots+x_nu_1.$

In other words,

$\displaystyle n=1+1+\ldots+1\le \frac{x_1}{c}+\frac{x_2}{c}+\ldots+\frac{x_n}{c}.$

which is exactly the AM-GM inequality.

Note that the sequences $\{a_i\}$ and $\displaystyle\{\frac{a_i}{s-a_i}\}$ are similarly ordered, so that, for all $k=2,3,\ldots,n,$

$\displaystyle\begin{align} \frac{a_1}{s-a_1}+\frac{a_2}{s-a_2}&+\ldots+\frac{a_n}{s-a_n}\\ &\ge\frac{a_1}{s-a_k}+\frac{a_2}{s-a_{k+1}}+\ldots+\frac{a_n}{s-a_{k-1}}. \end{align}$

Adding up all $n-1$ inequalities gives the desired result.

Note

For $n=3,$ the inequality $\displaystyle\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\ge\frac{3}{2}$ is known as Nesbitt's inequality.

1. Kin-Yin Li, Rearrangement Inequality, Mathematical Excalibur, Volume 4, Number 3, January, 1999 - March, 1999
2. Yue Kwok Choy, Rearrangement Inequality
3. Samin Riasat, Basics of Olympiad Inequalities
4. IMOMath, Rearrangement Inequality. Chebyshev’s Inequality
5. G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press (2^nd edition)
6. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998 1988.
7. Xu Jiagu, Lecture Notes on Mathematical Olympiad Courses, v 8, (For senior section, v 2), World Scientific, 2012
8. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999