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

Поделись знанием:
(перенаправлено с «Вполне унимодулярная матрица»)
Перейти к: навигация, поиск

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





Свойства

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

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

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

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

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

-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.

Отрывок, характеризующий Унимодулярная матрица

Уже были зазимки, утренние морозы заковывали смоченную осенними дождями землю, уже зелень уклочилась и ярко зелено отделялась от полос буреющего, выбитого скотом, озимого и светло желтого ярового жнивья с красными полосами гречихи. Вершины и леса, в конце августа еще бывшие зелеными островами между черными полями озимей и жнивами, стали золотистыми и ярко красными островами посреди ярко зеленых озимей. Русак уже до половины затерся (перелинял), лисьи выводки начинали разбредаться, и молодые волки были больше собаки. Было лучшее охотничье время. Собаки горячего, молодого охотника Ростова уже не только вошли в охотничье тело, но и подбились так, что в общем совете охотников решено было три дня дать отдохнуть собакам и 16 сентября итти в отъезд, начиная с дубравы, где был нетронутый волчий выводок.
В таком положении были дела 14 го сентября.
Весь этот день охота была дома; было морозно и колко, но с вечера стало замолаживать и оттеплело. 15 сентября, когда молодой Ростов утром в халате выглянул в окно, он увидал такое утро, лучше которого ничего не могло быть для охоты: как будто небо таяло и без ветра спускалось на землю. Единственное движенье, которое было в воздухе, было тихое движенье сверху вниз спускающихся микроскопических капель мги или тумана. На оголившихся ветвях сада висели прозрачные капли и падали на только что свалившиеся листья. Земля на огороде, как мак, глянцевито мокро чернела, и в недалеком расстоянии сливалась с тусклым и влажным покровом тумана. Николай вышел на мокрое с натасканной грязью крыльцо: пахло вянущим лесом и собаками. Чернопегая, широкозадая сука Милка с большими черными на выкате глазами, увидав хозяина, встала, потянулась назад и легла по русачьи, потом неожиданно вскочила и лизнула его прямо в нос и усы. Другая борзая собака, увидав хозяина с цветной дорожки, выгибая спину, стремительно бросилась к крыльцу и подняв правило (хвост), стала тереться о ноги Николая.
– О гой! – послышался в это время тот неподражаемый охотничий подклик, который соединяет в себе и самый глубокий бас, и самый тонкий тенор; и из за угла вышел доезжачий и ловчий Данило, по украински в скобку обстриженный, седой, морщинистый охотник с гнутым арапником в руке и с тем выражением самостоятельности и презрения ко всему в мире, которое бывает только у охотников. Он снял свою черкесскую шапку перед барином, и презрительно посмотрел на него. Презрение это не было оскорбительно для барина: Николай знал, что этот всё презирающий и превыше всего стоящий Данило всё таки был его человек и охотник.