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

Целочисленные матрицы с определителем +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) и отражения (определитель −1).
• Унимодулярная матрица, используемая (возможно, неявно) в редукции решетки и в нормальной форме матриц Эрмита .
• Произведение Кронекера двух унимодулярных матриц также унимодулярно. Это следует из того, что где p и q — размерности A и B соответственно. ${\displaystyle \det(A\otimes B)=(\det A)^{q}(\det B)^{p},}$

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

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

Полностью унимодулярные матрицы чрезвычайно важны в полиэдральной комбинаторике и комбинаторной оптимизации , поскольку они дают быстрый способ проверки того, что линейная программа является целочисленной (имеет целочисленный оптимум, когда любой оптимум существует). В частности, если A является TU и b является целочисленным, то линейные программы форм типа или имеют целочисленные оптимумы для любого c . Следовательно, если A полностью унимодулярна и b является целочисленным, каждая крайняя точка допустимой области (например, ) является целочисленной и, таким образом, допустимая область является целочисленным многогранником. ${\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 A}$ ${\displaystyle B}$ ${\displaystyle C}$

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

Позже было выяснено, что эти условия определяют матрицу инцидентности сбалансированного знакового графа ; таким образом, этот пример говорит, что матрица инцидентности знакового графа полностью унимодулярна, если знаковый граф сбалансирован. Обратное справедливо для знаковых графов без половинных ребер (это обобщает свойство неориентированной матрицы инцидентности графа). ^[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). ${\displaystyle s:R\to \pm 1}$ ${\displaystyle \sum _{r\in R}s(r)r}$ ${\displaystyle \{0,\pm 1\}}$

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

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

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

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

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. Любая матрица вида

${\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)}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m-k}$ ${\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
• Программное обеспечение для проверки полной унимодулярности М. Вальтера и К. Трумпера