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

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

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

а-иметь в виду

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

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

определить "а-иметь в виду" [а] положительных действительных чисел Икс₁, ..., Икс_п к

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

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

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

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

куда л это количество различных элементов в а, и k₁, ..., k_л их множественность.

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

Примеры

• За а = (1, 0, ..., 0), то а-средство просто обычное среднее арифметическое из Икс₁, ..., Икс_п.
• За а = (1/п, ..., 1/п), а-среднее это среднее геометрическое из Икс₁, ..., Икс_п.
• За а = (Икс, 1-Икс), а-среднее Хайнц означает.

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

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

An п × п матрица п является дважды стохастический именно если оба п и его транспонировать п^Т находятся стохастические матрицы. А стохастическая матрица представляет собой квадратную матрицу неотрицательных вещественных элементов, в которой сумма элементов в каждом столбце равна 1. Таким образом, дважды стохастическая матрица - это квадратная матрица неотрицательных вещественных элементов, в которой сумма элементов в каждой строке и сумма элементов записей в каждом столбце - 1.

Заявление

Неравенство Мюрхеда утверждает, что [а] ≤ [б] для всех Икс такой, что Икс_я > 0 для каждого я ∈ { 1, ..., п } тогда и только тогда, когда существует некоторая дважды стохастическая матрица п для которого а = Pb.

Кроме того, в этом случае мы имеем [а] = [б] если и только если а = б или все Икс_я равны.

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

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

Другое эквивалентное условие

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

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

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

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

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

(The последний один - равенство; остальные - слабые неравенства.)

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

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

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

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

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

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

Примеры

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

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

Позволять

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

и

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

У нас есть

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

потом

[а_А] ≥ [а_грамм],

который

${\displaystyle {\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!}$

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

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

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

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

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

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

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

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

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

который совпадает с

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

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

Смотрите также

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

Примечания

1. Буллен, П. С. Справочник средств и их неравенства. Kluwer Academic Publishers Group, Дордрехт, 2003. ISBN  1-4020-1522-4

Рекомендации

• Комбинаторная теория Джона Н. Гуиди на основе лекций, прочитанных Джан-Карло Рота в 1998, MIT Copy Technology Center, 2002.
• Киран Кедлая, А < B (А меньше, чем B), руководство по устранению неравенства
• Теорема Мюрхеда в PlanetMath.
• Харди, G.H .; Littlewood, J.E .; Полиа, Г. (1952), Неравенства, Кембриджская математическая библиотека (2-е изд.), Кембридж: Cambridge University Press, ISBN  0-521-05206-8, МИСТЕР0046395, Zbl  0047.05302, Раздел 2.18, теорема 45.