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

Двічі стохастична матриця квадратна матриця з невід'ємними дійсними елементами, в якій усі її рядкові і стовпцеві суми дорівнюють 1, тобто:

.

Множина всіх двічі стохастичних матриць позначається через .

Теорема Біркгофа: множина усіх двічі стохастичних матриць утворює опуклий багатогранник, вершини якого матриці перестановки. Інакше кажучи, якщо , то , де  — матриці перестановки, а  — невід'ємні числа, [1].

Будь-яка двічі стохастична матриця порядку є опуклою лінійною комбінацією не більше ніж матриць перестановок[2].

Для і , таких, що

за всіх і
,

існує така двічі стохастична матриця , що [2].

Перманент двічі стохастичної -матриці не менший, ніж  гіпотеза ван дер Вардена,[3] доведена 1980 Г. П. Єгоричевим[4] і незалежно Д. Фалікманом[5] (роботу подано до публікації 1979 року); за ці результати обох учених відзначено 1982 року премією Фалкерсона.[3]

Див. також

Примітки

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

Література

  • Минк Х. Перманенты. М. : Мир, 1982. — 211 с.
  • Прасолов В. В. Задачи и теоремы линейной алгебры. М. : Наука, 1996. — 304 с. — ISBN 5-02-014727-3.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.