Umordnungs-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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_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[Bearbeiten]

Beweis mittels Vertauschungen[Bearbeiten]

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[Bearbeiten]

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 \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[Bearbeiten]

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[Bearbeiten]