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

Унімодулярна матриця M — цілочисельна матриця з визначником, що дорівнює +1 або −1. Тотожне визначення, це цілочисельна матриця оборотна над цілими, тобто існує цілочисельна матриця N, яка є її оберненою. Отже, кожне рівняння Mx = b, де M і b цілочисельні, і M унімодулярна, має цілочисельний розв'язок. Унімодулярні матриці порядку n утворюють групу, яка позначається $GL_{n}(\mathbb {Z} )$ .

Приклади унімодулярних матриць

Унімодулярні матриці з підгрупи загальної лінійної групи щодо множення матриць, тобто наступні матриці є унімодулярними:

Одинична матриця
Обернена від унімодулярної матриці
Добуток двох унімодулярних матриць

Далі:

Добуток Кронекера двох унімодулярних матриць також унімодулярний. Це випливає з

\det(A\otimes B)=(\det A)^{q}(\det B)^{p},

де p і q розміри A і B, відповідно.

Конкретні приклади:

Симплектична матриця
Матриця Паскаля
Матриця перестановки
три матриці перетворень тримісного дерева примітивних тріад Піфагора
матриця обмежень Задачі про призначення

Повна унімодулярність

Повністю унімодулярна матриця [1] (ПУ матриця) — матриця, якщо всі її мінори приймають значення з множини {-1, 0, +1}. Інакше, будь-яка її невироджена квадратна підматриця унімодулярна. З визначення виходить, що всі елементи такої матриці це 0, +1 або −1.

Повністю унімодулярні матриці надзвичайно важливі в поліедральній комбінаторіці та комбінаторній оптимізації, бо вони надають швидкий спосіб перевірки лінійної програми на цілочисельність (наявність цілочисельного оптимуму, коли оптимум існує). Конкретно, якщо A це ПУ і b це цілочисельний вектор, тоді лінійні програми такої форми $\{\min cx\mid Ax=b,x\geq 0\}$ або $\{\max cx\mid Ax\geq b\}$ мають цілочисельний оптимум для будь-якого c. Отже, якщо A повністю унімодулярна і b цілочисельний вектор, кожен екстремум області досяжності (наприклад $\{x\mid Ax\geq b\}$ ) є цілочисельним, отже область досяжності утворює цілочисельний багатогранник.

Примітки

Термін винайшов Клод Берж, дивись Hoffman, A.J.; Kruskal, J. (2010). Introduction to Integral Boundary Points of Convex Polyhedra. У M. Jünger et al. (eds.). 50 Years of Integer Programming, 1958-2008. Springer-Verlag. с. 49–50.

Посилання

Mathematical Programming Glossary by Harvey J. Greenberg
Weisstein, Eric W. UnimodularMatrix(англ.) на сайті Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Термін винайшов Клод Берж, дивись Hoffman, A.J.; Kruskal, J. (2010). Introduction to Integral Boundary Points of Convex Polyhedra. У M. Jünger et al. (eds.). 50 Years of Integer Programming, 1958-2008. Springer-Verlag. с. 49–50.