Umordnungs-Ungleichung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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.

Inhaltsverzeichnis

1 Beweise
- 1.1 Beweis mittels Vertauschungen
- 1.2 Beweis mit Induktion
2 Anwendungen
3 Literatur

[Bearbeiten] Beweise

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

[Bearbeiten] 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},$