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

В математике , особенно в теории вероятности и комбинаторике , дважды стохастическая матрица (также называемая бистохастической матрицей ) представляет собой квадратную матрицу $X=(x_{ij})$ неотрицательных действительных чисел , каждая из строк и столбцов которых в сумме равна 1, т. е.

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

Таким образом, дважды стохастическая матрица является одновременно левостохастической и правостохастической.

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

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

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

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

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

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

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

(Такое разложение X известно как «выпуклая комбинация».) Доказательство теоремы, основанное на теореме Холла о браке, приведено ниже .

Это представление известно как разложение Биркгофа – фон Неймана и может быть неединственным. Его часто описывают как вещественное обобщение теоремы Кенига , где соответствие устанавливается через матрицы смежности графов.

Другие объекты недвижимости

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

Доказательство теоремы Биркгофа–фон Неймана.

Пусть X — дважды стохастическая матрица. Затем мы покажем, что существует матрица перестановок P такая, что x _ij ≠ 0 всякий раз, когда p _ij ≠ 0. Таким образом, если мы позволим λ быть наименьшим x _ij, соответствующим ненулевому p _ij , разница X – λ P будет равна скаляр, кратный дважды стохастической матрице, и будет иметь как минимум на одну нулевую ячейку больше, чем X . Соответственно, мы можем последовательно уменьшать количество ненулевых ячеек в X , удаляя скалярные кратные матриц перестановок, пока не достигнем нулевой матрицы, после чего мы построим выпуклую комбинацию матриц перестановок, равную исходному X .

Например, если $X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}$ затем $P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}$, $\lambda ={\frac {2}{12}}$, и $X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}$.

Доказательство. Постройте двудольный граф , в котором строки X перечислены в одной части, а столбцы — в другой, и в котором строка i соединена со столбцом j тогда и только тогда, когда x _ij ≠ 0. Пусть A — любой набор строк, и определите A ' как набор столбцов, соединенных со строками в A на графике. Мы хотим выразить размеры | А | и | А' | из двух наборов с точки зрения x _ij .

Для каждого i в A сумма по j в A' для x _ij равна 1, поскольку все столбцы j , для которых x _ij ≠ 0, включены в A ' , а X является вдвойне стохастическим; отсюда | А | является суммой по i ∈ A , j ∈ A ' x ij _. всем

Тем временем | А ' | является суммой по всем i (независимо от того, входит ли оно в A ) и по всем j в A ' из x _ij ; и это ≥ соответствующей суммы, в которой i ограничены строками в A . Следовательно | А ' | ≥ | А |.

Отсюда следует, что условия теоремы о браке Холла удовлетворены и, следовательно, мы можем найти набор ребер в графе, которые соединяют каждую строку в X ровно с одним (отдельным) столбцом. Эти ребра определяют матрицу перестановок, ненулевые ячейки которой соответствуют ненулевым ячейкам в X .

Обобщения

Существует простое обобщение на матрицы с большим количеством столбцов и строк, такие что i ^й сумма строк равна r _i (натуральное целое число), суммы столбцов равны 1, все ячейки неотрицательны (сумма сумм строк равна количеству столбцов). Любая матрица в этой форме может быть выражена как выпуклая комбинация матриц одинаковой формы, состоящая из нулей и единиц. Доказательство состоит в замене i ^й строку исходной матрицы на отдельные _строки , каждая из которых равна исходной строке, разделенной на r _i ; применить к полученной квадратной матрице теорему Биркгофа; и в конце аддитивно объединить строки r _i в одну i ^й ряд.

Таким же образом можно реплицировать как столбцы, так и строки, но результат рекомбинации не обязательно ограничивается нулями и единицами. Другое обобщение (со значительно более сложным доказательством) было предложено Р.М. Кароном и др.

См. также

• Стохастическая матрица
• Унистохастическая матрица
• Алгоритм Биркгофа

Ссылки

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

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

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