Rearrangement inequality
Template:Short description In mathematics, the rearrangement inequality<ref>Template:Citation, Section 10.2, Theorem 368</ref> states that for every choice of real numbers <math display=block>x_1 \le \cdots \le x_n \quad \text{ and } \quad y_1 \le \cdots \le y_n</math> and every permutation <math>\sigma</math> of the numbers <math>1, 2, \ldots n</math> we have Template:NumBlk Informally, this means that in these types of sums, the largest sum is achieved by pairing large <math>x</math> values with large <math>y</math> values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the <math>x_1, \ldots, x_n</math> are distinct, meaning that <math>x_1 < \cdots < x_n,</math> then:
- The upper bound in (Template:EquationNote) is attained only for permutations <math>\sigma</math> that keep the order of <math>y_1, \ldots, y_n,</math> that is, <math display=block>y_{\sigma(1)} \le \cdots \le y_{\sigma(n)},</math> or equivalently <math>(y_1,\ldots,y_n) = (y_{\sigma(1)},\ldots,y_{\sigma(n)}).</math> Such a <math>\sigma</math> can permute the indices of <math>y</math>-values that are equal; in the case <math>y_1 = \cdots = y_n</math> every permutation keeps the order of <math>y_1, \ldots, y_n.</math> If <math>y_1 < \cdots < y_n,</math> then the only such <math>\sigma</math> is the identity.
- Correspondingly, the lower bound in (Template:EquationNote) is attained only for permutations <math>\sigma</math> that reverse the order of <math>y_1, \ldots, y_n,</math> meaning that <math display=block>y_{\sigma(1)} \ge \cdots \ge y_{\sigma(n)}.</math> If <math>y_1 < \cdots < y_n,</math> then <math>\sigma(i) = n - i + 1</math> for all <math>i = 1, \ldots, n,</math> is the only permutation to do this.
Note that the rearrangement inequality (Template:EquationNote) makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.
<templatestyles src="Template:TOC_right/styles.css" />{{#if:|<templatestyles src="Template:TOC limit/styles.css" />}}
ApplicationsEdit
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 <math>x_1 \le \cdots \le x_n</math>: By applying (Template:EquationNote) with <math>y_i := x_i</math> for all <math>i = 1,\ldots,n,</math> it follows that <math display=block>x_1 x_n + \cdots + x_n x_1 \le x_1 x_{\sigma(1)} + \cdots + x_n x_{\sigma(n)} \le x_1^2 + \cdots + x_n^2</math> for every permutation <math>\sigma</math> of <math>1, \ldots, n.</math>
IntuitionEdit
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 <math>7\cdot100 + 5\cdot20 + 3\cdot10</math> dollars. This is exactly what the upper bound of the rearrangement inequality (Template:EquationNote) says for the sequences <math>3 < 5 < 7</math> and <math>10 < 20 < 100.</math> In this sense, it can be considered as an example of a greedy algorithm.
Geometric interpretationEdit
Assume that <math>0 < x_1 < \cdots < x_n</math> and <math> 0< y_1 < \cdots < y_n.</math> Consider a rectangle of width <math>x_1 + \cdots + x_n</math> and height <math>y_1 + \cdots + y_n,</math> subdivided into <math>n</math> columns of widths <math>x_1,\ldots,x_n</math> and the same number of rows of heights <math>y_1,\ldots,y_n,</math> so there are <math>\textstyle n^2</math> small rectangles. You are supposed to take <math>n</math> of these, one from each column and one from each row. The rearrangement inequality (Template:EquationNote) says that you optimize the total area of your selection by taking the rectangles on the diagonal or the antidiagonal.
ProofsEdit
Proof by contradictionEdit
The lower bound and the corresponding discussion of equality follow by applying the results for the upper bound to <math display="inline">- y_n \le \cdots \le - y_1</math>, that is, let <math>\upsilon</math> be any permutation of the numbers <math display="inline">1, 2, \ldots n</math> we have <math display="inline">x_1 (-y_{\upsilon(1)})+\cdots +x_n (-y_{\upsilon (n)})\leq x_1 (-y_{n})+\cdots +x_n (-y_{1})</math>. Then, <math display="inline">x_1 y_{n}+\cdots +x_n y_{1}\leq x_1 y_{\upsilon(1)}+\cdots +x_n y_{\upsilon (n)}</math> for every permutation <math>\upsilon</math> of <math>1, \dots ,n</math>.
Therefore, it suffices to prove the upper bound in (Template:EquationNote) and discuss when equality holds. Since there are only finitely many permutations of <math>1,\ldots,n,</math> there exists at least one <math>\sigma</math> for which the middle term in (Template:EquationNote) <math display="block">x_1 y_{\sigma(1)} + \cdots + x_n y_{\sigma(n)}</math> is maximal. In case there are several permutations with this property, let σ denote one with the highest number of integers <math>i</math> from <math>\{1,\ldots,n\}</math> satisfying <math>y_i = y_{\sigma(i)}.</math>
We will now prove by contradiction, that <math>\sigma</math> has to keep the order of <math>y_1,\ldots,y_n</math> (then we are done with the upper bound in (Template:EquationNote), because the identity has that property). Assume that there exists a <math>j\in\{1,\ldots,n-1\}</math> such that <math>y_i = y_{\sigma(i)}</math> for all <math>i\in\{1,\ldots,j-1\}</math> and <math>y_j \neq y_{\sigma(j)}.</math> Hence <math>y_j < y_{\sigma(j)}</math> and there has to exist a <math>k\in\{j+1,\ldots,n\}</math> with <math>y_j = y_{\sigma(k)}</math> to fill the gap. Therefore, Template:NumBlk which implies that Template:NumBlk Expanding this product and rearranging gives Template:NumBlk which is equivalent to (Template:EquationNote). Hence the permutation <math display=block>\tau(i):=\begin{cases}\sigma(i)&\text{for }i \in \{1,\ldots,n\}\setminus\{j,k\},\\ \sigma(k)&\text{for }i = j,\\ \sigma(j)&\text{for }i = k,\end{cases}</math> which arises from <math>\sigma</math> by exchanging the values <math>\sigma(j)</math> and <math>\sigma(k),</math> has at least one additional point which keeps the order compared to <math>\sigma,</math> namely at <math>j</math> satisfying <math>y_j=y_{\tau(j)},</math> and also attains the maximum in (Template:EquationNote) due to (Template:EquationNote). This contradicts the choice of <math>\sigma.</math>
If <math>x_1 < \cdots < x_n,</math> then we have strict inequalities in (Template:EquationNote), (Template:EquationNote), and (Template:EquationNote), hence the maximum can only be attained by permutations keeping the order of <math>y_1 \le \cdots \le y_n,</math> and every other permutation <math>\sigma</math> cannot be optimal.
Proof by inductionEdit
As above, it suffices to treat the upper bound in (Template:EquationNote). For a proof by mathematical induction, we start with <math>n=2.</math> Observe that <math display=block>x_1 \le x_2 \quad \text{ and } \quad y_1 \le y_2</math> implies that Template:NumBlk which is equivalent to Template:NumBlk hence the upper bound in (Template:EquationNote) is true for <math>n = 2.</math> If <math>x_1 < x_2,</math> then we get strict inequality in (Template:EquationNote) and (Template:EquationNote) if and only if <math>y_1 < y_2.</math> Hence only the identity, which is the only permutation here keeping the order of <math>y_1 < y_2,</math> gives the maximum.
As an induction hypothesis assume that the upper bound in the rearrangement inequality (Template:EquationNote) is true for <math>n-1</math> with <math>n\ge3</math> and that in the case <math>x_1 <\cdots <x_{n-1}</math> there is equality only when the permutation <math>\sigma</math> of <math>1,\ldots,n-1</math> keeps the order of <math>y_1,\ldots,y_{n-1}.</math>
Consider now <math>x_1 \le \cdots \le x_n</math> and <math>y_1 \le \cdots \le y_n.</math> Take a <math>\sigma</math> from the finite number of permutations of <math>1,\ldots,n</math> such that the rearrangement in the middle of (Template:EquationNote) gives the maximal result. There are two cases:
- If <math>\sigma(n)=n,</math> then <math>y_n=y_{\sigma(n)}</math> and, using the induction hypothesis, the upper bound in (Template:EquationNote) is true with equality and <math>\sigma</math> keeps the order of <math>y_1,\ldots,y_{n-1},y_n</math> in the case <math>x_1 < \cdots < x_n.</math>
- If <math>k := \sigma(n) < n,</math> then there is a <math>j\in\{1,\dots,n-1\}</math> with <math>\sigma(j)=n.</math> Define the permutation <math display=block>\tau(i)=\begin{cases}\sigma(i)&\text{for }i \in \{1,\ldots,n\}\setminus\{j,n\},\\
k&\text{for }i = j,\\ n&\text{for }i = n,\end{cases}</math> which arises from <math>\sigma</math> by exchanging the values of <math>j</math> and <math>n.</math> There are now two subcases:
- If <math>x_j = x_{\sigma_j} = x_n</math> or <math>y_n = y_{\sigma_n} = y_k,</math> then this exchange of values of <math>\sigma</math> has no effect on the middle term in (Template:EquationNote) because <math>\tau</math> gives the same sum, and we can proceed by applying the first case to <math>\tau.</math> Note that in the case <math>x_1 < \cdots < x_n,</math> the permutation <math>\tau</math> keeps the order of <math>y_1,\ldots,y_n</math> if and only if <math>\sigma</math> does.
- If <math>x_j < x_n</math> and <math>y_k < y_n,</math> then <math>0 < (x_n - x_j) (y_n - y_k),</math> which is equivalent to <math>x_j y_{\sigma_j}+ x_n y_{\sigma_n} < x_j y_{\tau_j} + x_n y_Template:\tau n</math> and shows that <math>\sigma</math> is not optimal, hence this case cannot happen due to the choice of <math>\sigma.</math>
GeneralizationsEdit
Three or more sequencesEdit
A straightforward generalization takes into account more sequences. Assume we have finite ordered sequences of nonnegative real numbers <math display=block>0 \le x_1\le\cdots\le x_n\quad\text{and}\quad 0\le y_1\le\cdots\le y_n\quad\text{and}\quad 0\le z_1\le\cdots\le z_n</math> and a permutation <math>y_{\sigma(1)},\ldots,y_{\sigma(n)}</math> of <math>y_1,\dots,y_n</math> and another permutation <math>z_{\tau(1)},\dots,z_{\tau(n)}</math> of <math>z_1,\dots,z_n.</math> Then <math display=block> x_1 y_{\sigma(1)} z_{\tau(1)} + \cdots + x_n y_{\sigma(n)} z_{\tau(n)} \le x_1 y_1 z_1 + \cdots + x_n y_n z_n.</math>
Note that, unlike the standard rearrangement inequality (Template:EquationNote), 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 factorsEdit
Another generalization of the rearrangement inequality states that for all real numbers <math>x_1 \le \cdots \le x_n</math> and every choice of continuously differentiable functions <math>f_i: [x_1,x_n] \to \R</math> for <math>i = 1, 2, \ldots, n</math> such that their derivatives <math>f'_1,\ldots,f'_n</math> satisfy <math display=block>f'_1(x) \le f'_2(x) \le \cdots \le f'_n(x) \quad \text{ for all } x \in [x_1,x_n],</math> the inequality <math display=block>\sum_{i=1}^n f_{n-i+1}(x_i) \le \sum_{i=1}^n f_{\sigma(i)}(x_i) \le \sum_{i=1}^n f_i(x_i)</math> holds for every permutation <math>f_{\sigma(1)}, \ldots, f_{\sigma(n)}</math> of <math>f_1, \ldots, f_n.</math><ref>Template:Citation</ref> Taking real numbers <math>y_1 \le \cdots \le y_n</math> and the linear functions <math>f_i(x) := x y_i</math> for real <math>x</math> and <math>i = 1,\ldots,n,</math> the standard rearrangement inequality (Template:EquationNote) is recovered.