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

Нехай

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

$x_{\sigma (1)},\dots ,x_{\sigma (n)}$ — перестановка чисел $x_{1},\dots ,x_{n}$.

Тоді справедливою є нерівність:

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

Доведення

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

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

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

$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. Оскільки

$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)$

Тому,

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

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

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

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

$\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, і також є максимальною. Це суперечить вибору σ.

Якщо

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

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

Див. також

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

Посилання

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