Loading AI tools
З Вікіпедії, вільної енциклопедії
Унімодулярна матриця M — цілочисельна матриця з визначником, що дорівнює +1 або −1. Тотожне визначення, це цілочисельна матриця оборотна над цілими, тобто існує цілочисельна матриця N, яка є її оберненою. Отже, кожне рівняння Mx = b, де M і b цілочисельні, і M унімодулярна, має цілочисельний розв'язок. Унімодулярні матриці порядку n утворюють групу, яка позначається .
Унімодулярні матриці з підгрупи загальної лінійної групи щодо множення матриць, тобто наступні матриці є унімодулярними:
Далі:
Конкретні приклади:
Повністю унімодулярна матриця [1] (ПУ матриця) — матриця, якщо всі її мінори приймають значення з множини {-1, 0, +1}. Інакше, будь-яка її невироджена квадратна підматриця унімодулярна. З визначення виходить, що всі елементи такої матриці це 0, +1 або −1.
Повністю унімодулярні матриці надзвичайно важливі в поліедральній комбінаторіці та комбінаторній оптимізації, бо вони надають швидкий спосіб перевірки лінійної програми на цілочисельність (наявність цілочисельного оптимуму, коли оптимум існує). Конкретно, якщо A це ПУ і b це цілочисельний вектор, тоді лінійні програми такої форми або мають цілочисельний оптимум для будь-якого c. Отже, якщо A повністю унімодулярна і b цілочисельний вектор, кожен екстремум області досяжності (наприклад ) є цілочисельним, отже область досяжності утворює цілочисельний багатогранник.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.