Wikipedia · einfach zusammengefasst · Stand
Umordnungs-Ungleichung
In der Mathematik ist die Umordnungs-Ungleichung eine Aussage über die Veränderung des Wertes von formalen Skalarprodukten durch Umordnung.
Inhalt4 Abschnitte
Grundidee und Aussage
Die Umordnungs-Ungleichung beschreibt, wie sich das Standardskalarprodukt zweier reeller n-Tupel durch eine Umordnung verändert. Gegeben seien x = (x₁, …, xₙ) und y = (y₁, …, yₙ) mit x₁ ≤ ⋯ ≤ xₙ und y₁ ≤ ⋯ ≤ yₙ. Für eine Permutation σ des Tupels x sei xσ = (xσ(1), …, xσ(n)).
Dann gilt:
x₁y₁ + ⋯ + xₙyₙ ≥ xσ(1)y₁ + ⋯ + xσ(n)yₙ ≥ xₙy₁ + ⋯ + x₁yₙ.
Das Skalarprodukt ist somit maximal, wenn die Elemente beider Tupel gleich geordnet miteinander multipliziert werden: das kleinste xᵢ steht beim kleinsten yᵢ und das größte xᵢ beim größten yᵢ. Es ist minimal, wenn die Tupel entgegengesetzt geordnet sind: xₙ wird mit y₁, xₙ₋₁ mit y₂ und so weiter multipliziert.
Eine wichtige Besonderheit ist, dass keine Voraussetzungen für die Vorzeichen der xᵢ und yᵢ nötig sind. Die Aussage gilt also auch dann, wenn positive und negative Zahlen vorkommen.
Beweis durch Vertauschungen
Für das Maximum betrachtet man das kleinste i mit σ(i) ≠ i sowie ein j mit i = σ(j). Daraus folgen σ(i) > i und j > i. Wegen der aufsteigenden Ordnung gilt xσ(j) ≤ xσ(i) und yᵢ ≤ yⱼ. Deshalb ist
(xσ(i) − xσ(j))(yᵢ − yⱼ) ≤ 0.
Durch Umformen erhält man
xσ(i)yᵢ + xσ(j)yⱼ ≤ xσ(j)yᵢ + xσ(i)yⱼ = xᵢyᵢ + xσ(i)yⱼ.
Die Summe kann also vergrößert werden, solange noch ein Index i mit σ(i) ≠ i existiert. Wiederholt man solche Vertauschungen, gelangt man zur gleich geordneten Anordnung. Diese liefert daher das Maximum.
Analog zeigt man, dass die Summe für die entgegengesetzt geordnete Anordnung verkleinert werden kann, solange die Permutation noch nicht diese Anordnung erreicht hat. Damit ist auch das Minimum bewiesen.
Beweis durch vollständige Induktion
Der Induktionsanfang für n = 2 besteht darin, die beiden möglichen Anordnungen zu vergleichen. Zu zeigen ist
x₂y₁ + x₁y₂ ≤ x₁y₁ + x₂y₂.
Diese Aussage ist äquivalent zu
0 ≤ (y₁ − y₂)(x₁ − x₂).
Sie folgt daraus, dass beide Tupel gleich geordnet sind: Sowohl y₁ − y₂ als auch x₁ − x₂ sind nichtpositiv, ihr Produkt ist daher nichtnegativ.
Im Induktionsschritt wird die Aussage für n Tupel vorausgesetzt und für n + 1 Tupel bewiesen. Sei j der Index mit σ(j) = n + 1. Falls j = n + 1 gilt, ist der größte Wert xₙ₊₁ bereits an der passenden Stelle. Für j ≠ n + 1 betrachtet man die beiden Terme an den Stellen j und n + 1. Mit dem Fall n = 2 kann man sie so vertauschen, dass xₙ₊₁ mit yₙ₊₁ multipliziert wird. Dadurch wird die Summe nicht kleiner.
Anschließend definiert man für i = 1, …, n eine Permutation τ durch
τ(i) = σ(n + 1), falls i = j, und τ(i) = σ(i) sonst.
Auf die ersten n Terme kann nun die Induktionsvoraussetzung angewendet werden. Zusammen mit dem unveränderten Term xₙ₊₁yₙ₊₁ ergibt sich
∑ᵢ₌₁ⁿ xτ(i)yᵢ + xₙ₊₁yₙ₊₁ ≤ ∑ᵢ₌₁ⁿ xᵢyᵢ + xₙ₊₁yₙ₊₁.
Damit ist die Behauptung für das Maximum bewiesen. Der Beweis für das Minimum verläuft analog.
Anwendungen
Die Umordnungs-Ungleichung ist ein Hilfsmittel zum Beweis mehrerer bekannter Ungleichungen. Dazu gehören die Ungleichung vom arithmetischen und geometrischen Mittel, die Cauchy-Schwarzsche Ungleichung und die Tschebyschow-Summenungleichung. Ihre Bedeutung liegt darin, dass sie eine allgemeine Regel bereitstellt, mit der sich die Wirkung verschiedener Anordnungen auf eine Summe von Produkten vergleichen lässt.