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

В математике , А унимодулярная матрица М представляет собой квадрат целочисленной матрицы , имеющей определитель +1 или -1. Эквивалентно, это целочисленная матрица, обратимая по целым числам: существует целочисленная матрица N, которая является ее обратной (они эквивалентны по правилу Крамера ). Таким образом, каждое уравнение Mx = b , где M и b оба имеют целые компоненты, а M унимодулярно, имеет целочисленное решение. Унимодулярные матрицы порядка n образуют группу , которая обозначается .${\ Displaystyle \ OperatorName {GL} _ {п} (\ mathbb {Z})}$

Примеры унимодулярных матриц [ править ]

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

• Единичная матрица
• Обратной унимодулярной матрицы
• Продукт из двух унимодулярных матриц

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

• Матрицы Паскаля
• Матрицы перестановок
• три матрицы преобразования в троичном дереве примитивных пифагоровых троек
• Определенные матрицы преобразования для вращения , сдвига (оба с определителем 1) и отражения (определитель -1).
• Унимодулярная матрица, используемая (возможно, неявно) при редукции решетки и в нормальной форме Эрмита матриц.
• Продукт Кронекера двух унимодулярных матриц также унимодулярная. Это следует из того, что где p и q - размеры A и B соответственно.${\displaystyle \det(A\otimes B)=(\det A)^{q}(\det B)^{p},}$

Полная унимодулярность [ править ]

Полностью унимодулярная матрица ^[1] (ТА матрица) представляет собой матрицу , для которой каждая квадратной невырожденной подматрица унимодулярна. Эквивалентно, каждая квадратная подматрица имеет определитель 0, +1 или -1. Полностью унимодулярная матрица не обязательно должна быть квадратной. Из определения следует, что любая подматрица вполне унимодулярной матрицы сама является вполне унимодулярной (TU). Кроме того, отсюда следует, что любая матрица TU имеет только 0, +1 или -1 элементов. Обратное неверно, т. Е. Матрица только с 0, +1 или −1 элементами не обязательно унимодулярна. Матрица является TU тогда и только тогда, когда ^T равно TU.${\displaystyle A}$${\displaystyle A}$

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

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

1. Неориентированная матрица инцидентности двудольного графа , которая является матрицей коэффициентов для двудольного согласования , является полностью унимодулярной (TU). (Неориентированная матрица инцидентности недвудольного графа - это не TU.) В более общем смысле, в приложении к статье Хеллера и Томпкинса ^[2] А. Дж. Хоффман и Д. Гейл доказывают следующее. Пусть - матрица размера m на n , строки которой можно разбить на два непересекающихся множества и . Тогда следующие четыре условия вместе , является достаточным для быть полностью унимодулярным:${\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. Каждая сетевая матрица - это ЕД. Строки сетевой матрицы соответствуют дереву T = ( V , R ) , каждая из дуг которого имеет произвольную ориентацию (необязательно, чтобы существовала корневая вершина r такая, что дерево «укоренено в r » или » из г «) .The столбцы соответствуют другому множеству C дуг на одной и той же множеством вершин V . Чтобы вычислить запись в строке R и столбце C = st , посмотрите на путь s -to- t P в T; тогда запись:

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

См. Больше в Schrijver (2003).

5. Гуила-Хури показал, что матрица является TU тогда и только тогда, когда для каждого подмножества R строк существует присвоение знаков строкам, так что знаковая сумма (которая является вектором-строкой той же ширины, что и матрица) имеет все свои элементы in (т.е. строка-подматрица имеет невязку не более одного). Эта и несколько других характеристик «если и только если» доказаны в 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 для versus . Тогда полностью унимодулярно тогда и только тогда, когда каждый простой произвольно ориентированный цикл состоит из чередующихся прямых и обратных дуг.${\displaystyle G}$${\displaystyle P}$${\displaystyle G}$${\displaystyle A}$${\displaystyle V(G)}$${\displaystyle P}$${\displaystyle A}$${\displaystyle G}$

7. Предположим, что матрица имеет 0- ( 1) элементов и в каждом столбце элементы не убывают сверху вниз (так что все -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]}${\displaystyle R}$${\displaystyle \operatorname {GL} _{n}(R)}$${\displaystyle k}$${\displaystyle m}$${\displaystyle m-k}$${\displaystyle R^{m}}$

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

См. Также [ править ]

• Сбалансированная матрица
• Обычный матроид
• Специальная линейная группа
• Полная двойная целостность
• Нормальная форма Эрмита

Заметки [ править ]

Ссылки [ править ]

• Papadimitriou, Christos H .; Стейглиц, Кеннет (1998), «Раздел 13.2», Комбинаторная оптимизация: алгоритмы и сложность , Минеола, Нью-Йорк: Dover Publications, стр. 316, ISBN 978-0-486-40258-1
• Александр Шрайвер (1998), Теория линейного и целочисленного программирования . John Wiley & Sons, ISBN 0-471-98232-6 (математический) 
• Александр Шрайвер (2003), Комбинаторная оптимизация: многогранники и эффективность , Springer

Внешние ссылки [ править ]

• Глоссарий по математическому программированию Харви Дж. Гринберга
• Унимодулярная матрица от MathWorld
• Программное обеспечение для проверки полной унимодулярности М. Вальтера и К. Трумпера.