Мажорирование

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

\sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }

для всех

k=1,\,\dots ,\,n

,

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Обобщения

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

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

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

См. также

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

Примечания

^ Талагран, Мишель (1 июля 1996 г.). «Мажорирующие меры: родовая цепочка» . Анналы вероятности . 24 (3). дои : 10.1214/aop/1065725175 . ISSN 0091-1798 .
^ Перейти обратно: ^а ^б ^с Барри С. Арнольд. «Майоризация и порядок Лоренца: краткое введение». Конспекты лекций Springer-Verlag по статистике, том. 43, 1987.
^ Синчжи, Чжан (2003). «Точная теорема Радо для мажорирования». Американский математический ежемесячник . 110 (2): 152–153. дои : 10.2307/3647776 . JSTOR 3647776 .
↑ Сообщение отfleting_guest от 3 июля 2005 г. в теме «Неравенство Караматы» , AoPS форумы сообщества . Архивировано 11 ноября 2020 г.
^ Перейти обратно: ^а ^б Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3 . OCLC 844974180 .
^ Маршалл, Альберт В. (2011). «14, 15». Неравенства: теория мажорирования и ее приложения . Ингрэм Олкин, Барри К. Арнольд (2-е изд.). Нью-Йорк: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1 . OCLC 694574026 .
^ Верль, Альфред (1 апреля 1978 г.). «Общие свойства энтропии» . Обзоры современной физики . 50 (2): 221–260. Бибкод : 1978РвМП...50..221Вт . дои : 10.1103/RevModPhys.50.221 .

Ссылки

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

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

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

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

[1] Талагран, Мишель (1 июля 1996 г.). «Мажорирующие меры: родовая цепочка» . Анналы вероятности . 24 (3). дои : 10.1214/aop/1065725175 . ISSN 0091-1798 .

[Arnold-2] Перейти обратно: ^а ^б ^с Барри С. Арнольд. «Майоризация и порядок Лоренца: краткое введение». Конспекты лекций Springer-Verlag по статистике, том. 43, 1987.

[Zhan-3] Синчжи, Чжан (2003). «Точная теорема Радо для мажорирования». Американский математический ежемесячник . 110 (2): 152–153. дои : 10.2307/3647776 . JSTOR 3647776 .

[4] Сообщение отfleting_guest от 3 июля 2005 г. в теме «Неравенство Караматы» , AoPS форумы сообщества . Архивировано 11 ноября 2020 г.

[NielsenChuang-5] Перейти обратно: ^а ^б Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. 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] Верль, Альфред (1 апреля 1978 г.). «Общие свойства энтропии» . Обзоры современной физики . 50 (2): 221–260. Бибкод : 1978РвМП...50..221Вт . дои : 10.1103/RevModPhys.50.221 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]