Построение нормальной диагональной формы Смита.

В этом разделе покажем эквивалентность матрицы A и ее нормальной диагональной формы Смита. Для этого потребуются следующие свойства.

1. Произведение унимодулярных матриц является унимодулярной матрицей

2. Перестановка i-ой и j-ой строк матрицы эквивалентна ее умножению слева на унимодулярную матрицу P. Матрица P получается из единичной матрицы перестановкой i-ой и j-ой строк.

3. Прибавление к j-ой строке i-ой строки умноженной на целое число t эквивалентно умножению матрицы слева на унимодулярную матрицу P. Матрица P отличается от единичной матрицы только одним элементом, расположенном на пересечении j-ой строки и i-го столбца, и равного t.

4. Перестановка i-го и j-го столбцов матрицы эквивалентна ее умножению справа на унимодулярную матрицу P. Матрица P получается из единичной матрицы перестановкой i-го и j-го столбцов.

5. Прибавление к j-ому столбцу i-го столбца умноженного на целое число t эквивалентно умножению матрицы справа на унимодулярную матрицу Q. Матрица Q отличается от единичной матрицы только одним элементом, расположенном на пересечении i-ой строки и j-го столбца, и равного t.

6. При всех перечисленных выше преобразованиях (2-5) ранг матрицы и наибольший общий делитель ее миноров k-го порядка не изменится.

Свойства 1-5 очевидным образом следуют из свойств определителя и правила умножения матриц. Обсуждения требует только свойство 6. Пусть матрица B получена из матрицы A в результате одного из преобразований, описанного в свойствах 2-5. Любой минор k-го порядка матрицы B является либо соответствующим минором k-го порядка матрицы A, либо комбинацией (с целыми коэффициентами) миноров k-го порядка матрицы A. В любом случае он делится без остатка на . Отсюда вытекает, что делится без остатка на . Поскольку матрица A может быть получена из матрицы B в результате аналогичных преобразований, то делится без остатка на . Следовательно , что и требовалось показать.

Теперь опишем алгоритм построения нормальной диагональной формы Смита матрицы A размерами m на n.

Шаг 1. Положим k=1.

Шаг 2. Если для всех и справедливо равенство , то алгоритм работу закончил. Иначе перейдем на шаг 3.

Шаг 3. Найдем i и j ( , ) для которых элемент наименьший по абсолютной величине и отличен от нуля. Переставим строки k и i, и столбцы k и j. Перейдем на следующий шаг.

Шаг 4. Если для каждого i ( ) справедливо равенство , то перейдем на следующий шаг. В противном случае вычтем из i-ой строки k-ю строку умноженную на ближайшее целое к ( ) и вернемся на шаг 3.

Шаг 5. Если для каждого j ( ) справедливо равенство , то перейдем на следующий шаг. В противном случае вычтем из j-го столбца k-ый столбец умноженный на ближайшее целое к ( ) и вернемся на шаг 3.

Шаг 6. Если найдутся i и j ( , ), что не делится без остатка на , то прибавим к k-ому столбцу j-ый столбец и вернемся на шаг 4. Иначе положим и вернемся на шаг 2.

Конечность описанного алгоритма следует из монотонного убывания по абсолютной величине элемента .

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

Описанный алгоритм не является эффективным из-за возможного роста промежуточных величин.