Нерівність перестановок

Нехай

${\displaystyle x_{1}\leq \cdots \leq x_{n}\quad \quad y_{1}\leq \cdots \leq y_{n}}$ — дійсні числа

${\displaystyle x_{\sigma (1)},\dots ,x_{\sigma (n)}}$ — перестановка чисел ${\displaystyle x_{1},\dots ,x_{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}.}$

Доведення

Друга нерівність випливає з першої, якщо її застосувати до послідовності

${\displaystyle -x_{n}\leq \cdots \leq -x_{1}.}$

Тому достатньо довести лише першу нерівність. Оскільки кількість перестановок є скінченною, принаймні для одної значення суми

${\displaystyle x_{\sigma (1)}y_{1}+\cdots +x_{\sigma (n)}y_{n}}$

є максимальним. Якщо таких перестановок є кілька нехай σ — та з них, що залишає незмінними найбільшу кількість чисел.

Доведемо, що σ — одинична перестановка. Припустимо, що це не так. Тоді існує число j ∈ {1, ..., n − 1}, таке що σ(j) ≠ j і σ(i) = i для всіх i ∈ {1, ..., j − 1}. Тому σ(j) > j і існує k ∈ {j + 1, ..., n} для якого σ(k) = j. Оскільки

${\displaystyle j<k\Rightarrow y_{j}\leq y_{k}\qquad {\text{and}}\qquad j=\sigma (k)<\sigma (j)\Rightarrow x_{j}\leq x_{\sigma (j)}.\quad (1)}$

Тому,

${\displaystyle 0\leq (x_{\sigma (j)}-x_{j})(y_{k}-y_{j}).\quad (2)}$

Розписуючи добуток отримуємо:

${\displaystyle x_{\sigma (j)}y_{j}+x_{j}y_{k}\leq x_{j}y_{j}+x_{\sigma (j)}y_{k}\,,\quad (3)}$

тому перестановка

${\displaystyle \tau (i):={\begin{cases}i&i\in \{1,\ldots ,j\},\\\sigma (j)&i=k,\\\sigma (i)&i\in \{j+1,\ldots ,n\}\setminus \{k\},\end{cases}}}$

що утворюється з σ заміною значень σ(j) і σ(k), має принаймні одну додаткову фіксовану точку j, і також є максимальною. Це суперечить вибору σ.

Якщо

${\displaystyle x_{1}<\cdots <x_{n}\quad \quad y_{1}<\cdots <y_{n},}$

то нерівності (1), (2), і (3) є строгими, тому максимум може бути досягнутим лише в одиничній перестановці.

Див. також

• Нерівність Чебишова для сум чисел

Посилання

• Доведення нерівності перестановок на PlanetMath.(англ.)