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

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

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

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

Единичная матрица
В обратный унимодулярной матрицы
В товар двух унимодулярных матриц

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

Матрицы Паскаля
Матрицы перестановок
три матрицы преобразования в троичном дерево первобытных пифагоровых троек
Некоторые матрицы преобразования для вращение, стрижка (оба с определителем 1) и отражение (определитель −1).
Унимодулярная матрица, используемая (возможно, неявно) в редукция решетки и в Нормальная форма Эрмита матриц.
В Кронекер продукт двух унимодулярных матриц также унимодулярна. Это следует, поскольку ${ Displaystyle Det (A otimes B) = ( Det A) ^ {q} ( Det B) ^ {p},}$ куда п и q размеры А и B, соответственно.

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

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

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

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

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

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

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

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

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

4. Каждые сетевая матрица это ТУ. Строки сетевой матрицы соответствуют дереву Т = (V, р), каждая из дуг которого имеет произвольную ориентацию (необязательно наличие корневой вершины р таким образом, что дерево «укоренено в р"или" из р"). Столбцы соответствуют другому набору C дуг на одном наборе вершин V. Чтобы вычислить запись в строке р и столбец C = улпосмотрите на s-к-т дорожка п в Т; тогда запись:

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

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

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

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

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

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

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

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

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

Примечания

^ Термин был придуман Клод Берже, видеть Хоффман, A.J .; Крускал, J. (2010), "Введение в Интегральные границы выпуклых многогранников.", в M. Jünger; et al. (ред.), 50 лет целочисленного программирования, 1958-2008 гг., Springer-Verlag, стр. 49–50.
^ Heller, I .; Томпкинс, C.B.Gh (1956), "Расширение теоремы Данцига", в Kuhn, H.W .; Такер, А. (ред.), Линейные неравенства и родственные системы, Анналы математических исследований, 38, Принстон (Нью-Джерси): Princeton University Press, стр. 247–254.
^ Т. Заславский (1982), «Знаковые графики», Дискретная прикладная математика 4. С. 401–406.
^ Фулкерсон, Д. Р .; Гросс, О. А. (1965). «Матрицы заболеваемости и интервальные графики». Тихоокеанский математический журнал. 15 (3): 835–855. ISSN 0030-8730.
^ Hoffman, A.J .; Крускал, Дж. Б. (1956), "Целые граничные точки выпуклых многогранников", в Kuhn, H.W .; Такер, А. (ред.), Линейные неравенства и родственные системы, Анналы математических исследований, 38, Princeton (NJ): Princeton University Press, стр. 223–246.
^ Fujishige, Satoru (1984), "Система линейных неравенств с субмодулярной функцией на (0, ± 1) векторах", Линейная алгебра и ее приложения, 63: 253–266, Дои:10.1016/0024-3795(84)90147-2
^ Сеймур, П. Д. (1980), "Разложение обычных матроидов", Линейные неравенства и родственные системы, Журнал комбинаторной теории (B), 28, Elsevier, стр. 305–359.
^ Rosenthal, J .; Лабиринт, G .; Вагнер, У. (2011), Натуральная плотность прямоугольных унимодулярных целочисленных матриц, Линейная алгебра и ее приложения, 434, Elsevier, стр. 1319–1324.
^ Micheli, G .; Шнайдер, Р. (2016), Плотность унимодулярных матриц над целозамкнутыми подкольцами функциональных полей, Современные разработки в конечных областях и приложениях, World Scientific, стр. 244–253.
^ Guo, X .; Ян, Г. (2013), Вероятность прямоугольных унимодулярных матриц над Fq [x], Линейная алгебра и ее приложения, Elsevier, стр. 2675–2682.

внешняя ссылка

[1] Термин был придуман Клод Берже, видеть Хоффман, A.J .; Крускал, J. (2010), "Введение в Интегральные границы выпуклых многогранников.", в M. Jünger; et al. (ред.), 50 лет целочисленного программирования, 1958-2008 гг., Springer-Verlag, стр. 49–50.

[2] Heller, I .; Томпкинс, C.B.Gh (1956), "Расширение теоремы Данцига", в Kuhn, H.W .; Такер, А. (ред.), Линейные неравенства и родственные системы, Анналы математических исследований, 38, Принстон (Нью-Джерси): Princeton University Press, стр. 247–254.

[3] Т. Заславский (1982), «Знаковые графики», Дискретная прикладная математика 4. С. 401–406.

[4] Фулкерсон, Д. Р .; Гросс, О. А. (1965). «Матрицы заболеваемости и интервальные графики». Тихоокеанский математический журнал. 15 (3): 835–855. ISSN 0030-8730.

[5] Hoffman, A.J .; Крускал, Дж. Б. (1956), "Целые граничные точки выпуклых многогранников", в Kuhn, H.W .; Такер, А. (ред.), Линейные неравенства и родственные системы, Анналы математических исследований, 38, Princeton (NJ): Princeton University Press, стр. 223–246.

[6] Fujishige, Satoru (1984), "Система линейных неравенств с субмодулярной функцией на (0, ± 1) векторах", Линейная алгебра и ее приложения, 63: 253–266, Дои:10.1016/0024-3795(84)90147-2

[7] Сеймур, П. Д. (1980), "Разложение обычных матроидов", Линейные неравенства и родственные системы, Журнал комбинаторной теории (B), 28, Elsevier, стр. 305–359.

[8] Rosenthal, J .; Лабиринт, G .; Вагнер, У. (2011), Натуральная плотность прямоугольных унимодулярных целочисленных матриц, Линейная алгебра и ее приложения, 434, Elsevier, стр. 1319–1324.

[9] Micheli, G .; Шнайдер, Р. (2016), Плотность унимодулярных матриц над целозамкнутыми подкольцами функциональных полей, Современные разработки в конечных областях и приложениях, World Scientific, стр. 244–253.

[10] Guo, X .; Ян, Г. (2013), Вероятность прямоугольных унимодулярных матриц над Fq [x], Линейная алгебра и ее приложения, Elsevier, стр. 2675–2682.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]