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

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

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

Примечания

Литература

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