Rearrangement inequality

In mathematics, the rearrangement inequality[1] states that for every choice of real numbers

and every permutation of the numbers we have
.

 

 

 

 

(1)

Informally, 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:

  1. The upper bound in (1) is attained only for permutations that keep the order of that is,
    or equivalently 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.
  2. Correspondingly, the lower bound in (1) 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 (1) makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.

Applications edit

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 (1) with   for all   it follows that

 
for every permutation   of  

Intuition edit

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 (1) says for the sequences   and   In this sense, it can be considered as an example of a greedy algorithm.

Geometric interpretation edit

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 (1) says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.

Proofs edit

Proof by contradiction edit

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. Since there are only finitely many permutations of   there exists at least one   for which the middle term in (1)
 
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 (1), 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,

 

 

 

 

 

(2)

which implies that

 

 

 

 

 

(3)

Expanding this product and rearranging gives

 

 

 

 

 

(4)

which is equivalent to (3). 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 (1) due to (4). This contradicts the choice of  

If   then we have strict inequalities in (2), (3), and (4), hence the maximum can only be attained by permutations keeping the order of   and every other permutation   cannot be optimal.

Proof by induction edit

As above, if suffices to treat the upper bound in (1). For a proof by mathematical induction, we start with   Observe that

 
implies that
 

 

 

 

 

(5)

which is equivalent to

 

 

 

 

 

(6)

hence the upper bound in (1) is true for   If   then we get strict inequality in (5) and (6) 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 (1) 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 (1) gives the maximal result. There are two cases:

  • If   then   and, using the induction hypothesis, the upper bound in (1) is true with equality and   keeps the order of   in the case  
  • If   then there is a   with   Define the permutation
     
    which arises from   by exchanging the values of   and   There are now two subcases:
  1. If   or   then this exchange of values of   has no effect on the middle term in (1) 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.
  2. If   and   then   which is equivalent to   and shows that   is not optimal, hence this case cannot happen due to the choice of  

Generalizations edit

Three or more sequences edit

A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbers

 
and a permutation   of   and another permutation   of   Then
 

Note that, unlike the standard rearrangement inequality (1), 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 edit

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   of  [2] Taking real numbers   and the linear functions   for real   and   the standard rearrangement inequality (1) is recovered.

See also edit

References edit

  1. ^ Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8, MR 0046395, Zbl 0047.05302, Section 10.2, Theorem 368
  2. ^ Holstermann, Jan (2017), "A Generalization of the Rearrangement Inequality" (PDF), Mathematical Reflections, no. 5 (2017)