Rearrangement inequality

In mathematics, the rearrangement inequality is a statement about the change in the value of formal scalar products by rearrangement.

Given two n- tuples of real numbers and with

The tuple

Is a permutation of the tuple. Summing up the n- tuples as vectors and considers its standard scalar product, so says the rearrangement inequality that

Thus, the dot product is a maximum when the elements of the n-grams are sorted matter and a minimum when they are arranged in opposite directions.

Note that in contrast to many other inequalities are no prerequisites for the signs of and necessary.

Evidence

Proof by means of permutations

The idea of ​​the proof is to consider the smallest that meets and one with. Then so are and, therefore, applies and so

And therefore

So as long as one exists with, the total for sibling tuples can be increased.

Analogously, one can show that the sum of opposite ordered tuple can reduce, as long as a with exists.

Proof by induction

This proof can be more fully lead by induction. For the base case there are only two permutations, so it's to show that

But this is equivalent to

So the condition that both tuples are ordered the same.

In the induction step, let the index with The case is easy to deal with, so be Then

Now one applies the proven in the induction base case and receives

Then, imagine that for the permutation

It follows from the induction hypothesis

Exactly the assertion for the maximum of the scalar product.

The proof for the minimum of the scalar product is analogous.

Applications

Many well-known inequalities can be derived from the rearrangement inequality to prove, for example, the inequality of the arithmetic and geometric means, Cauchy- Schwarz inequality and the Chebyshev - Summenungleichung.