Введение

Квадратная матрица. В математике, особенно в теории вероятностей и комбинаторике, двойно-стохастическая матрица (также называемая бистохастической матрицей) — это квадратная матрица неотрицательных вещественных чисел, у которой сумма элементов в каждой строке и каждом столбце равна 1, то есть:

Таким образом, двойно-стохастическая матрица является одновременно левостохастической и правостохастической. Действительно, любая матрица, являющаяся одновременно левостохастической и правостохастической, должна быть квадратной: если сумма элементов в каждой строке равна 1, то сумма всех элементов матрицы должна быть равна числу строк, и поскольку то же самое верно для столбцов, число строк и столбцов должно быть одинаковым. Утверждается, что политоп является выпуклой оболочкой множества матриц перестановок, и что вершины этого политопа — это именно матрицы перестановок. Иными словами, если X — двойно-стохастическая матрица, то существуют вещественные числа и матрицы перестановок P такие, что:

(Такое разложение X известно как "выпуклая комбинация".) Ниже приведено доказательство теоремы, основанное на теореме Холла о браке. Это представление известно как разложение Биркгоффа — фон Неймана и может быть не единственным. Оно часто описывается как вещественное обобщение теоремы Кёнига, где соответствие устанавливается через матрицы смежности графов.

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

Произведение двух двукратно стохастических матриц является двукратно стохастическим. Однако обратная невырожденной двукратно стохастической матрицы не обязана быть двукратно стохастической (фактически, обратная двукратно стохастична тогда и только тогда, когда все её элементы неотрицательны). Стационарное распределение неприводимой апериодической конечной цепи Маркова является равномерным тогда и только тогда, когда её матрица переходов двукратно стохастична. Теорема Синкхорна утверждает, что любую матрицу со строго положительными элементами можно сделать двукратно стохастической, умножив её слева и справа на диагональные матрицы. Для , все бистохастические матрицы являются унистохастическими и ортостохастическими, но для больших это не так. Гипотеза Ван дер Вардена гласит, что минимальный перманент среди всех двукратно стохастических матриц размера n × n равен , достигаемый матрицей, в которой все элементы равны . Доказательства этой гипотезы были опубликованы в 1980 году Б. Джиресом и в 1981 году Г. П. Егоричевым и Д. И. Фаликманом; за эту работу Егоричев и Фаликман были удостоены премии Фулкерсона в 1982 году.