Rearrangement inequality

From Wikipedia, the free encyclopedia

In mathematics, the rearrangement inequality states that

x_ny_1 + \cdots + x_1y_n \le x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \le x_1y_1 + \cdots + x_ny_n

for every choice of real numbers

x_1\le\cdots\le x_n\quad\text{and}\quad y_1\le\cdots\le y_n

and every permutation

x_{\sigma(1)},\dots,x_{\sigma(n)}

of x1, . . ., xn. If the numbers are different, meaning that

x_1<\cdots<x_n\quad\text{and}\quad y_1<\cdots<y_n,

then the lower bound is attained only for the permutation which reverses the order, i.e. σ(i) = n − i + 1 for all i = 1, ..., n, and the upper bound is attained only for the identity, i.e. σ(i) = i for all i = 1, ..., n.

Note that the rearrangement inequality makes no assumptions on the signs of the real numbers.

Contents

[edit] General rearrangement inequality

For any two sets of real numbers x_1\le\cdots\le x_n and y_1\le\cdots\le y_n,

x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \leq x_{\pi(1)}y_1 + \cdots + x_{\pi(n)}y_n

as soon as the permutation π has smaller number of inversions (i.e., such pair of indices i,j that 1\le i<j\le n and π(i) > π(j)) than the the permutation σ.

Note that the identity permutation (1,2,\dots,n) has zero inversions while the permutation (n,n-1,\dots,1) has the maximum possible number of inversions equal \frac{n(n-1)}{2}, implying the classic rearrangement inequality.

[edit] Applications

Many famous 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.

[edit] Proof

The lower bound follows by applying the upper bound to

-x_n\le\cdots\le-x_1.

Therefore, it suffices to prove the upper bound. Since there are only finitely many permutations, there exists at least one for which

x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n

is maximal. In case there are several permutations with this property, let σ denote one with the highest number of fixed points.

We will now prove by contradiction, that σ has to be the identity (then we are done). Assume that σ is not the identity. Then there exists a j in {1, ..., n − 1} such that σ(j) ≠ j and σ(i) = i for all i in {1, ..., j − 1}. Hence σ(j) > j and there exists k in {j + 1, ..., n} with σ(k) = j. Now

j<k\Rightarrow y_j\le y_k \qquad\text{and}\qquad j=\sigma(k)<\sigma(j)\Rightarrow x_j\le x_{\sigma(j)}.\quad(1)

Therefore,

0\le(x_{\sigma(j)}-x_j)(y_k-y_j). \quad(2)

Expanding this product and rearranging gives

x_{\sigma(j)}y_j+x_jy_k\le x_jy_j+x_{\sigma(j)}y_k\,, \quad(3)

hence the permutation

\tau(i):=\begin{cases}i&\text{for }i\in\{1,\ldots,j\},\\ \sigma(j)&\text{for }i=k,\\ \sigma(i)&\text{for }i\in\{j+1,\ldots,n\}\setminus\{k\},\end{cases}

which arises from σ by exchanging the values σ(j) and σ(k), has at least one additional fixed point compared to σ, namely at j, and also attains the maximum. This contradicts the choice of σ.

If

x_1<\cdots<x_n\quad\text{and}\quad y_1<\cdots<y_n,

then we have strict inequalities at (1), (2), and (3), hence the maximum can only be attained by the identity, any other permutation σ cannot be optimal.

[edit] References

  • Alan Wayne (1946). "Inequalities and inversions of order". Scripta Mathematica 12 (2): 164-169.