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

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

$\mathrm{\forall }j\sum _i{a}_{ij}=1,\mathrm{\forall }i\sum _j{a}_{ij}=1$.

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

Теорема Биркгофа: множество ${\mathrm{\Omega }}_n$ всех дважды стохастических матриц образует выпуклый многогранник, вершины которого — матрицы перестановки. Иначе говоря, если $A\in {\mathrm{\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$Шаблон:Sfn.

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

Для $x_1⩾x_2⩾\dots ⩾x_n$ и $y_1⩾y_2⩾\dots ⩾y_n$, таких, что

$x_1+\dots +x_k⩽y_1+\dots +y_k$ при всех $k<n$ и

$x_1+\dots +x_n=y_1+\dots +y_n$,

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга