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

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

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

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

Матрица идентичности
Обратная унимодулярная матрица
Произведение матриц двух унимодулярных

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

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

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

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

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

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

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

Каждая запись в $A$ равно 0, +1 или -1;
Каждый столбец $A$ содержит не более двух ненулевых (т. е. +1 или -1) записей;
Если две ненулевые записи в столбце $A$ имеют одинаковый знак, то строка единица находится в $B$ , а другой в $C$ ;
Если две ненулевые записи в столбце $A$ имеют противоположные знаки, то строки обоих находятся в $B$ или оба в $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 до t путь P в T ; тогда запись такая:

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

Подробнее см. в статье «Писатель» (2003).

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

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

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

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

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

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

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

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.

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

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

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

См. также

Примечания

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

Ссылки

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

Внешние ссылки

[1] Термин был придуман Клодом Берже , см. Хоффман , Эй Джей; Крускал , Дж. (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] Хоффман, Эй Джей; Крускал , Дж.Б. (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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т и Матричные классы
Явно ограниченные записи	Чередование Антидиагональ антиэрмитовский Антисимметричный наконечник стрелы Группа двуугольный Бисимметричный Блок-диагональ Блокировать Блок трехдиагональный логическое значение Коши Центросимметричный Конференция Комплекс Адамара Сопозитивный Диагональная доминанта Диагональ Дискретное преобразование Фурье элементарный Эквивалент Фробениус Обобщенная перестановка Адамар Приобретение эрмитовский Хессенберг Пустой Целое число Логический Матричный блок Мецлер Мур Неотрицательный Пятиугольный перестановка Персимметричный Полиномиальный кватернионный Подпись косо-эрмитовский Кососимметричный Горизонт Редкий Сильвестр Симметричный Тёплиц Треугольный Трехдиагональный Вандермонд Уолш С
Постоянный	Обмен Гильберт Личность Лемер Из них Паскаль Паули Редхеффер Сдвиг Ноль
Условия на собственные значения или собственные векторы	Компаньон Конвергентный Дефектный Определенный Диагонализуемый Гурвиц Положительно-определенный Стилтьес
Выполнение условий на изделия или инверсы	Конгруэнтный Идемпотент или проекция Обратимый Инволютивный Нильпотентный Нормальный Ортогональный Унимодульный Одномогущий Унитарный Полностью унимодульный Взвешивание
С конкретными приложениями	Адъюгат знак чередования Дополненный Безу Карл Великий Картан циркулирующий Кофактор коммутация Путаница Коксетер Расстояние Дублирование и устранение Евклидово расстояние Фундаментальное (линейное дифференциальное уравнение) Генератор Грамм Гессен Домохозяин якобиан Момент Расплачиваться Выбирать Случайный Вращение Зейферт сдвиг Сходство симплектический Полностью позитивный Трансформация
Используется в статистике	Центрирование Корреляция Ковариация Дизайн Двойной стохастический Информация о Фишере Имеет Точность Стохастический Переход
Используется в теории графов	Смежность Бисмежность Степень Эдмондс Заболеваемость лапласиан Соседство Зайделя Все
Используется в науке и технике	Кабиббо – Кобаяши – Маскава Плотность Фундаментальный (компьютерное зрение) Нечеткая ассоциативность Гамма Гелл-Манн гамильтониан Нерегулярный Перекрывать С Государственный переход Замена З (химия)
Связанные термины	Джордан в нормальной форме Линейная независимость Матричная экспонента Матричное представление конических сечений Идеальная матрица Псевдообратный Форма эшелона строк Вронскиан
Математический портал Список матриц Категория:Матрицы