Umordnungsungleichung

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 \leq \cdots \leq x_n\quad \mbox{und}\quad y_1 \leq \cdots \leq y_n$.

Das Tupel

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

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

$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.$

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)\neq i$ erfüllt und jenes j mit i = σ(j) zu betrachten. Dann sind also σ(i) > i und j > i, daher gilt $x_{\sigma(j)}\leq x_{\sigma(i)}$ und $y_i\leq y_j$, also

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

und daher

$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.$

Solange also ein i mit $\sigma (i)\neq 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)\neq 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_2y_1+x_1y_2\leq x_1y_1+x_2y_2.$

Das ist aber äquivalent zu

$0\leq (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 σ(j) = n + 1. Der Fall j = n + 1 ist einfach zu behandeln, sei also $j\neq n+1.$ Dann gilt

$\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}.$

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

$\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}.$

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

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

so ergibt sich aus der Induktionsvoraussetzung

$\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},$

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.