Введение

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

Определение

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

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

где (называемый i-м детерминантным делителем) равен наибольшему общему делителю детерминантов всех миноров матрицы и .
Пример: Для матрицы , с и .

Алгоритм

Первая цель — найти инвертируемые квадратные матрицы и такие, чтобы произведение было диагональным. Это самая сложная часть алгоритма. После достижения диагональности становится относительно легко привести матрицу к нормальной форме Смита. Если выразиться более абстрактно, цель состоит в том, чтобы показать, что, рассматривая как отображение из (свободного модуля ранга ) в (свободного модуля ранга ), существуют изоморфизмы и такие, что имеет простую форму диагональной матрицы. Матрицы и можно найти, начав с единичных матриц подходящего размера и изменяя их каждый раз, когда в алгоритме выполняется операция над строкой, соответствующей операцией над столбцом (например, если к строке прибавляется строка , то из столбца следует вычесть столбец , чтобы сохранить инвариант произведения), и аналогично изменяя для каждой выполненной операции над столбцом. Поскольку операции над строками — это левое умножение, а операции над столбцами — правое умножение, это сохраняет инвариант , где обозначают текущие значения, а — исходную матрицу; в конечном итоге матрицы в этом инварианте становятся диагональными. Выполняются только инвертируемые операции над строками и столбцами, что гарантирует, что и остаются инвертируемыми матрицами. Для обозначим число простых множителей (они существуют и единственны, поскольку любая область главных идеалов также является областью однозначной факторизации). В частности, также является областью Безу, поэтому это область НОД, и НОД любых двух элементов удовлетворяет тождеству Безу. Чтобы привести матрицу к нормальной форме Смита, можно неоднократно применять следующее, где проходит от 1 до .

Шаг I: выбор опорного пункта

Выберите наименьший индекс столбца с ненулевым элементом, начиная поиск со столбца с индексом , если требуется получить ; если это так, то этот шаг завершен, иначе, по предположению, существует элемент с , и мы можем поменять местами строки и , тем самым получив . Наш выбранный ведущий элемент теперь находится в позиции .

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

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

Приложения

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

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

Нормальная форма Смита матрицы размера N x N, A, может быть вычислена за время Если матрица разрежена, вычисления обычно выполняются значительно быстрее.