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

Дважды стохастическая матрица — квадратная матрица ${\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]