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

<math>x_1 \leq \cdots \leq x_n\quad \mbox{und}\quad y_1 \leq \cdots \leq y_n</math>.

Das Tupel

<math>x_{\sigma}=\left(x_{\sigma (1)}, \dots ,x_{\sigma (n)}\right)</math>

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

<math>x_1y_1 + \cdots + x_ny_n \geq x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \geq x_ny_1 + \cdots + x_1y_n.</math>

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

Beweise

Beweis mittels Vertauschungen

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

<math>(x_{\sigma(i)}-x_{\sigma(j)})(y_i-y_j)\leq 0</math>

und daher

<math>x_{\sigma (i)}y_i + x_{\sigma(j)}y_j \leq x_{\sigma (j)}y_i + x_{\sigma(i)}y_j = x_i y_i + x_{\sigma(i)}y_j.</math>

Solange also ein <math>i</math> mit <math>\sigma (i)\neq i</math> 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 <math>i</math> mit <math>\sigma (i)\neq i</math> existiert.

Beweis mit Induktion

Dieser Beweis lässt sich ausführlicher auch mit vollständiger Induktion führen. Für den Induktionsanfang <math>n=2</math> 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 <math>j</math> der Index mit <math>\sigma(j)=n+1.</math> Der Fall <math>j=n+1</math> ist einfach zu behandeln, sei also <math>j\neq n+1.</math> Dann gilt

<math>\sum_{i=1}^{n+1}x_{\sigma(i)}y_i=\sum_{i\not\in\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(j)}y_j+x_{\sigma(n+1)}y_{n+1}=\sum_{i\not\in\{j, n+1\} }x_{\sigma(i)}y_i + x_{n+1}y_j+x_{\sigma(n+1)}y_{n+1}.</math>

Nun wendet man den im Induktionsanfang bewiesenen Fall <math>n=2</math> an und erhält

<math>\sum_{i\not\in\{j, n+1\} }x_{\sigma(i)}y_i + x_{n+1}y_j+x_{\sigma(n+1)}y_{n+1}\leq\sum_{i\not\in\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(n+1)}y_j+x_{n+1}y_{n+1}.</math>

Definiert man nun für <math>i=1,\dots,n</math> die Permutation

<math>\tau(i)=\begin{cases}\sigma(n+1) \qquad \textrm{falls} \quad i=j \\ \sigma(i) \qquad \textrm{sonst}\end{cases}</math>

so ergibt sich aus der Induktionsvoraussetzung

<math>\sum_{i\not\in\{j, n+1\} }x_{\sigma(i)}y_i + x_{\sigma(n+1)}y_j+x_{n+1}y_{n+1}=\sum_{i\not\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}\leq\sum_{i=1}^n x_{i}y_i+x_{n+1}y_{n+1},</math>

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.