Rearrangement inequality explained
of the numbers
we haveInformally, this means that in these types of sums, the largest sum is achieved by pairing large
values with large
values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the
are distinct, meaning that
then:
- The upper bound in is attained only for permutations
that keep the order of
that is,
or equivalently
(y1,\ldots,yn)=(y\sigma(1),\ldots,y\sigma(n)).
Such a
can permute the indices of
-values that are equal; in the case
every permutation keeps the order of
If
then the only such
is the identiy.
- Correspondingly, the lower bound in is attained only for permutations
that reverse the order of
meaning that
If
then
for all
is the only permutation to do this.Note that the rearrangement inequality makes no assumptions on the signs of the real numbers, unlike inequalities such as the
arithmetic-geometric mean inequality.
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.
As a simple example, consider real numbers
: By applying with
for all
it follows that
for every permutation
of
Intuition
The rearrangement inequality can be regarded as intuitive in the following way. 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
dollars. This is exactly what the upper bound of the rearrangement inequality says for the sequences
and
In this sense, it can be considered as an example of a
greedy algorithm.
Geometric interpretation
Assume that
and
Consider a rectangle of width
and height
subdivided into
columns of widths
and the same number of rows of heights
so there are
small rectangles. You are supposed to take
of these, one from each column and one from each row. The rearrangement inequality says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.
Proofs
Proof by contradiction
The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound toTherefore, it suffices to prove the upper bound in and discuss when equality holds. Since there are only finitely many permutations of
there exists at least one
for which the middle term in
is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers
from
satisfying
We will now prove by contradiction, that
has to keep the order of
(then we are done with the upper bound in, because the identity has that property). Assume that there exists a
such that
for all
and
Hence
and there has to exist a
with
to fill the gap. Therefore,which implies thatExpanding this product and rearranging giveswhich is equivalent to . Hence the permutation
which arises from
by exchanging the values
and
has at least one additional point which keeps the order compared to
namely at
satisfying
and also attains the maximum in due to . This contradicts the choice of
If
then we have strict inequalities in,, and, hence the maximum can only be attained by permutations keeping the order of
and every other permutation
cannot be optimal.
Proof by induction
As above, it suffices to treat the upper bound in . For a proof by mathematical induction, we start with
Observe that
implies thatwhich is equivalent tohence the upper bound in is true for
If
then we get strict inequality in and if and only if
Hence only the identity, which is the only permutation here keeping the order of
gives the maximum.
As an induction hypothesis assume that the upper bound in the rearrangement inequality is true for
with
and that in the case
there is equality only when the permutation
of
keeps the order of
Consider now
and
Take a
from the finite number of permutations of
such that the rearrangement in the middle of gives the maximal result. There are two cases:
then
and, using the induction hypothesis, the upper bound in is true with equality and
keeps the order of
in the case
then there is a
with
Define the permutation
which arises from
by exchanging the values of
and
There are now two subcases:
- If
or
then this exchange of values of
has no effect on the middle term in because
gives the same sum, and we can proceed by applying the first case to
Note that in the case
the permutation
keeps the order of
if and only if
does.
- If
and
then
which is equivalent to
and shows that
is not optimal, hence this case cannot happen due to the choice of
Generalizations
Three or more sequences
A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbersand a permutation
y\sigma(1),\ldots,y\sigma(n)
of
and another permutation
of
Then
Note that, unlike the standard rearrangement inequality, this statement requires the numbers to be nonnegative. A similar statement is true for any number of sequences with all numbers nonnegative.
Functions instead of factors
Another generalization of the rearrangement inequality states that for all real numbers
and every choice of continuously
differentiable functions
for
such that their derivatives
satisfy
the inequality
holds for every
permutation f\sigma(1),\ldots,f\sigma(n)
of
Taking real numbers
and the linear functions
for real
and
the standard rearrangement inequality is recovered.
See also
Notes and References
- , Section 10.2, Theorem 368