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

Integer matrices with +1 or -1 determinant; invertible over the integers. 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 имеет только 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 » или « out of r "). Столбцы соответствуют другому множеству C дуг на том же множестве вершин V. Чтобы вычислить запись в строке R и столбце C = st , посмотрите на путь s -to- t P в T ; тогда запись такая:

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

Подробнее см. в Шрийвере (2003).

5. Гуила-Хури показал, что матрица является TU, если и только если для каждого подмножества R строк существует присвоение знаков строкам так, что сумма со знаком (которая представляет собой вектор-строку той же ширины, что и матрица) имеет все свои элементы. в (т.е. строка-подматрица имеет невязку не более единицы). Эта и несколько других характеристик типа «тогда и только если» доказаны Шрийвером (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. Этот термин был придуман Клодом Берже , см. Hoffman , AJ; Крускал , Дж. (2010), «Введение в целочисленные граничные точки выпуклых многогранников », в М. Юнгере; и другие. (ред.), 50 лет целочисленного программирования, 1958–2008 гг. , Springer-Verlag, стр. 49–50.
2. Хеллер, И.; Томпкинс, CB (1956), «Расширение теоремы Данцига», в Kuhn , HW; Такер , А.В. (ред.), Линейные неравенства и родственные системы , Анналы математических исследований, том. 38, Принстон (Нью-Джерси): Princeton University Press, стр. 247–254.
3. Т. Заславский (1982), «Знаковые графики», Дискретная прикладная математика 4, стр. 401–406.
4. Фулкерсон, доктор медицинских наук; Гросс, О.А. (1965). «Матрицы заболеваемости и интервальные графики». Тихоокеанский математический журнал . 15 (3): 835–855. ISSN  0030-8730.
5. Хоффман, AJ; Крускал , Дж.Б. (1956), «Целочисленные граничные точки выпуклых многогранников», в Куне , Х.В.; Такер , А.В. (ред.), Линейные неравенства и родственные системы , Анналы математических исследований, том. 38, Принстон (Нью-Джерси): Princeton University Press, стр. 223–246.
6. Фудзисигэ, Сатору (1984), «Система линейных неравенств с субмодулярной функцией на векторах (0, ±1)», Линейная алгебра и ее приложения , 63 : 253–266, doi : 10.1016/0024-3795(84) 90147-2
7. Сеймур , П.Д. (1980), «Разложение регулярных матроидов», Журнал комбинаторной теории , Серия B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1
8. Ланг, Серж (2002). Алгебра (ред. 3-е изд.). Спрингер. п. 510, раздел XIII.3. ISBN 0-387-95385-Х.
9. Розенталь, Дж.; Мейз, Г.; Вагнер, У. (2011), Естественная плотность прямоугольных унимодулярных целочисленных матриц , Линейная алгебра и ее приложения, том. 434, Эльзевир, стр. 1319–1324.
10. Микели, Г.; Шнайдер, Р. (2016), Плотность унимодулярных матриц над целозамкнутыми подкольцами функциональных полей , Современные разработки в конечных областях и приложениях, World Scientific, стр. 244–253
11. Го, X .; Ян, Г. (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
• Программное обеспечение для тестирования тотальной унимодулярности М. Уолтера и К. Трумпера