Линейная алгебра. Теоремы и алгоритмы. Яцкин Н.И. - 366 стр.

366    Спектральная теория линейных эндоморфизмов            Гл. 3

А л г о р и т м 30. 1.
Приведение полиномиальной матрицы
к канонической форме Смита

  Дана полиномиальная (m × n)-матрица A = A(λ). Образуем две
единичные матрицы U = U0 = Em и V = V0 = En . Каждое по-
следующее элементарное преобразование над строками (столбцами)
матрицы A дублируется на строках (столбцах) матрицы U (матри-
цы V ).

   1. В матрице A выбирается ненулевой многочлен наименьшей
степени и перемещается в северо-западный угол.
   2. Все остальные элементы первой строки и первого столбца, с
помощью приема Гаусса, заменяются на остатки от деления этих
элементов на угловой.
   2.1. Если все полученные остатки равны нулю, то переходим к
этапу 4.
   2.2. Если среди остатков есть ненулевые, то тот из них, степень
которого минимальна, отправляем в северо-западный угол и возвра-
щаемся к этапу 2.
   3. После конечного числа шагов типа 2 мы получаем нулевое
окаймление для подматрицы A0 = A0 (λ), расположенной в строках и
столбцах с номерами, начинающимися с двойки.
   3.1. Если все элементы подматрицы A0 делятся (без остатка) на
угловой элемент (для всей матрицы), то можно констатировать, что
первый и.м. µ1 (λ) отщеплен.
   3.2. Если же это пока не так, то приходится "портить" окаймле-
ние. Делим с остатком все элементы A0 на угловой элемент и прибав-
ляем к первой строке строку, содержащую наименьший по степени
остаток, после чего снова пытаемся обнулить окаймление (этап 2).
   Поскольку степень углового элемента при каждом его замещении
строго убывает, то рано или поздно будет достигнут первый успех —
отщепление µ1 (λ), после чего мы переходим к этапу 4.
   4. Приступаем к обработке блока A0 , повторяя все этапы, начиная
с первого.
   5. Работа алгоритма завершается, если
   — либо будет получен очередной и.м., расположенный в последней
строке (или в последнем столбце) матрицы; тогда останется обнулить
элементы справа от него (ниже его);