Н.И. Яцкин - Линейная алгебра (Теоремы и алгоритмы) (1109879), страница 62
Текст из файла (страница 62)
Однако невырожденность квадратной матрицы (т. е. максимальностьее ранга) уже не влечет теперь ее обратимость.Вообще вычисления с минорами приобретают особое значение,как важнейший метод в линейной алгебре над кольцами. Удобнобывает обобщить понятие минора следующим образом.Выберем в матрице (30.1) какие-либо s строк с номерами, составляющими мультииндекс (термин см.
в п. 48.1 пособия [A1 ])I = (i1 i2 ... is ); iα ∈ {1, ..., m} (1 6 α 6 s),(30.3)где номера iα не обязательно различны и не обязательно идут попорядку; аналогичным образом выберем s столбцов:J = (j1 j2 ... js ); jβ ∈ {1, ..., n} (1 6 β 6 s).(30.4)Рассмотрим (s × s)-матрицу, составленную из элементовaiα jβ (λ); 1 6 α, β 6 s.Определитель этой матрицы называется обобщенным минором порядка s для матрицы A и обозначаетсяµ ¶AIJµ=Ai1j1i2j2... is... js¶.(30.5)362Спектральная теория линейных эндоморфизмовГл. 3(Для краткости зависимость от λ не показывается.)"Настоящие" миноры выделяются тем, что мультииндексы I и Jявляются строго возрастающими. В силу свойств определителей очевидны следующие свойства обобщенных миноров:— в случае наличия (в числе выбранных) повторящихся строк илистолбцов обобщенный минор будет нулевым;— если элементы любого из задействованных мультииндексов подвергнуть некоторой перестановке σ, то это повлечет умножение значения минора на sgn(σ).Незаменимым инструментом в полиномиальной линейной алгебреоказывается так называемая формула Бине — Коши (справедливая,конечно, и в обычной ситуации, над полем), которая выражает миноры для произведения матриц через миноры матриц-сомножителей.ЕслиC = A · B ,m×pm×nn×pто для любого натурального s, не превышающего min(m, p), и длялюбых двух строго упорядоченных мультииндексов, I [см.
(30.3)] иK = (k1 k2 ... ks ); kγ ∈ {1, ..., p} (1 6 γ 6 p),справедливо равенствоµ ¶ X µ ¶µ ¶IIJC=A·B,KJJK(30.7)(30.8)где суммирование ведется по всем строго упорядоченным мультииндексам вида (30.4).(При s > n таких мультииндексов J нет. Тогда оказывается, чтовсе миноры порядка s в матрице C являются нулевыми.)Далее вводится (уже специфически кольцевое) понятие НОДМ’ов(наибольших общих делителей всех миноров заданного порядка вполиномиальной матрице A):d(A)s (λ) == НОД {Aµ ¶IJ(λ) : I, J − мультииндексы длины s},(30.9)где s 6 min(m, n) и все НОД берутся в кольце многочленов P [λ],причем — нормализованными (напомним, что благодаря последнемуусловию они определены однозначно).§ 30Каноническая форма Смита полиномиальной матрицы 363Обратим внимание на то, что первый из НОДМ’ов, d(A)1 (λ), естьне что иное, как НОД всех элементов матрицы A, и введем (по определению, с целью достижения единообразия в записи последующихформул) нулевой НОДМ: d(A)0 (λ) = 1.С помощью теоремы Лапласа о представлении определителя разложением по строке (столбцу) легко доказывается следующее свойство НОДМ’ов:(A)d(A)(30.10)s−1 (λ) | ds (λ); s = 1, ...
, r,где r = rank(A(λ)).При r+1 6 s 6 min(m, n) все НОДМ’ы обращаются в нуль. Такимобразом, ранг матрицы (над кольцом многочленов) можно охарактеризовать, как номер последнего ненулевого НОДМ’а.30.2. Каноническая форма Смита и эквивалентность полиномиальных матриц. Элементарные преобразования над строками и столбцами полиномиальной (m × n)-матрицы A = A(λ) типовI — III определяются вполне аналогично случаю матриц над полем(см. пп.
4.3 и 14.3 в пособии [A1 ]).Опишем преобразования над строками:I: iстр ↔ j стр ; i, j ∈ {1, ..., m}; i 6= j;II: iстр + j стр · c(λ); i, j ∈ {1, ..., m}; i 6= j; c(λ) ∈ P [λ];III: iстр · c; i ∈ {1, ..., m}; c ∈ P \ {0}.Для столбцов все точно так же. "Кольцевая специфика" просматривается в преобразованиях третьего типа: любую строку (любойстолбец) полиномиальной матрицы можно домножить на обратимый многочлен, т. е. — на ненулевую константу.Две полиномиальные матрицы, A = A(λ) и B = B(λ), одинаковых размеров, называются эквивалентными [используется знакомоеобозначение: A(λ) ∼ B(λ)], если от одной из них можно перейти кдругой за конечное число шагов, каждый из которых является элементарным преобразованием над строками или столбцами одного изтрех описанных выше типов.Элементарные преобразования над строками (столбцами) (m×n)матрицы A(λ) могут быть реализованы как умножение этой матрицы слева (справа) на соответствующие элементарные матрицы,описание которых ничем (кроме того, что скалярами теперь служатмногочлены) не отличается от приведенного в пп.
14.3, 14.4 первогопособия.364Спектральная теория линейных эндоморфизмовГл. 3По-прежнему элементарные матрицы оказываются обратимыми(их определители являются ненулевыми константами). Чтобы "отследить" всю цепочку элементарных преобразований над строками, формируется обратимая полиномиальная матрица U (λ) размераm × m, которую можно получить, дублируя каждое из преобразований над строками A(λ) точно таким же преобразованием над строками единичной матрицы Em .
Аналогично, элементарные преобразования над столбцами "накапливаются" в обратимой (n × n)-матрице V (λ).В результате эквивалентность матрицA(λ) ∼ B(λ)(30.11)оказывается выраженной соотношениемB (λ) = U (λ) · A (λ) · V (λ),m×nm×mm×nn×n(30.12)с обратимыми полиномиальными матрицами U (λ) и V (λ).[Из формулируемой ниже теоремы 30.2 будет следовать тот факт,что (30.12), в свою очередь, влечет (30.11). С учетом этого, вы можете сравнить исследуемое здесь понятие эквивалентности матрицнад кольцом многочленов с ранее изученным (см.
п. 13.3 настоящего пособия) понятием эквивалентности матриц над полем. Особоевнимание обратите на предложение 13.3; в теореме 30.2 оно получиточень интересное и нетривиальное обобщение.]Далее, с помощью формулы Бине — Коши (30.8), легко устанавливается, что эквивалентные полиномиальные матрицы имеют равныеранги и их соответствующие НОДМ’ы одинаковы, т. е.
(30.11) влечетrank(A(λ)) = rank(B(λ)) (= r)(30.13)(B)(∀s = 1, ... , r) [d(A)s (λ) = ds (λ)] .(30.14)иСправедливость обратного утверждения также будет зафиксирована ниже, в теореме 30.2.А пока мы обратимся к формулировке еще одной из наиболеепринципиальных и важных теорем линейной алгебры.§ 30Каноническая форма Смита полиномиальной матрицы 365Теорема 30.1 (теорема Смита).
Всякая полиномиальная матрица A(λ) ∈ Mat(m, n, P [λ]) эквивалентна однозначно определеннойматрице вида µ (λ)1µ2 (λ)S(λ) = ...µr (λ),(30.15)где r = rank(A(λ)), а многочлены µs (λ) = µ(A)s (λ) (где s = 1, ... , r)являются нормализованными, связаны соотношениями делимостиµs (λ) | µs+1 (λ); s = 1, ...
, r − 1(30.16)и могут быть выражены через НОДМ’ы:µ(A)s (λ) =ds(A) (λ); s = 1, ... , r.d(A)(λ)s−1(30.17)Доказательство (набросок). Сразу введем терминологию, принятую в теории полиномиальных матриц. Матрица (30.15) называется канонической формой Смита для данной матрицы A = A(λ).Элементы, стоящие на ее диагонали, называются инвариантнымимногочленами (или инвариантными множителями) (и.м.) для A.Важнейшую часть доказательства теоремы составляет описаниеалгоритма Смита, основанного на взаимодействии двух других алгоритмов (которые мы уже изучили и которые по праву считаютсяосновой всей алгебраической алгоритмики).
Речь идет об алгоритмеГаусса приведения матрицы к ступенчатому (и далее — скелетному)виду и алгоритме Евклида вычисления наибольшего общего делителя двух многочленов.Подробно ознакомиться с алгоритмом Смита можно по уже упомянутой в начале параграфа учебной литературе. К этому перечнюмы добавим здесь небольшую (но чрезвычайно насыщенную информацией) книгу [18], содержащую весьма лаконичное доказательствотеоремы Смита. (Именно его — еще более краткий — пересказ приводится ниже.)366Спектральная теория линейных эндоморфизмовГл.
3А л г о р и т м 30. 1.Приведение полиномиальной матрицык канонической форме СмитаДана полиномиальная (m × n)-матрица A = A(λ). Образуем двеединичные матрицы U = U0 = Em и V = V0 = En . Каждое последующее элементарное преобразование над строками (столбцами)матрицы A дублируется на строках (столбцах) матрицы U (матрицы V ).1. В матрице A выбирается ненулевой многочлен наименьшейстепени и перемещается в северо-западный угол.2. Все остальные элементы первой строки и первого столбца, спомощью приема Гаусса, заменяются на остатки от деления этихэлементов на угловой.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
