Rearrangement inequality

Rearrangement inequality

In mathematics, the rearrangement inequality states that

:x_ny_1 + cdots + x_1y_nle x_{sigma (1)}y_1 + cdots + x_{sigma (n)}y_nle x_1y_1 + cdots + x_ny_n

for every choice of real numbers

:x_1lecdotsle x_nquad ext{and}quad y_1lecdotsle y_n

and every permutation

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

of "x"1, . . ., "xn". If the numbers are different, meaning that

:x_1

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.

General rearrangement inequality

For an integer "n" ≤ 4 and any two sets of real numbers

: x_1lecdotsle x_n ext{ and }y_1lecdotsle y_n,,

we have

: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 pairs of indices (i,j) that 1le i and pi(i)>pi(j)) than the permutation sigma.Note that the identity permutation (1, 2, ..., "n") has zero inversions while the permutation ("n", "n" − 1, ..., 1) has the maximum possible number of inversions equal to "n"("n" − 1)/2, implying the classic rearrangement inequality.

Original publication [cite journal |author=Alan Wayne |title=Inequalities and inversions of order |journal=Scripta Mathematica |year=1946 |volume=12 |issue=2 |pages=164–169] of the general rearrangement inequality claimed its correctness for all integer "n" ≥ 1, however for "n" = 5 and up there exist counterexamples.

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.

Proof

The lower bound follows by applying the upper bound to

:-x_nlecdotsle-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 Therefore,

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

Expanding this product and rearranging gives

:x_{sigma(j)}y_j+x_jy_kle x_jy_j+x_{sigma(j)}y_k,, quad(3)

hence the permutation

: au(i):=egin{cases}i& ext{for }iin{1,ldots,j},\sigma(j)& ext{for }i=k,\sigma(i)& ext{for }iin{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

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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Inequality of arithmetic and geometric means — In mathematics, the inequality of arithmetic and geometric means, or more briefly the AM GM inequality, states that the arithmetic mean of a list of non negative real numbers is greater than or equal to the geometric mean of the same list; and… …   Wikipedia

  • Weitzenböck's inequality — In mathematics, Weitzenböck s inequality states that for a triangle of side lengths a, b, c, and area Delta, the following inequality holds:: a^2 + b^2 + c^2 geq 4sqrt{3}, Delta. Equality occurs if and only if the triangle is equilateral. Pedoe s …   Wikipedia

  • Nesbitt's inequality — In mathematics, Nesbitt s inequality is a special case of the Shapiro inequality. It states that for positive real numbers a, b and c we have: Contents 1 Proof 1.1 First proof …   Wikipedia

  • Chebyshev's sum inequality — For the similarly named inequality in probability theory, see Chebyshev s inequality. In mathematics, Chebyshev s sum inequality, named after Pafnuty Chebyshev, states that if and then Similarly, if …   Wikipedia

  • List of inequalities — This page lists Wikipedia articles about named mathematical inequalities. Inequalities in pure mathematics =Analysis= * Askey–Gasper inequality * Bernoulli s inequality * Bernstein s inequality (mathematical analysis) * Bessel s inequality *… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Spearman's rank correlation coefficient — In statistics, Spearman s rank correlation coefficient or Spearman s rho, named after Charles Spearman and often denoted by the Greek letter ho (rho) or as r s, is a non parametric measure of correlation ndash; that is, it assesses how well an… …   Wikipedia

  • Scientific phenomena named after people — This is a list of scientific phenomena and concepts named after people (eponymous phenomena). For other lists of eponyms, see eponym. NOTOC A* Abderhalden ninhydrin reaction Emil Abderhalden * Abney effect, Abney s law of additivity William de… …   Wikipedia

  • Pythagorean theorem — See also: Pythagorean trigonometric identity The Pythagorean theorem: The sum of the areas of the two squares on the legs (a and b) equals the area of the square on the hypotenuse (c) …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”