Двойная стохастическая матрица - Doubly stochastic matrix

В математика, особенно в вероятность и комбинаторика, а дважды стохастическая матрица (также называемый бистохастическая матрица), это квадратная матрица ${\displaystyle A=(a_{ij})}$ неотрицательных действительные числа, сумма каждой строки и столбца которого равна 1,^[1] т.е.

${\displaystyle \sum _{i}a_{ij}=\sum _{j}a_{ij}=1}$,

Таким образом, дважды стохастическая матрица остается стохастический и правый стохастик.^[1][2]

Действительно, любая матрица, которая является как левой, так и правой стохастической, должна быть квадрат: если сумма каждой строки равна единице, то сумма всех элементов в матрице должна быть равна количеству строк, и, поскольку то же самое верно для столбцов, количество строк и столбцов должно быть равным.^[1]

Многогранник Биркгофа

Основная статья: Многогранник Биркгофа

Класс ${\displaystyle n\times n}$ дважды стохастические матрицы - это выпуклый многогранник известный как Многогранник Биркгофа ${\displaystyle B_{n}}$. Используя элементы матрицы как Декартовы координаты, он находится в ${\displaystyle (n-1)^{2}}$-мерное аффинное подпространство ${\displaystyle n^{2}}$-размерный Евклидово пространство определяется ${\displaystyle 2n-1}$ независимые линейные ограничения, определяющие, что сумма строки и столбца равна единице. (Есть ${\displaystyle 2n-1}$ ограничения, а не ${\displaystyle 2n}$ поскольку одно из этих ограничений является зависимым, так как сумма сумм строк должна равняться сумме сумм столбцов.) Более того, все записи должны быть неотрицательными и меньше или равными единице.

Теорема Биркгофа – фон Неймана

В Теорема Биркгофа – фон Неймана утверждает, что многогранник ${\displaystyle B_{n}}$ это выпуклый корпус из набора ${\displaystyle n\times n}$ матрицы перестановок, и, кроме того, вершины из ${\displaystyle B_{n}}$ в точности матрицы перестановок. Другими словами, если ${\displaystyle A}$ является дважды стохастической матрицей, то существуют ${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$ и матрицы перестановок ${\displaystyle P_{1},\ldots ,P_{k}}$ такой, что

${\displaystyle A=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

Это представление известно как Разложение Биркгофа – фон Неймана, и в целом он может быть не уникальным. К Теорема Каратеодори, однако существует разложение с не более чем ${\displaystyle (n-1)^{2}+1=n^{2}-2n+2}$ сроки, т.е. с^[3]

${\displaystyle k\leq n^{2}-2n+2.}$

Другими словами, пока существует разложение с ${\displaystyle n!}$ перестановочных матриц существует по крайней мере одно конструктивное разложение с не более чем ${\displaystyle (n-1)^{2}+1}$ матрицы. Такое разложение можно найти за полиномиальное время с помощью Алгоритм Биркгофа. Это часто описывается как вещественное обобщение Теорема Кёнига, где соответствие устанавливается через матрицы смежности графов.

Другие свойства

• Произведение двух дважды стохастических матриц дважды стохастично. Однако матрица, обратная неособой дважды стохастической матрице, не обязательно должна быть дважды стохастической (действительно, обратная матрица является дважды стохастической, если и только если она имеет неотрицательные элементы).
• Стационарное распределение неприводимого апериодического конечного Цепь Маркова равномерно тогда и только тогда, когда его переходная матрица двустохастична.
• Теорема Синкхорна утверждает, что любая матрица со строго положительными элементами может быть сделана дважды стохастической путем предварительного и последующего умножения на диагональные матрицы.
• За ${\displaystyle n=2}$, все бистохастические матрицы неистохастический и ортостохастический, но для большего ${\displaystyle n}$ это не тот случай.
• Ван дер Варден предположил, что минимум постоянный среди всего п × п дважды стохастические матрицы ${\displaystyle n!/n^{n}}$, достигается матрицей, все элементы которой равны ${\displaystyle 1/n}$.^[4] Доказательства этой гипотезы были опубликованы в 1980 г. Б. Гиресом.^[5] и в 1981 г. Г. П. Егорычевым.^[6] и Д. И. Фаликман;^[7] за эту работу Егорычев и Фаликман выиграли Премия Фулкерсона в 1982 г.^[8]

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

• Стохастическая матрица
• Унистохастическая матрица

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

1. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 9–11. ISBN  978-1-119-38755-8.
2. Маршал, Олкин (1979). Неравенства: теория мажоризации и ее приложения. стр.8. ISBN  978-0-12-473750-1.
3. Marcus, M .; Ри, Р. (1959). «Диагонали дважды стохастических матриц». Ежеквартальный журнал математики. 10 (1): 296–302. Дои:10.1093 / qmath / 10.1.296.
4. ван дер Варден, Б. Л. (1926), "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35: 117.
5. Gyires, B. (1980), "Общий источник нескольких неравенств, касающихся дважды стохастических матриц", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis, 27 (3–4): 291–304, МИСТЕР  0604006.
6. Егорычев, Г. П. (1980), Решение проблемы ван-дер-вардена для перманентов Красноярск: Акад. АН СССР Сиб. Отдел. Inst. Физ., Стр. 12, МИСТЕР  0602332. Егорычев, Г. П. (1981), "Доказательство гипотезы Ван дер Вардена для перманентов", Академия Наук СССР (на русском), 22 (6): 65–71, 225, МИСТЕР  0638007. Егорычев, Г. П. (1981), "Решение проблемы Ван дер Вардена для перманентов", Успехи в математике, 42 (3): 299–305, Дои:10.1016 / 0001-8708 (81) 90044-Х, МИСТЕР  0642395.
7. Фаликман, Д. И. (1981), "Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы", Академия Наук Союза ССР (на русском), 29 (6): 931–938, 957, МИСТЕР  0625097.
8. Премия Фулкерсона, Mathematical Optimization Society, дата обращения 19 августа 2012.

• Бруальди, Ричард А. (2006). Комбинаторные матричные классы. Энциклопедия математики и ее приложений. 108. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-86565-4. Zbl  1106.05001.

внешняя ссылка

• Страница PlanetMath по теореме Биркгофа – фон Неймана
• Страница PlanetMath о доказательстве теоремы Биркгофа – фон Неймана