Неравенство перестановки

В математике перестановки неравенство утверждает, что для каждого выбора действительных чисел $$x_{1}\leq \cdots \leq x_{n}\quad {\text{ and }}\quad y_{1}\leq \cdots \leq y_{n}$$и каждая перестановка $\sigma$ чисел $1,2,\ldots n$ у нас есть

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

Неформально это означает, что в таких типах сумм наибольшая сумма получается путем спаривания больших $x$ значения с большими $y$ значения, а наименьшая сумма достигается путем объединения малых значений с большими значениями. Это можно формализовать в том случае, если $x_{1},\ldots ,x_{n}$ различны, а это означает, что $x_{1}<\cdots <x_{n},$ затем:

1. Верхняя оценка в ( 1 ) достигается только для перестановок $\sigma$ которые поддерживают порядок $y_{1},\ldots ,y_{n},$ то есть, $$y_{\sigma (1)}\leq \cdots \leq y_{\sigma (n)},$$ или эквивалентно $(y_{1},\ldots ,y_{n})=(y_{\sigma (1)},\ldots ,y_{\sigma (n)}).$ Такой $\sigma$ можно переставлять индексы $y$-ценности, которые равны; в случае $y_{1}=\cdots =y_{n}$ каждая перестановка сохраняет порядок $y_{1},\ldots ,y_{n}.$ Если $y_{1}<\cdots <y_{n},$ тогда единственный такой $\sigma$ это личность.
2. Соответственно нижняя оценка в ( 1 ) достигается только для перестановок $\sigma$ которые меняют порядок $y_{1},\ldots ,y_{n},$ это означает, что $$y_{\sigma (1)}\geq \cdots \geq y_{\sigma (n)}.$$ Если $y_{1}<\cdots <y_{n},$ затем $\sigma (i)=n-i+1$ для всех $i=1,\ldots ,n,$ это единственная перестановка, позволяющая сделать это.

Обратите внимание, что неравенство перестановки ( 1 ) не делает никаких предположений о знаках действительных чисел, в отличие от таких неравенств, как среднее арифметико-геометрическое неравенство .

Приложения

Многие важные неравенства могут быть доказаны с помощью неравенства перестановки, например, среднее арифметическое – неравенство среднего геометрического , неравенство Коши – Шварца и неравенство суммы Чебышева .

В качестве простого примера рассмотрим действительные числа. $x_{1}\leq \cdots \leq x_{n}$: Применяя ( 1 ) с $y_{i}:=x_{i}$ для всех $i=1,\ldots ,n,$ отсюда следует, что $$x_{1}x_{n}+\cdots +x_{n}x_{1}\leq x_{1}x_{\sigma (1)}+\cdots +x_{n}x_{\sigma (n)}\leq x_{1}^{2}+\cdots +x_{n}^{2}$$для каждой перестановки $\sigma$ из $1,\ldots ,n.$

Интуиция

Неравенство перестановки можно считать интуитивным следующим образом. Представьте себе, что есть стопка 10-долларовых купюр, стопка 20-долларовых купюр и еще одна стопка 100-долларовых купюр. Вам разрешено взять 7 купюр из выбранной вами стопки, после чего стопка исчезает. Во втором раунде вам разрешается взять 5 купюр из другой кучки, и кучка исчезает. В последнем раунде вы можете взять 3 купюры из последней стопки. В каком порядке вы хотите выбирать стопки, чтобы максимизировать свою прибыль? Очевидно, лучшее, что вы можете сделать, — это получить $7\cdot 100+5\cdot 20+3\cdot 10$ долларов. Именно об этом говорит верхняя оценка неравенства перестановки ( 1 ) для последовательностей $3<5<7$ и $10<20<100.$ В этом смысле его можно рассматривать как пример жадного алгоритма .

Геометрическая интерпретация

Предположим, что $0<x_{1}<\cdots <x_{n}$ и $0<y_{1}<\cdots <y_{n}.$ Рассмотрим прямоугольник шириной $x_{1}+\cdots +x_{n}$ и высота $y_{1}+\cdots +y_{n},$ подразделяется на $n$ столбцы ширины $x_{1},\ldots ,x_{n}$ и такое же количество рядов высот $y_{1},\ldots ,y_{n},$ так что есть $\textstyle n^{2}$ маленькие прямоугольники. Вы должны взять $n$ из них по одному из каждого столбца и по одному из каждой строки. Неравенство перестановки ( 1 ) говорит, что вы оптимизируете общую площадь вашего выбора, беря прямоугольники по диагонали или антидиагонали.

Доказательства

Доказательство от противного

Нижняя оценка и соответствующее обсуждение равенства следуют путем применения результатов для верхней оценки к $$-y_{n}\leq \cdots \leq -y_{1}.$$Поэтому достаточно доказать верхнюю оценку в ( 1 ) и обсудить, когда равенство имеет место. Поскольку существует лишь конечное число перестановок $1,\ldots ,n,$ существует хотя бы один $\sigma$ для которого средний член в ( 1 ) $$x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}$$является максимальным. В случае, если существует несколько перестановок с этим свойством, пусть σ обозначает одну с наибольшим количеством целых чисел. $i$ от $\{1,\ldots ,n\}$ удовлетворяющий $y_{i}=y_{\sigma (i)}.$

Теперь мы докажем от противного , что $\sigma$ должен поддерживать порядок $y_{1},\ldots ,y_{n}$ (тогда мы закончили с верхней границей в ( 1 ), поскольку тождество обладает этим свойством). Предположим, что существует $j\in \{1,\ldots ,n-1\}$ такой, что $y_{i}=y_{\sigma (i)}$ для всех $i\in \{1,\ldots ,j-1\}$ и $y_{j}\neq y_{\sigma (j)}.$ Следовательно $y_{j}<y_{\sigma (j)}$ и должен существовать $k\in \{j+1,\ldots ,n\}$ с $y_{j}=y_{\sigma (k)}$ чтобы заполнить пробел. Поэтому,

$x_{j}\leq x_{k}\qquad {\text{and}}\qquad y_{\sigma (k)}<y_{\sigma (j)},$ ( 2 )

что подразумевает, что

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

Расширение этого продукта и перестановка дает

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

что эквивалентно ( 3 ). Отсюда и перестановка $$\tau (i):={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,k\},\\\sigma (k)&{\text{for }}i=j,\\\sigma (j)&{\text{for }}i=k,\end{cases}}$$который возникает из $\sigma$ путем обмена значениями $\sigma (j)$ и $\sigma (k),$ имеет хотя бы одну дополнительную точку, которая сохраняет порядок по сравнению с $\sigma ,$ а именно в $j$ удовлетворяющий $y_{j}=y_{\tau (j)},$ а также достигает максимума в ( 1 ) благодаря ( 4 ). Это противоречит выбору $\sigma .$

Если $x_{1}<\cdots <x_{n},$ тогда мы имеем строгие неравенства в ( 2 ), ( 3 ) и ( 4 ), следовательно, максимума можно достичь только перестановками, сохраняющими порядок $y_{1}\leq \cdots \leq y_{n},$ и любая другая перестановка $\sigma$ не может быть оптимальным.

Доказательство по индукции

Как и выше, достаточно рассмотреть верхнюю оценку в ( 1 ). Для доказательства методом математической индукции мы начнем с $n=2.$ Обратите внимание, что $$x_{1}\leq x_{2}\quad {\text{ and }}\quad y_{1}\leq y_{2}$$подразумевает, что

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

что эквивалентно

$x_{1}y_{2}+x_{2}y_{1}\leq x_{1}y_{1}+x_{2}y_{2},$ ( 6 )

следовательно, верхняя оценка в ( 1 ) верна для $n=2.$Если $x_{1}<x_{2},$ тогда мы получаем строгое неравенство в ( 5 ) и ( 6 ) тогда и только тогда, когда $y_{1}<y_{2}.$ Следовательно, только тождество, которое является здесь единственной перестановкой, сохраняющей порядок $y_{1}<y_{2},$ дает максимум.

В качестве предположения индукции предположим, что верхняя оценка в неравенстве перестановки ( 1 ) верна для $n-1$ с $n\geq 3$ и это в деле $x_{1}<\cdots <x_{n-1}$ равенство существует только тогда, когда перестановка $\sigma$ из $1,\ldots ,n-1$ поддерживает порядок $y_{1},\ldots ,y_{n-1}.$

Рассмотрим сейчас $x_{1}\leq \cdots \leq x_{n}$ и $y_{1}\leq \cdots \leq y_{n}.$ Возьмите $\sigma$ из конечного числа перестановок $1,\ldots ,n$ такой, что перестановка в середине ( 1 ) дает максимальный результат. Есть два случая:

• Если $\sigma (n)=n,$ затем $y_{n}=y_{\sigma (n)}$ и, используя предположение индукции, верхняя оценка в ( 1 ) верна с равенством и $\sigma$ поддерживает порядок $y_{1},\ldots ,y_{n-1},y_{n}$ в случае $x_{1}<\cdots <x_{n}.$
• Если $k:=\sigma (n)<n,$ тогда есть $j\in \{1,\dots ,n-1\}$ с $\sigma (j)=n.$ Определите перестановку $$\tau (i)={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,n\},\\k&{\text{for }}i=j,\\n&{\text{for }}i=n,\end{cases}}$$ который возникает из $\sigma$ путем обмена значениями $j$ и $n.$ Теперь есть два подслучая:

1. Если $x_{k}=x_{n}$ или $y_{k}=y_{n},$ то этот обмен ценностями $\sigma$ не влияет на средний член в ( 1 ), поскольку $\tau$ дает ту же сумму, и мы можем продолжить, применив первый случай к $\tau .$ Обратите внимание, что в случае $x_{1}<\cdots <x_{n},$ перестановка $\tau$ поддерживает порядок $y_{1},\ldots ,y_{n}$ тогда и только тогда, когда $\sigma$ делает.
2. Если $x_{k}<x_{n}$ и $y_{k}<y_{n},$ затем $0<(x_{n}-x_{k})(y_{n}-y_{k}),$ что эквивалентно $x_{k}y_{n}+x_{n}y_{k}<x_{k}y_{k}+x_{n}y_{n}$ и показывает, что $\sigma$ не является оптимальным, следовательно, этот случай не может произойти из-за выбора $\sigma .$

Обобщения

Три или более последовательностей

Простое обобщение учитывает больше последовательностей. Предположим, что у нас есть конечные упорядоченные последовательности неотрицательных действительных чисел. $$0\leq x_{1}\leq \cdots \leq x_{n}\quad {\text{and}}\quad 0\leq y_{1}\leq \cdots \leq y_{n}\quad {\text{and}}\quad 0\leq z_{1}\leq \cdots \leq z_{n}$$и перестановка $y_{\sigma (1)},\ldots ,y_{\sigma (n)}$ из $y_{1},\dots ,y_{n}$ и еще одна перестановка $z_{\tau (1)},\dots ,z_{\tau (n)}$ из $z_{1},\dots ,z_{n}.$ Затем $$x_{1}y_{\sigma (1)}z_{\tau (1)}+\cdots +x_{n}y_{\sigma (n)}z_{\tau (n)}\leq x_{1}y_{1}z_{1}+\cdots +x_{n}y_{n}z_{n}.$$

Обратите внимание, что, в отличие от стандартного неравенства перестановки ( 1 ), это утверждение требует, чтобы числа были неотрицательными. Аналогичное утверждение верно для любого количества последовательностей, все числа которых неотрицательны.

Функции вместо факторов

Другое обобщение неравенства перестановки гласит, что для всех действительных чисел $x_{1}\leq \cdots \leq x_{n}$ и любой выбор непрерывно дифференцируемых функций $f_{i}:[x_{1},x_{n}]\to \mathbb {R}$ для $i=1,2,\ldots ,n$ такие, что их производные $f'_{1},\ldots ,f'_{n}$ удовлетворить $$f'_{1}(x)\leq f'_{2}(x)\leq \cdots \leq f'_{n}(x)\quad {\text{ for all }}x\in [x_{1},x_{n}],$$неравенство $$\sum _{i=1}^{n}f_{n-i+1}(x_{i})\leq \sum _{i=1}^{n}f_{\sigma (i)}(x_{i})\leq \sum _{i=1}^{n}f_{i}(x_{i})$$справедливо для каждой перестановки $f_{\sigma (1)},\ldots ,f_{\sigma (n)}$ из $f_{1},\ldots ,f_{n}.$Берем реальные цифры $y_{1}\leq \cdots \leq y_{n}$ и линейные функции $f_{i}(x):=xy_{i}$ серьезно $x$ и $i=1,\ldots ,n,$ стандартное перестановочное неравенство ( 1 ) восстанавливается.

См. также

• Неравенство Харди – Литтлвуда
• Неравенство сумм Чебышева