Дважды стохастическая матрица

Дважды стохастическая матрица — квадратная матрица ${\displaystyle A=(a_{ij})}$ с неотрицательными вещественными элементами, в которой все её строчные и столбцовые суммы равны 1, то есть:

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

Множество всех дважды стохастических матриц обозначается через ${\displaystyle \Omega _{n}}$.

Теорема Биркгофа: множество ${\displaystyle \Omega _{n}}$ всех дважды стохастических матриц образует выпуклый многогранник, вершины которого — матрицы перестановки. Иначе говоря, если ${\displaystyle A\in \Omega _{n}}$, то ${\displaystyle A=\sum _{j=1}^{s}\theta _{j}P_{j}}$, где ${\displaystyle P_{1},...,P_{s}}$ — матрицы перестановки, а ${\displaystyle \theta _{1},...,\theta _{s}}$ — неотрицательные числа, ${\displaystyle \sum _{j=1}^{s}\theta _{j}=1}$^[1].

Любая дважды стохастическая матрица ${\displaystyle S}$ порядка ${\displaystyle n}$ является выпуклой линейной комбинацией не более чем ${\displaystyle n^{2}-2n+2}$ матриц перестановок^[2].

Для ${\displaystyle x_{1}\geqslant x_{2}\geqslant \ldots \geqslant x_{n}}$ и ${\displaystyle y_{1}\geqslant y_{2}\geqslant \ldots \geqslant y_{n}}$, таких, что

${\displaystyle x_{1}+\ldots +x_{k}\leqslant y_{1}+\ldots +y_{k}}$ при всех ${\displaystyle k<n}$ и

${\displaystyle x_{1}+\ldots +x_{n}=y_{1}+\ldots +y_{n}}$,

существует такая дважды стохастическая матрица ${\displaystyle S}$, что ${\displaystyle Sy=x}$^[2].

Перманент дважды стохастической ${\displaystyle n}$-матрицы не менее, чем ${\displaystyle n!/n^{n}}$ — гипотеза ван дер Вардена,^[3] доказанная в 1980 году Г. П. Егорычевым^[4] и независимо Д. Фаликманом^[5] (работа представлена к публикации в 1979 году); за эти результаты оба учёных удостоены в 1982 году премии Фалкерсона. ^[3]

Примечания

1. Задачи и теоремы линейной алгебры, 1996, с. 223.
2. Задачи и теоремы линейной алгебры, 1996, с. 225.
3. Минк, 1982, с. 211.
4. Егорычев Г. П.  Решение проблемы Ван дер Вардена для перманентов // Институт физики им. Л. В. Киренского СО АН СССР, препринт ИФСО-13М. — Красноярск, 1980.
5. Фаликман Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы // Математические заметки. — 1981. — Т. 29, № 6. — С. 931—938. Архивировано 23 апреля 2021 года.

Литература

• Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.
• Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996. — 304 с. — ISBN 5-02-014727-3.