Umordnungs-Ungleichung

In der Mathematik ist die Umordnungs-Ungleichung eine Aussage über die Veränderung des Wertes von formalen Skalarprodukten durch Umordnung.

Gegeben seien zwei n-Tupel reeller Zahlen und mit

.

Das Tupel

sei eine Permutation des Tupels . Fasst man nun die n-Tupel als Vektoren auf und betrachtet deren Standardskalarprodukt, so besagt die Umordnungs-Ungleichung, dass

Das Skalarprodukt ist also maximal, wenn die Elemente der n-Tupel gleich geordnet sind, und minimal, wenn sie entgegengesetzt geordnet sind.

Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von und notwendig sind.

Beweise

Beweis mittels Vertauschungen

Die Beweisidee besteht darin, das kleinste , das erfüllt, und jenes mit zu betrachten. Dann sind also und , daher gilt und , also

und daher

Solange also ein mit existiert, lässt sich die Summe für gleich geordnete Tupel vergrößern.

Analog zeigt man, dass sich die Summe für entgegengesetzt geordnete Tupel verkleinern lässt, solange ein mit existiert.

Beweis mit Induktion

Dieser Beweis lässt sich ausführlicher auch mit vollständiger Induktion führen. Für den Induktionsanfang gibt es nur zwei Permutationen, es ist also zu zeigen, dass

Das ist aber äquivalent zu

also zur Voraussetzung, dass beide Tupel gleich geordnet sind.

Im Induktionsschritt sei nun der Index mit Der Fall ist einfach zu behandeln, sei also Dann gilt

Nun wendet man den im Induktionsanfang bewiesenen Fall an und erhält

Definiert man nun für die Permutation

so ergibt sich aus der Induktionsvoraussetzung

also genau die Behauptung für das Maximum des Skalarprodukts.

Der Beweis für das Minimum des Skalarprodukts ist analog.

Anwendungen

Viele bekannte Ungleichungen lassen sich aus der Umordnungs-Ungleichung beweisen, beispielsweise die Ungleichung vom arithmetischen und geometrischen Mittel, Cauchy-Schwarzsche Ungleichung und die Tschebyschow-Summenungleichung.

Literatur

  • G. H. Hardy, J. E. Littlewood, G. Polya: Inequalities, Cambridge University Press (1952), Kapitel 10.2.