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

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

∀ j ∑ i a i j = 1 , ∀ i ∑ j a i j = 1 {displaystyle forall jsum _{i}a_{ij}=1,;forall isum _{j}a_{ij}=1} .

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

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

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

Для x 1 ⩾ x 2 ⩾ … ⩾ x n {displaystyle x_{1}geqslant x_{2}geqslant ldots geqslant x_{n}} и y 1 ⩾ y 2 ⩾ … ⩾ y n {displaystyle y_{1}geqslant y_{2}geqslant ldots geqslant y_{n}} , таких, что

x 1 + … + x k ⩽ y 1 + … + y k {displaystyle x_{1}+ldots +x_{k}leqslant y_{1}+ldots +y_{k}} при всех k < n {displaystyle k<n} и x 1 + … + x n = y 1 + … + y n {displaystyle x_{1}+ldots +x_{n}=y_{1}+ldots +y_{n}} ,

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

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