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

Целочисленные матрицы с определителем +1 или -1; обратимы над целыми числами. GL_n(Z)

В математике унимодулярная матрица M — это квадратная целочисленная матрица с определителем +1 или −1. Эквивалентно, это целочисленная матрица, которая обратима над целыми числами : существует целочисленная матрица N , которая является ее обратной (они эквивалентны по правилу Крамера ). Таким образом, каждое уравнение Mx = b , где M и b оба имеют целочисленные компоненты, а M унимодулярна, имеет целочисленное решение. Унимодулярные матрицы n  ×  n образуют группу, называемую общей линейной группой n  ×  n над , которая обозначается . З {\displaystyle \mathbb {Z} } ГЛ н ⁡ ( З ) {\displaystyle \operatorname {GL} _{n}(\mathbb {Z})}

Примеры унимодулярных матриц

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

Другие примеры включают в себя:

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

Полностью унимодулярная матрица [ 1] (матрица TU) — это матрица, у которой каждая квадратная подматрица имеет определитель 0, +1 или −1. Полностью унимодулярная матрица не обязательно должна быть квадратной. Из определения следует, что любая подматрица полностью унимодулярной матрицы сама по себе полностью унимодулярна (TU). Кроме того, следует, что любая матрица TU имеет только 0, +1 или −1 элементов. Обратное неверно , т. е. матрица, имеющая только 0, +1 или −1 элементов, не обязательно унимодулярна. Матрица является TU тогда и только тогда, когда ее транспонирование является TU.

Полностью унимодулярные матрицы чрезвычайно важны в полиэдральной комбинаторике и комбинаторной оптимизации , поскольку они дают быстрый способ проверки того, что линейная программа является целочисленной (имеет целочисленный оптимум, когда любой оптимум существует). В частности, если A является TU и b является целочисленным, то линейные программы форм типа или имеют целочисленные оптимумы для любого c . Следовательно, если A полностью унимодулярна и b является целочисленным, каждая крайняя точка допустимой области (например, ) является целочисленной и, таким образом, допустимая область является целочисленным многогранником. { мин с ⊤ х ∣ А х ≥ б , х ≥ 0 } {\displaystyle \{\min c^{\top }x\mid Ax\geq b,x\geq 0\}} { макс с ⊤ х ∣ А х ≤ б } {\displaystyle \{\max c^{\top }x\mid Ax\leq b\}} { х ∣ А х ≥ б } {\displaystyle \{x\mid Ax\geq b\}}

Общие полностью унимодулярные матрицы

1. Неориентированная матрица инцидентности двудольного графа , которая является матрицей коэффициентов для двудольного паросочетания , является полностью унимодулярной (TU). (Неориентированная матрица инцидентности недвудольного графа не является TU.) В более общем смысле, в приложении к статье Хеллера и Томпкинса [2] А. Дж. Хоффман и Д. Гейл доказывают следующее. Пусть будет матрицей m на n , строки которой можно разбить на два непересекающихся множества и . Тогда следующие четыре условия вместе достаточны для того, чтобы A была полностью унимодулярной: А {\displaystyle А} Б {\displaystyle Б} С {\displaystyle С}

  • Каждая запись равна 0, +1 или −1; А {\displaystyle А}
  • Каждый столбец содержит не более двух ненулевых (т.е. +1 или −1) записей; А {\displaystyle А}
  • Если два ненулевых элемента в столбце имеют одинаковый знак, то строка одного из них находится в , а другого в ; А {\displaystyle А} Б {\displaystyle Б} С {\displaystyle С}
  • Если два ненулевых элемента в столбце имеют противоположные знаки, то строки обоих находятся в , или обе в . А {\displaystyle А} Б {\displaystyle Б} С {\displaystyle С}

Позже было выяснено, что эти условия определяют матрицу инцидентности сбалансированного знакового графа ; таким образом, этот пример говорит, что матрица инцидентности знакового графа полностью унимодулярна, если знаковый граф сбалансирован. Обратное справедливо для знаковых графов без половинных ребер (это обобщает свойство неориентированной матрицы инцидентности графа). [3]

2. Ограничения задач максимального потока и минимальной стоимости потока дают матрицу коэффициентов с этими свойствами (и с пустым C ). Таким образом, такие задачи сетевого потока с ограниченными целочисленными мощностями имеют целочисленное оптимальное значение. Обратите внимание, что это не относится к задачам многопродуктового потока , в которых возможно иметь дробное оптимальное значение даже с ограниченными целочисленными мощностями.

3. Свойство последовательных единиц: если A является (или может быть переставлена ​​в) матрицей 0-1, в которой для каждой строки единицы появляются последовательно, то A является TU. (То же самое справедливо и для столбцов, поскольку транспонированная матрица TU также является TU.) [4]

4. Каждая сетевая матрица является TU. Строки сетевой матрицы соответствуют дереву T = ( V , R ) , каждая из дуг которого имеет произвольную ориентацию (не обязательно, чтобы существовала корневая вершина r такая, что дерево «корневое в r » или «из r »). Столбцы соответствуют другому набору C дуг на том же наборе вершин V . Чтобы вычислить запись в строке R и столбце C = st , посмотрите на путь P от s до t в T ; тогда запись будет:

  • +1, если дуга R появляется впереди в P ,
  • −1, если дуга R появляется в обратном направлении в P ,
  • 0 , если дуга R не появляется в P.

Подробнее см. в Schrijver (2003).

5. Гуила-Хури показала, что матрица является TU тогда и только тогда, когда для каждого подмножества строк R существует присвоение знаков строкам таким образом, что знаковая сумма (которая является вектором-строкой той же ширины, что и матрица) имеет все свои элементы в (т.е. строка-подматрица имеет расхождение не более одного). Эта и несколько других характеристик «если и только если» доказаны в Schrijver (1998). с : Р → ± 1 {\displaystyle s:R\to \pm 1} ∑ г ∈ Р с ( г ) г {\displaystyle \sum _{r\in R}s(r)r} { 0 , ± 1 } {\displaystyle \{0,\pm 1\}}

6. Хоффман и Крускал [5] доказали следующую теорему. Предположим, что — ориентированный граф без 2-дициклов, — множество всех дипутов в , а — матрица инцидентности 0-1 по сравнению с . Тогда является полностью унимодулярным тогда и только тогда, когда каждый простой произвольно ориентированный цикл в состоит из чередующихся прямых и обратных дуг. Г {\displaystyle G} П {\displaystyle P} Г {\displaystyle G} А {\displaystyle А} В ( Г ) {\displaystyle V(Г)} П {\displaystyle P} А {\displaystyle А} Г {\displaystyle G}

7. Предположим, что матрица имеет 0-( 1) элементов, и в каждом столбце элементы не убывают сверху вниз (то есть все −1 находятся сверху, затем 0, затем 1 находятся снизу). Фудзисиге показал [6] , что матрица является TU тогда и только тогда, когда каждая подматрица 2 на 2 имеет определитель в . ± {\displaystyle \pm} 0 , ± 1 {\displaystyle 0,\pm 1}

8. Сеймур (1980) [7] доказал полную характеристику всех матриц TU, которую мы описываем здесь только неформально. Теорема Сеймура заключается в том, что матрица является TU тогда и только тогда, когда она является определенной естественной комбинацией некоторых сетевых матриц и некоторых копий конкретной матрицы TU размером 5 на 5.

Конкретные примеры

1. Следующая матрица полностью унимодулярна:

А = [ − 1 − 1 0 0 0 + 1 + 1 0 − 1 − 1 0 0 0 + 1 + 1 0 − 1 0 0 0 0 + 1 + 1 − 1 ] . {\displaystyle A=\left[{\begin{array}{rrrrrr}-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{array}}\right].}

Эта матрица возникает как матрица коэффициентов ограничений в формулировке линейного программирования задачи максимального потока в следующей сети:

2. Любая матрица вида

А = [ ⋮ ⋮ ⋯ + 1 ⋯ + 1 ⋯ ⋮ ⋮ ⋯ + 1 ⋯ − 1 ⋯ ⋮ ⋮ ] . {\displaystyle A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].}

не является полностью унимодулярной, поскольку имеет квадратную подматрицу с определителем −2.

Абстрактная линейная алгебра

Абстрактная линейная алгебра рассматривает матрицы с элементами из любого коммутативного кольца , не ограничиваясь целыми числами. В этом контексте унимодулярная матрица — это матрица, обратимая над кольцом; эквивалентно, определитель которой — единица . Эта группа обозначается . [ 8] Прямоугольная матрица называется унимодулярной, если ее можно расширить строками до унимодулярной квадратной матрицы. [9] [10] [11] Р {\displaystyle R} ГЛ н ⁡ ( Р ) {\displaystyle \operatorname {GL} _{n}(R)} k {\displaystyle k} m {\displaystyle m} m − k {\displaystyle m-k} R m {\displaystyle R^{m}}

Над полем унимодулярный имеет то же значение, что и невырожденный . Унимодулярный здесь относится к матрицам с коэффициентами в некотором кольце (часто целые числа), которые обратимы над этим кольцом, а невырожденный используется для обозначения матриц, которые обратимы над полем.

Смотрите также

Примечания

  1. ↑ Термин был придуман Клодом Берже , см. Хоффман , А. Дж.; Крускал , Дж. (2010), «Введение в интегральные граничные точки выпуклых многогранников », в М. Юнгере и др. (ред.), 50 лет целочисленного программирования, 1958–2008 , Springer-Verlag, стр.  49–50
  2. ^ Хеллер, И.; Томпкинс, К. Б. (1956), «Расширение теоремы Данцига», в Kuhn , HW; Tucker , AW (ред.), Линейные неравенства и родственные системы , Annals of Mathematics Studies, т. 38, Принстон (Нью-Джерси): Princeton University Press, стр.  247–254
  3. ^ Т. Заславский (1982), «Знаковые графы», Дискретная прикладная математика 4, стр. 401–406.
  4. ^ Фулкерсон, DR; Гросс, OA (1965). «Матрицы инцидентности и интервальные графы». Pacific Journal of Mathematics . 15 (3): 835–855 . ISSN  0030-8730.
  5. ^ Хоффман, А. Дж.; Крускал , Дж. Б. (1956), «Интегральные граничные точки выпуклых многогранников», в Kuhn , HW; Tucker , AW (ред.), Линейные неравенства и родственные системы , Annals of Mathematics Studies, т. 38, Принстон (Нью-Джерси): Princeton University Press, стр.  223–246
  6. ^ Фудзисиге, Сатору (1984), «Система линейных неравенств с субмодулярной функцией на (0, ±1) векторах», Линейная алгебра и ее приложения , 63 : 253–266 , doi : 10.1016/0024-3795(84)90147-2
  7. ^ Сеймур , PD (1980), «Разложение регулярных матроидов», Журнал комбинаторной теории , Серия B, 28 (3): 305–359 , doi :10.1016/0095-8956(80)90075-1
  8. ^ Ланг, Серж (2002). Алгебра (переиздание 3-е). Springer. стр. 510, раздел XIII.3. ISBN 0-387-95385-X.
  9. ^ Розенталь, Дж.; Мейз, Г.; Вагнер, У. ( 2011 ), Естественная плотность прямоугольных унимодулярных целочисленных матриц , Линейная алгебра и ее приложения, т. 434, Elsevier, стр.  1319–1324
  10. ^ Микели, Г.; Шнайдер, Р. (2016), Плотность унимодулярных матриц над целочисленно замкнутыми подкольцами полей функций , Contemporary Developments in Finite Fields and Applications, World Scientific, стр.  244–253
  11. ^ Го, X.; Ян, G. (2013), Вероятность прямоугольных унимодулярных матриц над Fq [x] , Линейная алгебра и ее приложения, Elsevier, стр.  2675–2682

Ссылки

  • Пападимитриу, Христос Х.; Стейглиц, Кеннет (1998), «Раздел 13.2», Комбинаторная оптимизация: алгоритмы и сложность, Минеола, Нью-Йорк: Dover Publications, стр. 316, ISBN 978-0-486-40258-1
  • Александр Шрайвер (1998), Теория линейного и целочисленного программирования . John Wiley & Sons, ISBN 0-471-98232-6 (математический) 
  • Александр Шрийвер (2003), Комбинаторная оптимизация: многогранники и эффективность , Springer
  • Глоссарий математического программирования Харви Дж. Гринберга
  • Унимодулярная матрица из MathWorld
  • Программное обеспечение для проверки полной унимодулярности М. Вальтера и К. Трумпера
Retrieved from "https://en.wikipedia.org/w/index.php?title=Unimodular_matrix&oldid=1261065664"