Нормальная форма Смита

В математике нормальная форма Смита (иногда сокращенно SNF ^[1] ) - это нормальная форма, которая может быть определена для любой матрицы (не обязательно квадратной) с элементами в области главных идеалов (PID). Нормальная форма Смита матрицы диагональна и может быть получена из исходной матрицы умножением слева и справа на обратимые квадратные матрицы. В частности, целые числа являются PID, поэтому всегда можно вычислить нормальную форму Смита для целочисленной матрицы. Нормальная форма Смита очень полезна для работы с конечно сгенерированными модулями над PID и, в частности, для вывода структуры частного свободного модуля.. Он назван в честь британского математика Генри Джона Стивена Смита .

Определение [ править ]

Пусть ненулевые м × п матрица над областью главных идеалов R . Существуют обратимые и -матрицы S, T такие, что произведение SAT равно ${\ displaystyle m \ times m}$${\ Displaystyle п \ раз п}$

${\displaystyle {\begin{pmatrix}\alpha _{1}&0&0&&\cdots &&0\\0&\alpha _{2}&0&&\cdots &&0\\0&0&\ddots &&&&0\\\vdots &&&\alpha _{r}&&&\vdots \\&&&&0&&\\&&&&&\ddots &\\0&&&\cdots &&&0\end{pmatrix}}.}$

и диагональные элементы удовлетворяют . Это Смит нормальная форма матрицы A . Элементы уникальны с точностью до умножения на единицу и называются элементарными делителями , инвариантами или инвариантными множителями . Их можно вычислить (с точностью до умножения на единицу) как${\displaystyle \alpha _{i}}$${\displaystyle \alpha _{i}\mid \alpha _{i+1}\;\forall \;1\leq i<r}$${\displaystyle \alpha _{i}}$

${\displaystyle \alpha _{i}={\frac {d_{i}(A)}{d_{i-1}(A)}},}$

где (называемый i -м делителем определителя ) равен наибольшему общему делителю всех миноров матрицы A и .${\displaystyle d_{i}(A)}$${\displaystyle i\times i}$ ${\displaystyle d_{0}(A):=1}$

Алгоритм [ править ]

Первая цель - найти обратимые квадратные матрицы и такие, чтобы произведение было диагональным. Это самая сложная часть алгоритма. Когда диагональность достигнута, матрицу относительно легко привести в нормальную форму Смита. Выражаясь более отвлеченно, цель состоит в том, чтобы показать , что мышление как отображение (свободный - модуль ранга ) до (свободный - модуль ранга ), существуют изоморфизмы и такие , что имеет простой вид диагональной матрицы . Матрицы и можно найти, начав с единичных матриц соответствующего размера и изменив${\displaystyle S}$${\displaystyle T}$${\displaystyle SAT}$${\displaystyle A}$${\displaystyle R^{n}}$${\displaystyle R}$${\displaystyle n}$${\displaystyle R^{m}}$${\displaystyle R}$${\displaystyle m}$${\displaystyle S:R^{m}\to R^{m}}$${\displaystyle T:R^{n}\to R^{n}}$${\displaystyle S\cdot A\cdot T}$${\displaystyle S}$${\displaystyle T}$${\displaystyle S}$каждый раз , когда операция строки выполняются на в алгоритме с помощью соответствующей операции на колонке (например, если строка добавляется к строке из , а затем колонку следует вычесть из столбца из сохранить инвариант продукта), а так же изменений для каждой операции на колонку выполнила. Поскольку операции со строками - это умножения слева, а операции со столбцами - умножения справа, это сохраняет инвариант, где обозначают текущие значения и обозначает исходную матрицу; со временем матрицы в этом инварианте становятся диагональными. Только обратимые строк и столбцов операции выполняются, который гарантирует , что и остаются обратимые матрицы.${\displaystyle A}$${\displaystyle i}$${\displaystyle j}$${\displaystyle A}$${\displaystyle j}$${\displaystyle i}$${\displaystyle S}$${\displaystyle T}$${\displaystyle A'=S'\cdot A\cdot T'}$${\displaystyle A',S',T'}$${\displaystyle A}$${\displaystyle S}$${\displaystyle T}$

Для напишите количество простых множителей (они существуют и уникальны, поскольку любой PID также является уникальной областью факторизации ). В частности, это также область Безу , поэтому это область НОД, а НОД любых двух элементов удовлетворяет тождеству Безу .${\displaystyle a\in R\setminus \{0\}}$${\displaystyle \delta (a)}$${\displaystyle a}$${\displaystyle R}$

Чтобы преобразовать матрицу в нормальную форму Смита, можно многократно применить следующее, где цикл от 1 до ' .${\displaystyle t}$${\displaystyle m}$

Шаг I. Выбор точки поворота [ править ]

Выберите наименьший индекс столбца с ненулевой записью, начиная поиск с индекса столбца, если .${\displaystyle j_{t}}$${\displaystyle A}$${\displaystyle j_{t-1}+1}$${\displaystyle t>1}$

Мы хотим иметь ; если это так, то этот шаг завершен, в противном случае по предположению есть некоторый with , и мы можем поменять местами строки и , таким образом получив .${\displaystyle a_{t,j_{t}}\neq 0}$${\displaystyle k}$${\displaystyle a_{k,j_{t}}\neq 0}$${\displaystyle t}$${\displaystyle k}$${\displaystyle a_{t,j_{t}}\neq 0}$

Выбранная нами точка опоры теперь находится в позиции .${\displaystyle (t,j_{t})}$

Шаг 2. Улучшение сводной таблицы [ править ]

Если существует запись в позиции ( k , j _t ) такая, что , то, позволяя , мы знаем по свойству Безу, что существуют такие σ, τ в R , что${\displaystyle a_{t,j_{t}}\nmid a_{k,j_{t}}}$${\displaystyle \beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)}$

${\displaystyle a_{t,j_{t}}\cdot \sigma +a_{k,j_{t}}\cdot \tau =\beta .}$

Путем умножения слева на подходящую обратимую матрицу L можно добиться, чтобы строка t матричного произведения была суммой σ, умноженной на исходную строку t, и τ, умноженную на исходную строку k , что строка k произведения является другой линейной комбинацией исходных строк и что все остальные строки не изменились. Явно, если σ и τ удовлетворяют приведенному выше уравнению, то для и (какие деления возможны по определению β) имеем${\displaystyle \alpha =a_{t,j_{t}}/\beta }$${\displaystyle \gamma =a_{k,j_{t}}/\beta }$

${\displaystyle \sigma \cdot \alpha +\tau \cdot \gamma =1,}$

так что матрица

${\displaystyle L_{0}={\begin{pmatrix}\sigma &\tau \\-\gamma &\alpha \\\end{pmatrix}}}$

обратима, с обратным

${\displaystyle {\begin{pmatrix}\alpha &-\tau \\\gamma &\sigma \\\end{pmatrix}}.}$

Теперь L можно получить, поместив в строки и столбцы t и k единичной матрицы. По построению матрица, полученная после умножения слева на L, имеет элемент β в позиции ( t , j _t ) (и из-за нашего выбора α и γ она также имеет элемент 0 в позиции ( k , j _t ), что полезно хотя и не принципиально для алгоритма). Эта новая запись β делит запись, которая была раньше, и, в частности ; поэтому повторение этих шагов должно в конечном итоге прекратиться. В итоге получается матрица, имеющая запись в позиции ( t , j _t${\displaystyle L_{0}}$${\displaystyle a_{t,j_{t}}}$${\displaystyle \delta (\beta )<\delta (a_{t,j_{t}})}$), который разделяет все записи в столбце j _t .

Шаг III: Удаление записей [ править ]

Наконец, добавляя соответствующие кратные строки t , можно добиться, чтобы все записи в столбце j _t, кроме записи в позиции ( t , j _t ), были равны нулю. Это может быть достигнуто умножением слева на соответствующую матрицу. Однако, чтобы сделать матрицу полностью диагональной, нам нужно также удалить ненулевые элементы в строке позиции ( t , j _t ). Это может быть достигнуто путем повторения действий , описанных в стадии II для столбцов вместо строк, и используя умножение справа на транспонированной матрицы , полученной L . Как правило, это приведет к тому, что нулевые записи из предыдущего применения шага III снова станут ненулевыми.

Однако обратите внимание, что каждое применение шага II для строк или столбцов должно продолжать уменьшать значение , и поэтому процесс должен в конечном итоге останавливаться после некоторого количества итераций, что приводит к матрице, в которой запись в позиции ( t , j _t ) является единственной ненулевой записью как в строке, так и в столбце.${\displaystyle \delta (a_{t,j_{t}})}$

На этом этапе необходимо диагонализовать только блок A в нижнем правом углу ( t , j _t ), и концептуально алгоритм может применяться рекурсивно, рассматривая этот блок как отдельную матрицу. Другими словами, мы можем увеличить t на единицу и вернуться к шагу I.

Последний шаг [ править ]

Применяя шаги, описанные выше, к оставшимся ненулевым столбцам результирующей матрицы (если они есть), мы получаем -матрицу с индексами столбцов где . Элементы матрицы не равны нулю, и все остальные записи равны нулю.${\displaystyle m\times n}$${\displaystyle j_{1}<\ldots <j_{r}}$${\displaystyle r\leq \min(m,n)}$${\displaystyle (l,j_{l})}$

Теперь мы можем переместить нулевые столбцы этой матрицы вправо, чтобы ненулевые элементы находились на позициях для . Для краткости установите элемент в положение .${\displaystyle (i,i)}$${\displaystyle 1\leq i\leq r}$${\displaystyle \alpha _{i}}$${\displaystyle (i,i)}$

Условие делимости диагональных элементов может не выполняться. Для любого индекса, для которого этот недостаток можно исправить операциями со строками и столбцами, и только: сначала добавьте столбец в столбец, чтобы получить запись в столбце i, не нарушая запись в позиции , а затем примените операцию строки, чтобы сделать запись в положение такое же, как на шаге II; наконец, действуйте как в шаге III, чтобы снова сделать диагональ матрицы. Поскольку новая запись в позиции является линейной комбинацией исходной , она делится на β.${\displaystyle i<r}$${\displaystyle \alpha _{i}\nmid \alpha _{i+1}}$${\displaystyle i}$${\displaystyle i+1}$${\displaystyle i+1}$${\displaystyle i}$${\displaystyle \alpha _{i+1}}$${\displaystyle \alpha _{i}}$${\displaystyle (i,i)}$${\displaystyle (i,i)}$${\displaystyle \beta =\gcd(\alpha _{i},\alpha _{i+1})}$${\displaystyle (i+1,i+1)}$${\displaystyle \alpha _{i},\alpha _{i+1}}$

Значение не изменяется с помощью вышеуказанной операции (это δ определителя верхней подматрицы), поэтому эта операция уменьшает (перемещая простые множители вправо) значение${\displaystyle \delta (\alpha _{1})+\cdots +\delta (\alpha _{r})}$${\displaystyle r\times r}$

${\displaystyle \sum _{j=1}^{r}(r-j)\delta (\alpha _{j}).}$

Таким образом, после конечного числа применений этой операции дальнейшее применение невозможно, что означает, что мы получили желаемое.${\displaystyle \alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}}$

Поскольку все задействованные в процессе манипуляции со строками и столбцами обратимы, это показывает, что существуют обратимые и -матрицы S, T, так что произведение SAT удовлетворяет определению нормальной формы Смита. В частности, это показывает, что нормальная форма Смита существует, что предполагалось без доказательства в определении.${\displaystyle m\times m}$${\displaystyle n\times n}$

Приложения [ править ]

Нормальная форма Смита полезно для вычисления гомологии в виде цепного комплекса , когда цепные модули цепи комплекса конечно порождены . Например, в топологии его можно использовать для вычисления гомологии симплициального комплекса или комплекса CW над целыми числами, поскольку граничные карты в таком комплексе являются просто целочисленными матрицами. Его также можно использовать для определения инвариантных факторов, которые встречаются в структурной теореме для конечно порожденных модулей над областью главных идеалов , которая включает фундаментальную теорему о конечно порожденных абелевых группах .

Нормальная форма Смита также используется в теории управления для вычисления передачи и блокировки нулей из в передаточной функции матрицы . ^[2]

Пример [ править ]

В качестве примера мы найдем нормальную форму Смита следующей матрицы над целыми числами.

${\displaystyle {\begin{pmatrix}2&4&4\\-6&6&12\\10&4&16\end{pmatrix}}}$

Следующие матрицы являются промежуточными этапами применения алгоритма к указанной выше матрице.

${\displaystyle \to {\begin{pmatrix}2&0&0\\-6&18&24\\10&-16&-4\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&18&24\\0&-16&-4\end{pmatrix}}}$

${\displaystyle \to {\begin{pmatrix}2&0&0\\0&2&20\\0&-16&-4\end{pmatrix}}\to {\begin{pmatrix}2&0&0\\0&2&20\\0&0&156\end{pmatrix}}}$

${\displaystyle \to {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}$

Итак, нормальная форма Смита

${\displaystyle {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}$

а инвариантные множители равны 2, 2 и 156.

Сходство [ править ]

Нормальная форма Смита может использоваться, чтобы определить, похожи ли матрицы с записями над общим полем . В частности, две матрицы A и B подобны тогда и только тогда, когда характеристические матрицы и имеют одинаковую нормальную форму Смита.${\displaystyle xI-A}$${\displaystyle xI-B}$

Например, с

${\displaystyle {\begin{aligned}A&{}={\begin{bmatrix}1&2\\0&1\end{bmatrix}},&&{\mbox{SNF}}(xI-A)={\begin{bmatrix}1&0\\0&(x-1)^{2}\end{bmatrix}}\\B&{}={\begin{bmatrix}3&-4\\1&-1\end{bmatrix}},&&{\mbox{SNF}}(xI-B)={\begin{bmatrix}1&0\\0&(x-1)^{2}\end{bmatrix}}\\C&{}={\begin{bmatrix}1&0\\1&2\end{bmatrix}},&&{\mbox{SNF}}(xI-C)={\begin{bmatrix}1&0\\0&(x-1)(x-2)\end{bmatrix}}.\end{aligned}}}$

A и B похожи, потому что нормальная форма Смита их характеристических матриц совпадает, но не похожи на C, потому что нормальная форма Смита характеристических матриц не совпадает.

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

• Каноническая форма
• Элементарные делители
• Нормальная форма Фробениуса (также называемая рациональной канонической формой)
• Нормальная форма Эрмита
• Инвариантный фактор
• Структурная теорема для конечно порожденных модулей над областью главных идеалов

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

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

• Смит, Генри Дж. Стивен (1861). «О системах линейных неопределенных уравнений и сравнений». Фил. Пер. R. Soc. Лондон. 151 (1): 293–326. DOI : 10,1098 / rstl.1861.0016 . JSTOR  108738 .Перепечатано (стр. 367–409 ) в The Collected Mathematical Papers of Henry John Stephen Smith , Vol. I , отредактированный JWL Glaisher . Оксфорд: Clarendon Press (1894), xcv +603 стр.
• Нормальная форма Смита в PlanetMath .
• Пример нормальной формы Смита в PlanetMath .
• К. Р. Мэтьюз, нормальная форма Смита . MP274: Линейная алгебра, конспект лекций, Университет Квинсленда, 1991.

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

• Анимированный пример вычисления нормальной формы Смита .