Двічі стохастична матриця — квадратна матриця з невід'ємними дійсними елементами, в якій усі її рядкові і стовпцеві суми дорівнюють 1, тобто:
.
Множина всіх двічі стохастичних матриць позначається через .
Теорема Біркгофа: множина усіх двічі стохастичних матриць утворює опуклий багатогранник, вершини якого — матриці перестановки. Інакше кажучи, якщо , то , де — матриці перестановки, а — невід'ємні числа, .
Будь-яка двічі стохастична матриця порядку є опуклою лінійною комбінацією не більше ніж матриць перестановок.
Для і , таких, що
за всіх і ,
існує така двічі стохастична матриця , що .
Перманент двічі стохастичної -матриці не менший, ніж — гіпотеза ван дер Вардена, доведена 1980 Г. П. Єгоричевим і незалежно Д. Фалікманом (роботу подано до публікації 1979 року); за ці результати обох учених відзначено 1982 року премією Фалкерсона.
Див. також Стохастична матриця Багатогранник Біркгофа
Примітки
Джерела