Мажоризация

Предварительный заказ на векторы действительных чисел

В математике мажорирование — это предварительный порядок векторов действительных чисел . Для двух таких векторов, мы говорим, что слабо мажорирует (или доминирует) снизу , обычно обозначается , когда ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {x} \succ _{w}\mathbf {y} ,}$

${\displaystyle \sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }}$для всех , ${\displaystyle k=1,\,\dots ,\,n}$

где обозначает ^{наибольший} элемент . Если далее удовлетворяет , мы говорим, что мажорирует (или доминирует) , обычно обозначается . Мажорирование является частичным порядком для векторов, элементы которых не убывают, но только предварительным порядком для общих векторов, поскольку мажорирование не зависит от порядка элементов в векторах, например, утверждение просто эквивалентно . ${\displaystyle x_{i}^{\downarrow }}$ ${\displaystyle i}$ ${\displaystyle x}$ ${\displaystyle \mathbf {x} ,\mathbf {y} }$ ${\displaystyle \sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ ${\displaystyle (1,2)\prec (0,3)}$ ${\displaystyle (2,1)\prec (3,0)}$

Мажорирование также иногда относится к упорядочению по записям, например, действительная функция f мажорирует действительную функцию g , когда для всех в области, или другие технические определения, такие как меры мажорирования в теории вероятностей . ^[1] ${\displaystyle f(x)\geq g(x)}$ ${\displaystyle x}$

Эквивалентные условия

Геометрическое определение

Рисунок 1. Пример 2D мажорирования

Для нас есть тогда и только тогда, когда находится в выпуклой оболочке всех векторов, полученных перестановкой координат . Это эквивалентно утверждению, что для некоторой дважды стохастической матрицы . ^{[2] : Теор. 2.1} В частности, может быть записана как выпуклая комбинация перестановок . ^[3] ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n},}$ ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {x} =\mathbf {D} \mathbf {y} }$ ${\displaystyle \mathbf {D} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle n}$ ${\displaystyle \mathbf {y} }$

На рисунке 1 показана выпуклая оболочка в 2D для вектора . Обратите внимание, что центр выпуклой оболочки, который в данном случае является интервалом, является вектором . Это «наименьший» вектор, удовлетворяющий данному вектору . На рисунке 2 показана выпуклая оболочка в 3D. Центр выпуклой оболочки, который в данном случае является двумерным многоугольником, является «наименьшим» вектором, удовлетворяющим данному вектору . ${\displaystyle \mathbf {y} =(3,\,1)}$ ${\displaystyle \mathbf {x} =(2,\,2)}$ ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ ${\displaystyle \mathbf {y} }$

Рисунок 2. Пример 3D-мажорирования

Другие определения

Каждое из следующих утверждений верно тогда и только тогда, когда . ${\displaystyle \mathbf {x} \succ \mathbf {y} }$

• Из мы можем получить с помощью конечной последовательности «операций Робин Гуда», где мы заменяем два элемента и на и , соответственно, для некоторых . ^{[2] : 11} ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}<x_{i}}$ ${\displaystyle x_{i}-\varepsilon }$ ${\displaystyle x_{j}+\varepsilon }$ ${\displaystyle \varepsilon \in (0,x_{i}-x_{j})}$
• Для каждой выпуклой функции , . ^{[2] : Теор. 2.9} ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$ ${\displaystyle \sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})}$
  • На самом деле, достаточно особого случая: и для каждого t , . ^[4] ${\displaystyle \sum _{i}{x_{i}}=\sum _{i}{y_{i}}}$ ${\displaystyle \sum _{i=1}^{d}\max(0,x_{i}-t)\geq \sum _{i=1}^{d}\max(0,y_{i}-t)}$
• Для каждого , . ^{[5] : Упражнение 12.17} ${\displaystyle t\in \mathbb {R} }$ ${\displaystyle \sum _{j=1}^{d}|x_{j}-t|\geq \sum _{j=1}^{d}|y_{j}-t|}$

Примеры

Среди неотрицательных векторов с тремя компонентами и перестановками его мажорируют все другие векторы, такие что . Например, . Аналогично, мажорируется всеми другими такими векторами, поэтому . ${\displaystyle (1,0,0)}$ ${\displaystyle (p_{1},p_{2},p_{3})}$ ${\displaystyle p_{1}+p_{2}+p_{3}=1}$ ${\displaystyle (1,0,0)\succ (1/2,0,1/2)}$ ${\displaystyle (1/3,1/3,1/3)}$ ${\displaystyle (1/2,0,1/2)\succ (1/3,1/3,1/3)}$

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

Выпуклость Шура

Говорят, что функция является выпуклой по Шуру, когда подразумевает . Следовательно, выпуклые по Шуру функции переводят порядок векторов в стандартный порядок в . Аналогично, является ли вогнутой по Шуру, когда подразумевает ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ ${\displaystyle f(\mathbf {x} )\geq f(\mathbf {y} )}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ ${\displaystyle f(\mathbf {x} )\leq f(\mathbf {y} ).}$

Примером функции Шура-выпуклой является функция max, . Выпуклые функции Шура обязательно симметричны, так что элементы ее аргумента можно переключать без изменения значения функции. Следовательно, линейные функции, которые являются выпуклыми, не являются функциями Шура-выпуклыми, если они не симметричны. Если функция симметрична и выпукла, то она является функцией Шура-выпуклой. ${\displaystyle \max(\mathbf {x} )=x_{1}^{\downarrow }}$

Обобщения

Мажорирование можно обобщить до порядка Лоренца , частичного порядка функций распределения . Например, распределение богатства больше другого, если его кривая Лоренца лежит ниже другого. Таким образом, распределение богатства больше Лоренца имеет более высокий коэффициент Джини и большее неравенство доходов . ^[6]

Предварительный порядок мажорирования может быть естественным образом расширен до матриц плотности в контексте квантовой информации . ^{[5] [7]} В частности, именно тогда, когда (где обозначает спектр состояния ). ${\displaystyle \rho \succ \rho '}$ ${\displaystyle \mathrm {spec} [\rho ]\succ \mathrm {spec} [\rho ']}$ ${\displaystyle \mathrm {spec} }$

Аналогично можно сказать, что эрмитов оператор , , мажорирует другой, , если набор собственных значений мажорирует набор собственных значений . ${\displaystyle \mathbf {H} }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {H} }$ ${\displaystyle \mathbf {M} }$

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

• Неравенство Мьюирхеда
• Неравенство Караматы
• Шур-выпуклая функция
• Теорема Шура–Хорна, связывающая диагональные элементы матрицы с ее собственными значениями.
• Для положительных целых чисел слабое мажорирование называется порядком доминирования .
• порядок лексимин

Примечания

1. Талагранд, Мишель (1996-07-01). "Мажорирование мер: общая цепочка". Анналы вероятности . 24 (3). doi : 10.1214/aop/1065725175 . ISSN  0091-1798.
2. Барри К. Арнольд. "Мажоризация и порядок Лоренца: краткое введение". Springer-Verlag Lecture Notes in Statistics, т. 43, 1987.
3. Синчжи, Чжань (2003). «Точная теорема Радо для мажораций». The American Mathematical Monthly . 110 (2): 152–153. doi :10.2307/3647776. JSTOR  3647776.
4. 3 июля 2005 г., сообщение от Fleeting_guest в теме «Неравенство Карамата», форумы сообщества AoPS . Архивировано 11 ноября 2020 г.
5. Nielsen, Michael A. ; Chuang, Isaac L. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC  844974180.
6. Маршалл, Альберт В. (2011). "14, 15". Неравенства: теория мажорирования и ее приложения. Ингрэм Олкин, Барри К. Арнольд (2-е изд.). Нью-Йорк: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1. OCLC  694574026.
7. Wehrl, Alfred (1 апреля 1978 г.). «Общие свойства энтропии». Reviews of Modern Physics . 50 (2): 221–260. Bibcode : 1978RvMP...50..221W. doi : 10.1103/RevModPhys.50.221.

Ссылки

• Дж. Карамата. «Sur une inegalite относительно выпуклых функций». Опубл. Математика. унив. Белград  1, 145–158, 1932.
• GH Hardy, JE Littlewood и G. Pólya, Неравенства , 2-е издание, 1952, Cambridge University Press, Лондон.
• Неравенства: теория мажорирования и ее приложения Альберт В. Маршалл, Ингрэм Олкин , Барри Арнольд, Второе издание. Springer Series in Statistics. Springer, Нью-Йорк, 2011. ISBN 978-0-387-40087-7 
• Посвящение книге Маршалла и Олкина «Неравенства: теория мажорирования и ее приложения»
• Матричный анализ (1996) Раджендра Бхатия, Springer, ISBN 978-0-387-94846-1 
• Темы матричного анализа (1994) Роджер А. Хорн и Чарльз Р. Джонсон, Cambridge University Press, ISBN 978-0-521-46713-1 
• Мажорирование и матричные монотонные функции в беспроводной связи (2007) Эдуард Йорсвик и Хольгер Боше, Now Publishers, ISBN 978-1-60198-040-3 
• Мастер-класс Коши-Шварца (2004) Дж. Майкл Стил, Cambridge University Press, ISBN 978-0-521-54677-5 

Внешние ссылки

• Специальность MathWorld
• Специальность PlanetMath

Программное обеспечение

• Код OCTAVE / MATLAB для проверки мажорирования