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

Двічі стохастична матриця — квадратна матриця ${\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 року премією Фалкерсона.

Див. також

• Стохастична матриця
• Багатогранник Біркгофа

Примітки

1. Задачи и теоремы линейной алгебры, 1996, с. 223.
2. Задачи и теоремы линейной алгебры, 1996, с. 225.
3. Минк, 1982, с. 211.
4. Егорычев Г. П.  Решение проблемы Ван дер Вардена для перманентов // ^[ru], препринт ИФСО-13М. — Красноярск, 1980. — 16 червня.
5. Фаликман Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы // . — 1981. — Т. 29, № 6 (16 червня). — С. 931—938. з джерела 23 квітня 2021. Процитовано 23 квітня 2021.

Література

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