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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Унімодулярна матриця 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 \ge 0\} або \{\max cx \mid Ax \ge b\} мають цілочисельний оптимум для будь-якого c. Отже, якщо A повністю унімодулярна і b цілочисельний вектор, кожен екстремум області досяжності (наприклад \{x \mid Ax \ge b\}) є цілочисельним, отже область досяжності утворює цілочисельний багатогранник.

Примітки[ред.ред. код]

  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 

Посилання[ред.ред. код]