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

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

Определение

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

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

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

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

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

Пример: Для $2\times 2$ матрица, ${\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})$ с $d_{1}=\gcd(a,b,c,d)$ и $d_{2}=ad-bc$.

Алгоритм

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

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

Чтобы привести матрицу к нормальной форме Смита, можно неоднократно применять следующее: $t$ петли от 1 до $m$.

Шаг I: Выбор опорной точки

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

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

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

Шаг II: Улучшение поворота

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

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

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

$\sigma \cdot \alpha +\tau \cdot \gamma =1,$

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

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

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

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

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

Шаг III: Удаление записей

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

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

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

Последний шаг

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

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

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

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

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

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

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

Приложения

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

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

Пример

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

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

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

$\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}}$

$\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}}$

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

Таким образом, нормальная форма Смита равна

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

а инвариантные коэффициенты — 2, 2 и 156.

Сложность во время выполнения

Нормальная форма Смита матрицы A размером N на N может быть вычислена за время $O(\|A\|\log \|A\|N^{4}\log N)$. Если матрица разрежена , вычисления обычно выполняются намного быстрее.

Сходство

Нормальную форму Смита можно использовать для определения того, являются ли матрицы с элементами в общем поле $K$ похожи ​ . В частности, две матрицы A и B подобны тогда и только тогда, когда характеристические матрицы $xI-A$ и $xI-B$ имеют ту же нормальную форму Смита (работающую в PID $K[x]$).

Например, с

${\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). «О системах линейных неопределенных уравнений и сравнений». Фил. Пер. Р. Сок. Лонд. 151 (1): 293–326. дои : 10.1098/rstl.1861.0016 . JSTOR   108738 . S2CID   110730515 . Перепечатано (стр. 367–409 ) в Сборнике математических статей Генри Джона Стивена Смита , Vol. I , под редакцией Дж. У. Л. Глейшера . Оксфорд: Clarendon Press (1894), xcv +603 стр.
• Нормальная форма Смита в PlanetMath .
• Пример нормальной формы Смита в PlanetMath .
• К. Р. Мэтьюз, Смит, нормальная форма . MP274: Линейная алгебра, конспект лекций, Университет Квинсленда, 1991.

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

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