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}\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 . 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}\geq x_{{\sigma (1)}}y_{1}+\cdots +x_{{\sigma (n)}}y_{n}\geq 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 , das $\sigma (i)\neq i$ erfüllt, und jenes mit $i=\sigma (j)$ zu betrachten. Dann sind also $\sigma (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 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 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_{2}y_{1}+x_{1}y_{2}\leq x_{1}y_{1}+x_{2}y_{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 der Index mit $\sigma (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.

Basierend auf einem Artikel in:

Wikipedia.de