In mathematics, the rearrangement inequality [1] states that for every choice of real numbers
. | (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:
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.
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
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.
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.
The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to
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
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.
As above, it suffices to treat the upper bound in ( 1). For a proof by mathematical induction, we start with Observe 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:
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. 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 and every choice of continuously differentiable functions for such that their derivatives satisfy
In mathematics, the rearrangement inequality [1] states that for every choice of real numbers
. | (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:
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.
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
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.
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.
The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to
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
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.
As above, it suffices to treat the upper bound in ( 1). For a proof by mathematical induction, we start with Observe 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:
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. 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 and every choice of continuously differentiable functions for such that their derivatives satisfy