Двічі стохастична матриця

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