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
und
mit
.
Das Tupel
![{\displaystyle x_{\sigma }=\left(x_{\sigma (1)},\dots ,x_{\sigma (n)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4720a7197bc44de8722997e044b095366b325e5c)
sei eine Permutation des Tupels
. Fasst man nun die n-Tupel als Vektoren auf und betrachtet deren Standardskalarprodukt, so besagt die Umordnungs-Ungleichung, dass
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df513266161d1f7309ea3b4214511a06456cc2ba)
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
und
notwendig sind.
Die Beweisidee besteht darin, das kleinste
, das
erfüllt, und jenes
mit
zu betrachten. Dann sind also
und
, daher gilt
und
, also
![{\displaystyle (x_{\sigma (i)}-x_{\sigma (j)})(y_{i}-y_{j})\leq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/676c7b5ef17b376d9c1acb77c0e382feeaea00f7)
und daher
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba45939d57d5870a2dcce1228d03ba8b3c3dfe11)
Solange also ein
mit
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
existiert.
Dieser Beweis lässt sich ausführlicher auch mit vollständiger Induktion führen. Für den Induktionsanfang
gibt es nur zwei Permutationen, es ist also zu zeigen, dass
![{\displaystyle x_{2}y_{1}+x_{1}y_{2}\leq x_{1}y_{1}+x_{2}y_{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fe2a5a4660f3b098a4bb45777b612fa5f97d3b2)
Das ist aber äquivalent zu
![{\displaystyle 0\leq (y_{1}-y_{2})(x_{1}-x_{2}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5512ab5c8cdb4db66a7369e149604bfbaca1770)
also zur Voraussetzung, dass beide Tupel gleich geordnet sind.
Im Induktionsschritt sei nun
der Index mit
Der Fall
ist einfach zu behandeln, sei also
Dann gilt
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b360ffffc6f49e87be11d729ae8ed0916edcd0a)
Nun wendet man den im Induktionsanfang bewiesenen Fall
an und erhält
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23f6f6372a477b489f85369cdd4d7257ed4a2cf6)
Definiert man nun für
die Permutation
![{\displaystyle \tau (i)={\begin{cases}\sigma (n+1)\qquad {\textrm {falls}}\quad i=j\\\sigma (i)\qquad {\textrm {sonst}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9978e1e89fb37c859f01a985eef80ad759f5a7d)
so ergibt sich aus der Induktionsvoraussetzung
![{\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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/675152da1db05c5db44ee199816a62a5786f1015)
also genau die Behauptung für das Maximum des Skalarprodukts.
Der Beweis für das Minimum des Skalarprodukts ist analog.
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.