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
,
…
,
x
n
)
{\displaystyle x=(x_{1},\dots ,x_{n})}
y
=
(
y
1
,
…
,
y
n
)
{\displaystyle y=(y_{1},\dots ,y_{n})}
x
1
≤
⋯
≤
x
n
und
y
1
≤
⋯
≤
y
n
{\displaystyle x_{1}\leq \cdots \leq x_{n}\quad {\mbox{und}}\quad y_{1}\leq \cdots \leq y_{n}}
Das Tupel
x
σ
=
(
x
σ
(
1
)
,
…
,
x
σ
(
n
)
)
{\displaystyle x_{\sigma }=\left(x_{\sigma (1)},\dots ,x_{\sigma (n)}\right)}
sei eine Permutation des Tupels
x
{\displaystyle x}
Tupel als Vektoren auf und betrachtet deren Standardskalarprodukt , so besagt die Umordnungs-Ungleichung , dass
x
1
y
1
+
⋯
+
x
n
y
n
≥
x
σ
(
1
)
y
1
+
⋯
+
x
σ
(
n
)
y
n
≥
x
n
y
1
+
⋯
+
x
1
y
n
.
{\displaystyle 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
{\displaystyle x_{i}}
y
i
{\displaystyle y_{i}}
Die Beweisidee besteht darin, das kleinste
i
{\displaystyle i}
σ
(
i
)
≠
i
{\displaystyle \sigma (i)\neq i}
j
{\displaystyle j}
i
=
σ
(
j
)
{\displaystyle i=\sigma (j)}
σ
(
i
)
>
i
{\displaystyle \sigma (i)>i}
j
>
i
{\displaystyle j>i}
x
σ
(
j
)
≤
x
σ
(
i
)
{\displaystyle x_{\sigma (j)}\leq x_{\sigma (i)}}
y
i
≤
y
j
{\displaystyle y_{i}\leq y_{j}}
(
x
σ
(
i
)
−
x
σ
(
j
)
)
(
y
i
−
y
j
)
≤
0
{\displaystyle (x_{\sigma (i)}-x_{\sigma (j)})(y_{i}-y_{j})\leq 0}
und daher
x
σ
(
i
)
y
i
+
x
σ
(
j
)
y
j
≤
x
σ
(
j
)
y
i
+
x
σ
(
i
)
y
j
=
x
i
y
i
+
x
σ
(
i
)
y
j
.
{\displaystyle 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
{\displaystyle i}
σ
(
i
)
≠
i
{\displaystyle \sigma (i)\neq i}
Analog zeigt man, dass sich die Summe für entgegengesetzt geordnete Tupel verkleinern lässt, solange ein
i
{\displaystyle i}
σ
(
i
)
≠
i
{\displaystyle \sigma (i)\neq i}
Dieser Beweis lässt sich ausführlicher auch mit vollständiger Induktion führen. Für den Induktionsanfang
n
=
2
{\displaystyle n=2}
x
2
y
1
+
x
1
y
2
≤
x
1
y
1
+
x
2
y
2
.
{\displaystyle x_{2}y_{1}+x_{1}y_{2}\leq x_{1}y_{1}+x_{2}y_{2}.}
Das ist aber äquivalent zu
0
≤
(
y
1
−
y
2
)
(
x
1
−
x
2
)
,
{\displaystyle 0\leq (y_{1}-y_{2})(x_{1}-x_{2}),}
also zur Voraussetzung, dass beide Tupel gleich geordnet sind.
Im Induktionsschritt sei nun
j
{\displaystyle j}
σ
(
j
)
=
n
+
1.
{\displaystyle \sigma (j)=n+1.}
j
=
n
+
1
{\displaystyle j=n+1}
j
≠
n
+
1.
{\displaystyle j\neq n+1.}
∑
i
=
1
n
+
1
x
σ
(
i
)
y
i
=
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
j
)
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
=
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
n
+
1
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
.
{\displaystyle \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
{\displaystyle n=2}
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
n
+
1
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
≤
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
n
+
1
)
y
j
+
x
n
+
1
y
n
+
1
.
{\displaystyle \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
,
…
,
n
{\displaystyle i=1,\dots ,n}
τ
(
i
)
=
{
σ
(
n
+
1
)
falls
i
=
j
σ
(
i
)
sonst
{\displaystyle \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
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
n
+
1
)
y
j
+
x
n
+
1
y
n
+
1
=
∑
i
∉
{
j
,
n
+
1
}
x
τ
(
i
)
y
i
+
x
τ
(
j
)
y
j
+
x
n
+
1
y
n
+
1
=
∑
i
=
1
n
x
τ
(
i
)
y
i
+
x
n
+
1
y
n
+
1
≤
∑
i
=
1
n
x
i
y
i
+
x
n
+
1
y
n
+
1
,
{\displaystyle \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.
