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 $x=(x_1,\dots ,x_n)$ und $y=(y_1,\dots ,y_n)$ mit

$x_1\le \cdots \le x_n\text{und}{y}_1\le \cdots \le y_n$.

Das Tupel

$x_{\sigma }=(x_{\sigma (1)},\dots ,x_{\sigma (n)})$

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

$x_1{y}_1+\cdots +x_n{y}_n\ge x_{\sigma (1)}{y}_1+\cdots +x_{\sigma (n)}{y}_n\ge x_n{y}_1+\cdots +x_1{y}_n.$

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 $x_i$ und $y_i$ notwendig sind.

Beweise

Beweis mittels Vertauschungen

Die Beweisidee besteht darin, das kleinste $i$, das $\sigma (i)\ne i$ erfüllt, und jenes $j$ mit $i=\sigma (j)$ zu betrachten. Dann sind also $\sigma (i)>i$ und $j>i$, daher gilt $x_{\sigma (j)}\le x_{\sigma (i)}$ und $y_i\le y_j$, also

$(x_{\sigma (i)}-x_{\sigma (j)})(y_i-y_j)\le 0$

und daher

$x_{\sigma (i)}{y}_i+x_{\sigma (j)}{y}_j\le x_{\sigma (j)}{y}_i+x_{\sigma (i)}{y}_j=x_i{y}_i+x_{\sigma (i)}{y}_j.$

Solange also ein $i$ mit $\sigma (i)\ne i$ 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 $i$ mit $\sigma (i)\ne i$ existiert.

Beweis mit Induktion

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

$x_2{y}_1+x_1{y}_2\le x_1{y}_1+x_2{y}_2.$

Das ist aber äquivalent zu

$0\le (y_1-y_2)(x_1-x_2),$

also zur Voraussetzung, dass beide Tupel gleich geordnet sind.

Im Induktionsschritt sei nun $j$ der Index mit $\sigma (j)=n+1.$ Der Fall $j=n+1$ ist einfach zu behandeln, sei also $j\ne n+1.$ Dann gilt

$\sum _{i=1}^{n+1}{x}_{\sigma (i)}{y}_i=\sum _{i\in ̸\{j,n+1\}}{x}_{\sigma (i)}{y}_i+x_{\sigma (j)}{y}_j+x_{\sigma (n+1)}{y}_{n+1}=\sum _{i\in ̸\{j,n+1\}}{x}_{\sigma (i)}{y}_i+x_{n+1}{y}_j+x_{\sigma (n+1)}{y}_{n+1}.$

Nun wendet man den im Induktionsanfang bewiesenen Fall $n=2$ an und erhält

$\sum _{i\in ̸\{j,n+1\}}{x}_{\sigma (i)}{y}_i+x_{n+1}{y}_j+x_{\sigma (n+1)}{y}_{n+1}\le \sum _{i\in ̸\{j,n+1\}}{x}_{\sigma (i)}{y}_i+x_{\sigma (n+1)}{y}_j+x_{n+1}{y}_{n+1}.$

Definiert man nun für $i=1,\dots ,n$ die Permutation

$\tau (i)=\{\begin{array}{c}\sigma (n+1)\text{falls}i=j\\ \sigma (i)\text{sonst}\end{array}$

so ergibt sich aus der Induktionsvoraussetzung

$\sum _{i\in ̸\{j,n+1\}}{x}_{\sigma (i)}{y}_i+x_{\sigma (n+1)}{y}_j+x_{n+1}{y}_{n+1}=\sum _{i\in ̸\{j,n+1\}}{x}_{\tau (i)}{y}_i+x_{\tau (j)}{y}_j+x_{n+1}{y}_{n+1}=\sum _{i=1}^n{x}_{\tau (i)}{y}_i+x_{n+1}{y}_{n+1}\le \sum _{i=1}^n{x}_i{y}_i+x_{n+1}{y}_{n+1},$

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.