# Rearrangement Inequality

The **rearrangement inequality** is a statement about the pairwise products of two sequences. It can be extended to Chebyshev's inequality, and illustrates the practical power of greedy algorithms.

## Definition

The rearrangement inequality states that, for two sequences $a_1 \geq a_2 \geq \ldots \geq a_n$ and $b_1 \geq b_2 \geq \ldots \geq b_n$, the inequalities

$a_1b_1+a_2b_2+\cdots+a_nb_n \geq a_1b_{\pi(1)}+a_2b_{\pi(2)}+\cdots+a_nb_{\pi(n)} \geq a_1b_n+a_2b_{n-1}+\cdots+a_nb_1$

hold, where $\pi(1), \pi(2), \ldots, \pi(n)$ is any permutation of $1, 2, \ldots, n$.

## Proof

Consider a permutation $\pi(1), \pi(2), \ldots, \pi(n)$ such that $a_1b_{\pi(1)}+a_2b_{\pi(2)}+\cdots+a_nb_{\pi(n)}$ is maximized. The desired result is that $\pi$ is the identity permutation: i.e. $\pi(i)=i$ for all $i$. Suppose for the sake of contradiction that $\pi$ is **not** the identity, and let $i$ be the smallest integer such that $\pi(i) \neq i$.

Since $i$ is the smallest such integer, this means that $\pi(i)=j>i$ (as the numbers $1$ to $i-1$ are already assigned). Furthermore, there must exist a $k>i$ such that $\pi(k)=i$, as some number must be assigned to $i$.

Now, since $i<j$, it follows that $b_i \leq b_j$. Similarly, since $i<k$, it follows that $a_i \leq a_k$. Therefore,

$0 \leq (a_k-a_i)(b_j-b_i) \implies a_ib_j+a_kb_i \leq a_kb_j+a_ib_i,$

so the sum $a_1b_{\pi(1)}+\cdots+a_nb_{\pi(n)}$ is not decreased by changing $\pi(i)=j, \pi(k)=i$ to $\pi(i)=i, \pi(k)=j$. This implies that the identity permutation gives the maximum possible value of $a_1b_{\pi(1)}+a_2b_{\pi(2)}+\cdots+a_nb_{\pi(n)}$, as desired.

## Strategies and Applications

The value of the rearrangement inequality lies chiefly in the fact that it formalizes one's intuition towards what amounts to a greedy algorithm. For instance, if one were presented with a large number of $20 bills, $10 bills, $5 bills, and $1 bills, with the instructions to take 4 of one type of bill, 3 of another, 2 of another, and 1 of the last, it is intuitively obvious that four $20 bills, three $10 bills, two $5 bills, and one $1 bill should be selected. Indeed, this is precisely the statement of the rearrangement inequality, applied to the sequences $20, 10, 5, 1$ and $4, 3, 2, 1$.

Like the Chebyshev inequality, care must be taken to assure both sequences are similarly ordered. Common strategies include

- $a \geq b \geq c \implies a+b \geq a+c \geq b+c$
- $a \geq b \geq c \implies \frac{1}{a} \leq \frac{1}{b} \leq \frac{1}{c}$.

Cycling the variables is also a powerful technique, as this preserves some ordering. For instance,

Show that

$a^2+b^2+c^2 \geq ab+bc+ca$

for reals $a,b,c$.

Assume without loss of generality that $a \geq b \geq c$. By rearrangement,

$a \cdot a+b \cdot b+c \cdot c \geq a \cdot b+b \cdot c+c \cdot a,$

which is precisely the desired inequality. $_\square$

A similar strategy leads to another proof of the AM-GM inequality:

Show that

$a^4+b^4+c^4+d^4 \geq 4abcd$

for positive reals $a,b,c,d$.

Assume without loss of generality that $a \leq b \leq c \leq d$. The rearrangement inequality tells us that

$\begin{aligned} d \cdot d^3+c \cdot c^3 \geq d \cdot c^3+c \cdot d^3 &\implies d^4+c^4 \geq dc^3+cd^3\\\\ d \cdot cd^2+b \cdot b^3 \geq d \cdot b^3+b \cdot cd^2 &\implies cd^3+b^4 \geq db^3+bcd^2, \end{aligned}$

which implies that

$d^4+c^4+b^4 \geq dc^3+db^3+bcd^2.$

Additionally, the rearrangement inequality tells us that

$d \cdot bcd+a \cdot a^3 \geq d \cdot a^3+a \cdot bcd \implies bcd^2+a^4 \geq da^3+abcd,$

which implies that

$d^4+c^4+b^4+a^4 \geq dc^3+db^3+da^3+abcd,$

so it suffices to show that $dc^3+db^3+da^3 \geq 3abcd$, or $a^3+b^3+c^3 \geq 3abc$. This argument is then repeated until it is left to prove that $a \geq a$, which is self-evident. $_\square$

## See Also

**Cite as:**Rearrangement Inequality.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/rearrangement-inequality/