Унимодулярная матрица

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Унимодул́ярная м́атрица — квадратная матрица с целыми коэффициентами, определитель которой равен +1 или -1. Это в точности те невырожденные матрицы A, для которых уравнение Ax = b имеет целочисленное решение для любого целочисленного вектора b.

Свойства[править | править исходный текст]

Унимодулярные матрицы образуют группу по умножению, т.е. следующие матрицы являются унимодулярными:

Вполне унимодулярная матрица[править | править исходный текст]

Прямоугольная матрица называется вполне унимодулярной (или абсолютно, или тотально унимодулярной), если все её миноры принимают значения из множества {-1, 0, +1}. Иными словами, любая её невырожденная квадратная подматрица унимодулярна.

Вполне унимодулярные матрицы играют важную роль в теории целочисленного линейного программирования: задачи линейного программирования с системой ограничений вида Ax = b, где A вполне унимодулярна, а b — целочисленный вектор, имеют целочисленные базисные допустимые решения, а значит, в частности, могут быть решены стандартным средством линейного программирования — симплекс-методом.

Некоторые примеры вполне унимодулярных матриц:

Унимодулярная полиномиальная матрица[править | править исходный текст]

Теоремы[править | править исходный текст]

Теорема1: Полиномиальная матрица унимодулярна тогда и только тогда, когда все её инвариантные множители равны единице, т.е. когда она эквивалентна единичной матрице.

Теорема 2: Полиномиальная матрица унимодулярна тогда и только тогда, когда она есть произведение матричных элементов.

Литература[править | править исходный текст]

  • Берж К.. Теория графов и ее применения. Глава 15. М., ИЛ, 1962.
  • Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. 1984.
  • Емеличев В.А. Многогранники. Графы. Оптимизация. Глава IV. г. 1981.