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

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

Определение

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

( α 1 0 0 ⋯ 0 ⋯ 0 0 α 2 0 0 0 ⋱ ⋮ ⋮ ⋮ α r 0 ⋯ 0 ⋯ 0 ⋮ ⋮ ⋮ 0 ⋯ 0 ⋯ 0 ) . {\displaystyle {\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}}.}

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

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

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

Пример: Для матрицы с и . 2 × 2 {\displaystyle 2\times 2} S N F ( a     b c     d ) = d i a g ( d 1 , d 2 / d 1 ) {\displaystyle {\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})} d 1 = gcd ( a , b , c , d ) {\displaystyle d_{1}=\gcd(a,b,c,d)} d 2 = | a d − b c | {\displaystyle d_{2}=|ad-bc|}

Алгоритм

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

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

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

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

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

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

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

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

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

a t , j t ⋅ σ + a k , j t ⋅ τ = β . {\displaystyle a_{t,j_{t}}\cdot \sigma +a_{k,j_{t}}\cdot \tau =\beta .}

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

σ ⋅ α + τ ⋅ γ = 1 , {\displaystyle \sigma \cdot \alpha +\tau \cdot \gamma =1,}

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

L 0 = ( σ τ − γ α ) {\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 ), который делит все элементы в столбце j t . L 0 {\displaystyle L_{0}} a t , j t {\displaystyle a_{t,j_{t}}} δ ( β ) < δ ( a t , j t ) {\displaystyle \delta (\beta )<\delta (a_{t,j_{t}})}

Шаг III: Исключение записей

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

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

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

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

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

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

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

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

∑ j = 1 r ( r − j ) δ ( α j ) . {\displaystyle \sum _{j=1}^{r}(r-j)\delta (\alpha _{j}).}

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

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

Приложения

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

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

Пример

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

( 2 4 4 − 6 6 12 10 4 16 ) {\displaystyle {\begin{pmatrix}2&4&4\\-6&6&12\\10&4&16\end{pmatrix}}}

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

→ ( 2 0 0 − 6 18 24 10 − 16 − 4 ) → ( 2 0 0 0 18 24 0 − 16 − 4 ) {\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}}}
→ ( 2 0 0 0 2 20 0 − 16 − 4 ) → ( 2 0 0 0 2 20 0 0 156 ) {\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}}}
→ ( 2 0 0 0 2 0 0 0 156 ) {\displaystyle \to {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}

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

( 2 0 0 0 2 0 0 0 156 ) {\displaystyle {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}

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

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

Нормальная форма Смита матрицы A размером N на N может быть вычислена за время [3] . Если матрица разреженная , вычисления обычно происходят намного быстрее. O ( ‖ A ‖ log ⁡ ‖ A ‖ N 4 log ⁡ N ) {\displaystyle O(\|A\|\log \|A\|N^{4}\log N)}

Сходство

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

Например, с

A = [ 1 2 0 1 ] , SNF ( x I − A ) = [ 1 0 0 ( x − 1 ) 2 ] B = [ 3 − 4 1 − 1 ] , SNF ( x I − B ) = [ 1 0 0 ( x − 1 ) 2 ] C = [ 1 0 1 2 ] , SNF ( x I − C ) = [ 1 0 0 ( x − 1 ) ( x − 2 ) ] . {\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, поскольку нормальная форма Смита характеристических матриц не совпадает.

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

Примечания

  1. ^ Стэнли, Ричард П. (2016). «Нормальная форма Смита в комбинаторике». Журнал комбинаторной теории . Серия A. 144 : 476–495. arXiv : 1602.00166 . doi : 10.1016/j.jcta.2016.06.013 . S2CID  14400632.
  2. ^ Мацейовски, Ян М. (1989). Многовариантный дизайн обратной связи . Wokingham, Англия: Addison-Wesley. ISBN 0201182432. OCLC  19456124.
  3. ^ "Время вычисления нормальной формы Смита в Maple". MathOverflow . Получено 2024-04-05 .

Ссылки

  • Смит, Генри Дж. Стивен (1861). «О системах линейных неопределенных уравнений и сравнений». Phil. Trans. R. Soc. Lond. 151 (1): 293–326. doi :10.1098/rstl.1861.0016. JSTOR  108738. S2CID  110730515.Перепечатано (стр. 367–409) в The Collected Mathematical Papers of Henry John Stephen Smith, Vol. I, под редакцией JWL Glaisher . Oxford: Clarendon Press (1894), xcv +603 стр.
  • Нормальная форма Смита на PlanetMath .
  • Пример нормальной формы Смита на PlanetMath .
  • KR Matthews, Нормальная форма Смита. MP274: Линейная алгебра, Конспект лекций, Университет Квинсленда, 1991.
  • Анимированный пример вычисления нормальной формы Смита.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Smith_normal_form&oldid=1248686978"