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

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

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

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

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

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

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

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

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

существует такая дважды стохастическая матрица $S$, что $Sy=x$.

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

Литература

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