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

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