Двічі стохастична матриця
Двічі стохастична матриця — квадратна матриця з невід'ємними дійсними елементами, в якій усі її рядкові і стовпцеві суми дорівнюють 1, тобто:
- .
Множина всіх двічі стохастичних матриць позначається через .
Теорема Біркгофа: множина усіх двічі стохастичних матриць утворює опуклий багатогранник, вершини якого — матриці перестановки. Інакше кажучи, якщо , то , де — матриці перестановки, а — невід'ємні числа, [1].
Будь-яка двічі стохастична матриця порядку є опуклою лінійною комбінацією не більше ніж матриць перестановок[2].
Для і , таких, що
- за всіх і
- ,
існує така двічі стохастична матриця , що [2].
Перманент двічі стохастичної -матриці не менший, ніж — гіпотеза ван дер Вардена,[3] доведена 1980 Г. П. Єгоричевим[4] і незалежно Д. Фалікманом[5] (роботу подано до публікації 1979 року); за ці результати обох учених відзначено 1982 року премією Фалкерсона.[3]
Див. також
ред.Примітки
ред.- ↑ Задачи и теоремы линейной алгебры, 1996, с. 223.
- ↑ а б Задачи и теоремы линейной алгебры, 1996, с. 225.
- ↑ а б Минк, 1982, с. 211.
- ↑ Егорычев Г. П. Решение проблемы Ван дер Вардена для перманентов // Институт физики им. Л. В. Киренского СО АН СССР[ru], препринт ИФСО-13М. — Красноярск, 1980. — 28 серпня.
- ↑ Фаликман Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы // Математические заметки. — 1981. — Т. 29, № 6 (28 серпня). — С. 931—938. Архівовано з джерела 23 квітня 2021. Процитовано 23 квітня 2021.
Література
ред.- Минк Х. Перманенты. — М. : Мир, 1982. — 211 с.
- Прасолов В. В. Задачи и теоремы линейной алгебры. — М. : Наука, 1996. — 304 с. — ISBN 5-02-014727-3.