Неравенство Мюрхеда

В математике , неравенство Мюрхеда названное в честь Роберта Франклина Мюрхеда , также известное как метод «группировки», обобщает неравенство средних арифметических и геометрических .

Предварительные определения

-среднее ​

Для любого вещественного вектора

$a=(a_{1},\dots ,a_{n})$

определите « a -mean» [ a ] положительных действительных чисел x ₁ , ..., x _n с помощью

$[a]={\frac {1}{n!}}\sum _{\sigma }x_{\sigma _{1}}^{a_{1}}\cdots x_{\sigma _{n}}^{a_{n}},$

где сумма распространяется на все перестановки σ из { 1, ..., n }.

Когда элементы a являются неотрицательными целыми числами, a -среднее может быть эквивалентно определено через мономиальный симметричный многочлен $m_{a}(x_{1},\dots ,x_{n})$ как

$[a]={\frac {k_{1}!\cdots k_{l}!}{n!}}m_{a}(x_{1},\dots ,x_{n}),$

где ℓ — количество различных элементов в a , а k ₁ , ..., k _ℓ — их кратности.

Обратите внимание, что а -среднее, определенное выше, имеет только обычные свойства среднего значения (например, если среднее значение равных чисел им равно), если $a_{1}+\cdots +a_{n}=1$. В общем случае вместо этого можно рассмотреть $[a]^{1/(a_{1}+\cdots +a_{n})}$, которое называется средним Мюрхеда .

Примеры

• Для a ) a -среднее — это просто обычное среднее арифметическое x 1 _{= (1, 0, ..., 0} , ..., x _n .
• Для a = (1/ n , ..., 1/ n ) a -среднее является средним геометрическим x 1 _, ..., x _n .
• Для a = ( x , 1 − x ) a -среднее является средним значением Хайнца .
• Среднее Мюрхеда для a = (−1, 0, ..., 0) является гармоническим средним .

Дважды стохастические матрицы

Основная статья: Двойная стохастическая матрица

Матрица n × n P размера является дважды стохастической , если и P , и ее транспонированная P ^Т являются стохастическими матрицами . Стохастическая матрица — это квадратная матрица неотрицательных вещественных элементов, в которой сумма элементов в каждом столбце равна 1. Таким образом, дважды стохастическая матрица — это квадратная матрица неотрицательных действительных элементов, в которой сумма элементов в каждой строке и сумма записей в каждом столбце равна 1.

Заявление

Неравенство Мюрхеда утверждает, что [ a ] ​​≤ [ b ] для всех x таких, что x _i > 0 для каждого i ∈ { 1, ..., n } тогда и только тогда, когда существует некоторая дважды стохастическая матрица P , для которой a = Pb .

Более того, в этом случае мы имеем [ a ] ​​= [ b ] тогда и только тогда, когда a = b или все x _i равны.

Последнее условие можно выразить несколькими эквивалентными способами; один из них приведен ниже.

В доказательстве используется тот факт, что каждая дважды стохастическая матрица представляет собой средневзвешенное значение матриц перестановок ( теорема Биркгофа-фон Неймана ).

Еще одно эквивалентное условие

Из-за симметрии суммы общность не теряется при сортировке показателей степени по убыванию:

$a_{1}\geq a_{2}\geq \cdots \geq a_{n}$

$b_{1}\geq b_{2}\geq \cdots \geq b_{n}.$

Тогда существование дважды стохастической матрицы P такой, что a = Pb, эквивалентно следующей системе неравенств:

${\begin{aligned}a_{1}&\leq b_{1}\\a_{1}+a_{2}&\leq b_{1}+b_{2}\\a_{1}+a_{2}+a_{3}&\leq b_{1}+b_{2}+b_{3}\\&\,\,\,\vdots \\a_{1}+\cdots +a_{n-1}&\leq b_{1}+\cdots +b_{n-1}\\a_{1}+\cdots +a_{n}&=b_{1}+\cdots +b_{n}.\end{aligned}}$

( Последнее — равенство; остальные — слабые неравенства.)

Последовательность $b_{1},\ldots ,b_{n}$ Говорят, что она мажорирует последовательность $a_{1},\ldots ,a_{n}$.

Обозначение симметричной суммы

Для сумм удобно использовать специальные обозначения. Успех в сокращении неравенства в этой форме означает, что единственным условием его проверки является проверка того, является ли одна последовательность показателей ( $\alpha _{1},\ldots ,\alpha _{n}$) мажорирует другой.

$\sum _{\text{sym}}x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n}}$

Эта запись требует разработки каждой перестановки, разработки выражения, состоящего из n ! мономы , например:

${\begin{aligned}\sum _{\text{sym}}x^{3}y^{2}z^{0}&=x^{3}y^{2}z^{0}+x^{3}z^{2}y^{0}+y^{3}x^{2}z^{0}+y^{3}z^{2}x^{0}+z^{3}x^{2}y^{0}+z^{3}y^{2}x^{0}\\&=x^{3}y^{2}+x^{3}z^{2}+y^{3}x^{2}+y^{3}z^{2}+z^{3}x^{2}+z^{3}y^{2}\end{aligned}}$

Примеры

Среднее арифметико-геометрическое неравенство

Основная статья: Неравенство средних арифметических и геометрических

Позволять

$a_{G}=\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)$

и

$a_{A}=(1,0,0,\ldots ,0).$

У нас есть

${\begin{aligned}a_{A1}=1&>a_{G1}={\frac {1}{n}},\\a_{A1}+a_{A2}=1&>a_{G1}+a_{G2}={\frac {2}{n}},\\&\,\,\,\vdots \\a_{A1}+\cdots +a_{An}&=a_{G1}+\cdots +a_{Gn}=1.\end{aligned}}$

Затем

[ а _А ] ≥ [ а _G ],

который

${\frac {1}{n!}}(x_{1}^{1}\cdot x_{2}^{0}\cdots x_{n}^{0}+\cdots +x_{1}^{0}\cdots x_{n}^{1})(n-1)!\geq {\frac {1}{n!}}(x_{1}\cdot \cdots \cdot x_{n})^{1/n}n!$

приводящее к неравенству.

Другие примеры

Мы стремимся доказать, что x ² + и ² ≥ 2 xy с использованием группировки (неравенство Мюрхеда). Преобразуем его в обозначениях симметричной суммы:

$\sum _{\mathrm {sym} }x^{2}y^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}.$

Последовательность (2, 0) мажорирует последовательность (1, 1), поэтому неравенство выполняется за счет группировки.

Аналогично можно доказать неравенство

$x^{3}+y^{3}+z^{3}\geq 3xyz$

записав его, используя обозначение симметричной суммы, как

$\sum _{\mathrm {sym} }x^{3}y^{0}z^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}z^{1},$

что то же самое, что

$2x^{3}+2y^{3}+2z^{3}\geq 6xyz.$

Поскольку последовательность (3, 0, 0) мажорирует последовательность (1, 1, 1), неравенство выполняется за счет группировки.

См. также

• Неравенство средних арифметических и геометрических
• Двойная стохастическая матрица
• Неравенство Маклорена
• Мономиальный симметричный полином
• Неравенства Ньютона

Ссылки

• Комбинаторная теория Джона Н. Гуиди, основанная на лекциях, прочитанных Джан-Карло Рота в 1998 году, Центр копировальных технологий Массачусетского технологического института, 2002 год.
• Киран Кедлая, A < B ( A меньше B ) , руководство по решению неравенств
• Теорема Мюрхеда в PlanetMath .
• Харди, GH; Литтлвуд, Дж. Э.; Полиа, Г. (1952), Неравенства, Кембриджская математическая библиотека (2-е изд.), Кембридж: Издательство Кембриджского университета, ISBN   0-521-05206-8 , МР 0046395 , Збл   0047.05302 , раздел 2.18, теорема 45.