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 x₁, . . ., x_n. 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.

1 General rearrangement inequality
2 Applications
3 Proof
4 References

[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 σ.

$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.

Categories: Inequalities | Articles containing proofs

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Rearrangement inequality

From Wikipedia, the free encyclopedia

Contents

[edit] General rearrangement inequality

[edit] Applications

[edit] Proof

[edit] References

Views

Navigation

Interaction

Search

Languages