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

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

Свойства

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

• Единичная матрица
• Обратная к унимодулярной матрице
• Произведение двух унимодулярных матриц

Вполне унимодулярная матрица

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

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

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

• матрица инцидентности любого ориентированного графа;
• матрица инцидентности двудольного неориентированного графа;
• частный пример:

  [math]\displaystyle{ \begin{bmatrix} -1 & -1 & 0 & 0 & 0 & +1\\ +1 & 0 & -1 & -1 & 0 & 0\\ 0 & +1 & +1 & 0 & -1 & 0\\ 0 & 0 & 0 & +1 & +1 & -1\\ \end{bmatrix}. }[/math]

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

Теоремы

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

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

Литература

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