Umordnungs-Ungleichung
# 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 $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}\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 $i$, das $\sigma (i)\neq 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)}\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_{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 $j$ 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.