Beweis mittels Vertauschungen

Die Beweisidee besteht darin, das kleinste ${\displaystyle i}$, das ${\displaystyle \sigma (i)\neq i}$ erfüllt, und jenes ${\displaystyle j}$ mit ${\displaystyle i=\sigma (j)}$ zu betrachten. Dann sind also ${\displaystyle \sigma (i)>i}$ und ${\displaystyle j>i}$, daher gilt ${\displaystyle x_{\sigma (j)}\leq x_{\sigma (i)}}$ und ${\displaystyle y_{i}\leq y_{j}}$, also

${\displaystyle (x_{\sigma (i)}-x_{\sigma (j)})(y_{i}-y_{j})\leq 0}$

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}.}$

Solange also ein ${\displaystyle i}$ mit ${\displaystyle \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 ${\displaystyle i}$ mit ${\displaystyle \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 ${\displaystyle n=2}$ 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}.}$

Das ist aber äquivalent zu

${\displaystyle 0\leq (y_{1}-y_{2})(x_{1}-x_{2}),}$

also zur Voraussetzung, dass beide Tupel gleich geordnet sind.

Im Induktionsschritt sei nun ${\displaystyle j}$ der Index mit ${\displaystyle \sigma (j)=n+1.}$ Der Fall ${\displaystyle j=n+1}$ ist einfach zu behandeln, sei also ${\displaystyle j\neq n+1.}$ 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}.}$

Nun wendet man den im Induktionsanfang bewiesenen Fall ${\displaystyle n=2}$ 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}.}$

Definiert man nun für ${\displaystyle i=1,\dots ,n}$ die Permutation

${\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

${\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.