Дважды стохастическая матрица

Дважды стохастическая матрица — квадратная матрица с неотрицательными вещественными элементами, в которой все её строчные и столбцовые суммы равны 1, то есть:

.

Множество всех дважды стохастических матриц обозначается через .

Теорема Биркгофа: множество всех дважды стохастических матриц образует выпуклый многогранник, вершины которого — матрицы перестановки. Иначе говоря, если , то , где  — матрицы перестановки, а  — неотрицательные числа, [1].

Любая дважды стохастическая матрица порядка является выпуклой линейной комбинацией не более чем матриц перестановок[2].

Для и , таких, что

при всех и
,

существует такая дважды стохастическая матрица , что [2].

Перманент дважды стохастической -матрицы не менее, чем  — гипотеза ван дер Вардена,[3] доказанная в 1980 году Г. П. Егорычевым[4] и независимо Д. Фаликманом[5] (работа представлена к публикации в 1979 году); за эти результаты оба учёных удостоены в 1982 году премии Фалкерсона. [3]

Примечания

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

Литература

править
  • Минк Х. Перманенты. — М.: Мир, 1982. — 211 с.
  • Прасолов В. В. Задачи и теоремы линейной алгебры. — М.: Наука, 1996. — 304 с. — ISBN 5-02-014727-3.