Унимодулярная матрица
Унимодуля́рная ма́трица — квадратная матрица с целыми коэффициентами, определитель которой равен или . Это в точности те невырожденные матрицы , для которых уравнение имеет целочисленное решение для любого целочисленного вектора .
Свойства
Унимодулярные матрицы образуют группу по умножению, т.е. следующие матрицы являются унимодулярными:
- Единичная матрица
- Обратная к унимодулярной матрице
- Произведение двух унимодулярных матриц
Вполне унимодулярная матрица
Прямоугольная матрица называется вполне унимодулярной (или абсолютно, или тотально унимодулярной), если все её миноры принимают значения из множества . Иными словами, любая её невырожденная квадратная подматрица унимодулярна.
Вполне унимодулярные матрицы играют важную роль в теории целочисленного линейного программирования: задачи линейного программирования с системой ограничений вида , где вполне унимодулярна, а — целочисленный вектор, имеют целочисленные базисные допустимые решения, а значит, в частности, могут быть решены стандартным средством линейного программирования — симплекс-методом.
Некоторые примеры вполне унимодулярных матриц:
- матрица инцидентности любого ориентированного графа;
- матрица инцидентности двудольного неориентированного графа;
- частный пример:
Унимодулярная полиномиальная матрица
Теоремы
Теорема1: Полиномиальная матрица унимодулярна тогда и только тогда, когда все её инвариантные множители равны единице, т.е. когда она эквивалентна единичной матрице.
Теорема 2: Полиномиальная матрица унимодулярна тогда и только тогда, когда она есть произведение матричных элементов.
Литература
- Берж К.. Теория графов и её применения. Глава 15. М., ИЛ, 1962.
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. 1984.
- Емеличев В.А. Многогранники. Графы. Оптимизация. Глава IV. г. 1981.