In mathematics, the rearrangement inequality[1] states that for every choice of real numbers
we have Informally, this means that in these types of sums, the largest sum is achieved by pairing large
then: Note that the rearrangement inequality (1) makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.
As a simple example, consider real numbers
The rearrangement inequality can be regarded as intuitive in the following way.
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?
This is exactly what the upper bound of the rearrangement inequality (1) says for the sequences
In this sense, it can be considered as an example of a greedy algorithm.
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
Therefore, it suffices to prove the upper bound in (1) and discuss when equality holds.
In case there are several permutations with this property, let σ denote one with the highest number of integers
(then we are done with the upper bound in (1), because the identity has that property).
Therefore, which implies that Expanding this product and rearranging gives which is equivalent to (3).
has at least one additional point which keeps the order compared to
then we have strict inequalities in (2), (3), and (4), hence the maximum can only be attained by permutations keeping the order of
As above, it suffices to treat the upper bound in (1).
For a proof by mathematical induction, we start with
implies that which is equivalent to hence the upper bound in (1) is true for
Hence only the identity, which is the only permutation here keeping the order of
As an induction hypothesis assume that the upper bound in the rearrangement inequality (1) is true for
such that the rearrangement in the middle of (1) gives the maximal result.
There are two cases: A straightforward generalization takes into account more sequences.
Assume we have finite ordered sequences of nonnegative real numbers
Note that, unlike the standard rearrangement inequality (1), this statement requires the numbers to be nonnegative.
Another generalization of the rearrangement inequality states that for all real numbers
and every choice of continuously differentiable functions
[2] Taking real numbers
the standard rearrangement inequality (1) is recovered.