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

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

\sum _{i}a_{ij}=\sum _{j}a_{ij}=1

,

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

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

Многогранник Биркгофа [ править ]

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

Теорема Биркгофа – фон Неймана [ править ]

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

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

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

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

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

Другие свойства [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

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

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

Внешние ссылки [ править ]

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

[:0-1] Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: John Wiley & Sons. С. 9–11. ISBN 978-1-119-38755-8.

[2] Маршал, Олкин (1979). Неравенства: теория мажоризации и ее приложения . С. 8 . ISBN 978-0-12-473750-1.

[3] Маркус, М .; Ри, Р. (1959). «Диагонали дважды стохастических матриц». Ежеквартальный журнал математики . 10 (1): 296–302. DOI : 10.1093 / qmath / 10.1.296 .

[4] van der Waerden, BL (1926), «Aufgabe 45», Jber. Deutsch. Math.-Verein. , 35 : 117.

[5] Gyires, B. (1980), "Общий источник нескольких неравенств, касающихся дважды стохастических матриц", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis , 27 (3–4): 291–304, MR 0604006 .

[6] Egoryčev, GP (1980), Reshenie проблемы- ван дер-Vardena Dlya permanentov (на русском языке ), Красноярск: Изд. АН СССР Сиб. Отдел. Inst. Физ., Стр. 12, Руководство MR 0602332 . Егорычев, Г.П. (1981), «Доказательство гипотезы Ван дер Вардена для перманентов», Академия Наук СССР , 22 (6): 65–71, 225, MR 0638007. . Егорычев, Г.П. (1981), "Решение проблемы Ван дер Вардена для перманентов", Успехи в математике , 42 (3): 299–305, DOI : 10.1016 / 0001-8708 (81) 90044-X , MR 0642395 .

[7] Фаликман, Д.И. (1981), «Доказательство гипотезы Ван дер Вардена о перманенте двустохастической матрицы», Академия наук Союза ССР , 29 (6): 931–938, 957, MR 0625097 .

[8] Фулкерсон премии , Математическая оптимизация общества, извлекаться 2012-08-19.

[1]