Унімодулярна матриця M — цілочисельна матриця з визначником, що дорівнює +1 або −1. Тотожне визначення, це цілочисельна матриця оборотна над цілими, тобто існує цілочисельна матриця N, яка є її оберненою. Отже, кожне рівняння Mx = b, де M і b цілочисельні, і M унімодулярна, має цілочисельний розв'язок. Унімодулярні матриці порядку n утворюють групу, яка позначається .
Приклади унімодулярних матриць Унімодулярні матриці з підгрупи загальної лінійної групи щодо множення матриць, тобто наступні матриці є унімодулярними: Одинична матриця Обернена від унімодулярної матриці Добуток двох унімодулярних матриць Далі: Добуток Кронекера двох унімодулярних матриць також унімодулярний. Це випливає з
де p і q розміри A і B, відповідно.
Конкретні приклади: Симплектична матриця Матриця Паскаля Матриця перестановки три матриці перетворень тримісного дерева примітивних тріад Піфагора матриця обмежень Задачі про призначення
Повна унімодулярність Повністю унімодулярна матриця Термін винайшов Клод Берж, дивись (ПУ матриця) — матриця, якщо всі її мінори приймають значення з множини {-1, 0, +1}. Інакше, будь-яка її невироджена квадратна підматриця унімодулярна. З визначення виходить, що всі елементи такої матриці це 0, +1 або −1.
Повністю унімодулярні матриці надзвичайно важливі в поліедральній комбінаторіці та комбінаторній оптимізації, бо вони надають швидкий спосіб перевірки лінійної програми на цілочисельність (наявність цілочисельного оптимуму, коли оптимум існує). Конкретно, якщо A це ПУ і b це цілочисельний вектор, тоді лінійні програми такої форми або мають цілочисельний оптимум для будь-якого c. Отже, якщо A повністю унімодулярна і b цілочисельний вектор, кожен екстремум області досяжності (наприклад ) є цілочисельним, отже область досяжності утворює цілочисельний багатогранник.
Примітки
Посилання Mathematical Programming Glossary by Harvey J. Greenberg