Rearrangement Inequality

In mathematics, the rearrangement inequality states that
$x_n y_1 + \cdots + x_1 y_n \leq x_ y_1 + \cdots + x_ y_n \leq x_1 y_1 + \cdots + x_n y_n$
for every choice of real numbers
$x_1 \leq \cdots \leq x_n \quad \text \quad y_1 \leq \cdots \leq y_n$
and every permutation
$x_, \ldots, x_$
of $x_1, \ldots, x_n.$
If the numbers are different, meaning that
$x_1 < \cdots < x_n \quad \text \quad y_1 < \cdots < y_n,$

then the lower bound is attained only for the permutation which reverses the order, that is, $\sigma(i) = n - i + 1$ for all $i = 1, \ldots, n,$ and the upper bound is attained only for the identity, that is, $\sigma(i) = i$ for all $i = 1, \ldots, n.$

Note that the rearrangement inequality makes no assumptions on the signs of the real numbers.

Applications

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.

One particular consequence is that if $x_1 \leq \cdots \leq x_n$ then (by using $y_i := x_i \text i$): $x_1 x_n + \cdots + x_n x_1 \; \leq \; x_1 x_ + \cdots + x_n x_ \; \leq \; x_1^2 + \cdots + x_n^2$ holds for every permutation $\sigma$ of $1, \ldots, n.$

Intuition

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 $7\cdot100 + 5\cdot20 + 3\cdot10$ dollars. This is exactly what rearrangement inequality says for sequences $10 < 20 < 100$ and $3 < 5 < 7.$ It is also an application of a greedy algorithm.

Proof

The lower bound follows by applying the upper bound to
$- x_n \leq \cdots \leq - x_1.$

Therefore, it suffices to prove the upper bound. Since there are only finitely many permutations, there exists at least one for which
$x_ y_1 + \cdots + x_ y_n$
is maximal. In case there are several permutations with this property, let σ denote one with the highest number of fixed points.

We will now prove by contradiction, that σ has to be the identity (then we are done). Assume that σ is the identity. Then there exists a ''j'' in such that σ(''j'') ≠ ''j'' and σ(''i'') = ''i'' for all ''i'' in . Hence σ(''j'') > ''j'' and there exists a ''k'' in with σ(''k'') = ''j''. Now
$j < k \Rightarrow y_j \leq y_k \qquad\text\qquad j < \sigma(j)\Rightarrow x_j \leq x_.\quad(1)$

Therefore,
$0 \leq \left(x_ - x_j\right)\left(y_k - y_j\right). \quad(2)$

Expanding this product and rearranging gives
$x_ y_j + x_j y_k \leq x_j y_j + x_ y_k\,, \quad(3)$

hence the permutation
$\tau(i):=\begini&\texti \in \,\\ \sigma(j)&\texti = k,\\ \sigma(i)&\texti \in\ \setminus \,\end$

which arises from σ by exchanging the values σ(''j'') and σ(''k''), has at least one additional fixed point compared to σ, namely at ''j'', and also attains the maximum. This contradicts the choice of σ.

If
$x_1 < \cdots < x_n \quad \text \quad y_1 < \cdots < y_n,$
then we have strict inequalities at (1), (2), and (3), hence the maximum can only be attained by the identity, any other permutation σ cannot be optimal.

Proof by induction

Observe first that
$x_1 > x_2 \quad \text \quad y_1 > y_2$
implies
$\left(x_1 - x_2\right) \left(y_1 - y_2\right) > 0 \quad \text \quad x_1 y_1 + x_2 y_2 > x_2 y_1 + x_1 y_2,$
hence the result is true if ''n'' = 2.
Assume it is true at rank ''n-1'', and let
$x_1 > \cdots > x_n, \quad \text \quad y_1 > \cdots > y_n.$
Choose a permutation σ for which the arrangement gives rise a maximal result.

If σ(''n'') were different from ''n'', say σ(''n'') = ''k'',
there would exist ''j'' < ''n'' such that σ(''j'') = ''n''.
But
$x_k > x_n \quad\text\quad y_j > y_n, \quad\text\quad x_ny_n + x_ky_j > x_ky_n + x_ny_j$
by what has just been proved.
Consequently, it would follow that the permutation τ coinciding with σ, except at ''j'' and ''n'', where
τ(''j'') = ''k'' and τ(''n'') = ''n'', gives rise a better result. This contradicts the choice of σ.
Hence σ(''n'') = ''n'', and from the induction hypothesis, σ(''i'') = ''i'' for every ''i'' < ''n''.

The same proof holds if one replace strict inequalities by non strict ones.

Generalizations

A straightforward generalization takes into account more sequences. Assume we have ordered sequences of positive real numbers
$x_n\geq\cdots\geq x_1\geq0\quad\text\quad y_n\geq\cdots\geq y_1\geq0\quad\text\quad z_n\geq\cdots\geq z_1\geq0$
and a permutation $x_,\dots,x_$ of $x_1,\dots,x_n$ and another permutation $y_,\dots,y_$ of $y_1,\dots,y_n$. Then it holds
$x_n y_n z_n + \ldots + x_1 y_1 z_1\geq x_ y_ z_n + \ldots + x_ y_ z_1.$

Note that unlike the common rearrangement inequality this statement requires the numbers to be nonnegative. A similar statement is true for any number of sequences with all numbers nonnegative.

Another generalization of the rearrangement inequality states that for all real numbers $x_1 \leq \cdots \leq x_n$ and any choice of functions f_i: _1,x_n\rightarrow \R, i = 1, 2, \ldots, n such that the derivatives $f'_i$ satisfy:
f'_1(x) \leq f'_2(x) \leq \cdots \leq f'_n(x) \quad \text x \in _1,x_n/math>
the inequality
$\sum_^n f_i(x_) \leq \sum_^n f_i(x_) \leq \sum_^n f_i(x_i)$
holds for every permutation $x_, \ldots, x_$ of $x_1, \ldots, x_n.$

See also

* Hardy–Littlewood inequality
* Chebyshev's sum inequality

References

{{reflist

Inequalities
Articles containing proofs