Глухов М. М. Алгебра том 1 (1016678), страница 22
Текст из файла (страница 22)
Эквивалентные матрицы О п р е д е л е н и е 11. Элементарными преобразованиями строк матрицы А Е ВР, „называют: 1) умножение любой ее строки на обратимый элемент кольца Л; 2) прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца В. Аналогично определяются элементарные преобразования стиолбцов матрицы А.
Элементарным и преобразованиями матр ицы называют элементарные преобразования ее строк и столбцов. Покажем, что элементарные преобразования строк (столбцов) матрицы можно осуществить путем умножения ее слева (справа) на подходящие квадратные обратимые матрицы. У т в е р ж д е н и е 5. а) Умножение г-й строки (г-го столбца) матрицы А Е ВР,,„на т равносильно умножению А слева (,справа) на матрицу Р® (т) (Р(') (т) ), где Р~~') Я = с!1ад(е,..., т,..., е))р „)р. б) Прибавление к г-й строке (г-му столбцу) матрицы А ~ Д „произведения ее )'-й строки Ц-го столбца) на т е Л, при )' ф г равносильно умножению А слева (справа) на матрицу Т~"~) (т) (ТО")), где Т~("') (т) = Е~„)р + Е~~'„*~~ Я.
Доказывается утверждение непосредственной проверкой. О п р е д е л е н и е 12. Матрицы Р~~,'~(т) при т Е В* и Т)~('~)(с) при любом с Е Л и г ф ~ называются элементарными матрицами. Легко видеть, что матрицы Р~р (т) и Т~р ' (с) получаются путем соот(б) (б З') ветствующих элементарных преобразований единичной матрицы Е)р„)р.
(Проверьте! ) Так как ~Ра' (г)) = г, )Т~" (е)) = е и элемеиг г ибрагим, те элементарные матрицы обратимы. Легко видеть, что обратные для них матрицы также являются элементарными, а именно: Р(~)(т) — 1 Р(~)(т — 1) Т(~ ~)( )-1 Т(~ ~)( ) ~Проверьте!) О п р е д е л е н и е 13. Матрица В ~ ЛР,„, называется эквивалентной матрице А е В „, если она может быть получена из А с помощью конечной последовательности элементарных преобразований. Обозначение: В ° А. Из определения 13 видно, что эквивалентные матрицы имеют одни и те же размеры.
Следовательно, отношение ° является бинарным отношением на множестве ВР,,„. Укажем простейшие свойства этого отношения. У т в е р ж д е н и е б. а) Отношение ° является отношением эквивалентности на множестве К„,„. б) Если матрица В получена из А тберестановкой строк или столбцов, то В А. в) Если А,В Е ВР, „и А ° В, то существуют матрицы У Е Е В*, У е В„* „такие, что В = УА! .
г) Если матрицы А и В квадратные и А В, то !В~ = т~А!, где т — некоторый обратимый элемент кольца Л. П а) Свойства рефлексивности и транзитивности отношения очевидны. Для доказательства симметричности достаточно заметить, что 124 125 3'б к / аи аь~ аи ..аМ ...аи ..а~ч ..О...арф... ..О...а ...ар~...арф .. ЙаК(й ° ° ° А)зззхзз (20) 5. Заказ М 573. 129 128 в) Если А, В Е В„, „и А В, то существует обратимая матрица У Е Л*,з,„такая, что В = УА.
г) Если матрицы А, В квадратные и А ' В, то ~В~ = т~А1 где т— некоторый обратимый элемент кольца Л. П В некоторых случаях элементарные преобразования строк матриц могут помочь найти обратную матрицу для заданной обратимой матрица из Л„,„. У т в е р ж д е н и е 8. Пусть А — обратимая, а Š— единичная матрица из Я „. Если матрица В = (А,Е) строчно эквивалентна матрице В' = (Е, А'), то А' = А 1. П Из условия и утверждения 7в) имеем: В' = У(А,Е), где У Е е Л„* „. Так как У(А, Е) = (УА,УЕ), то УА = Е и У = А'. Отсюда и из следствия теоремы 7 получим А' = А 1. П Таким образом, для нахождения матрицы А 1 достаточно уметь обратимую матрицу А элементарными преобразованиями строк приводить к единичной матрице.
Заметим, что для решения последней задачи в общем случае (т. е. для матриц над произвольным кольцом В) алгоритм не известен. То же самое относится и к задаче распознавания эквивалентности матриц. Вместе с тем, для матриц над Ж алгоритмы решения указанных задач известны.
В частности, алгоритм распознавания эквивалентности матриц над Ж основан на преобразовании матриц к определенным каноническим матрицам. В главе Ч11 та же идея будет использована для матриц над полями. ~ 6. Канонические матрицы над кольцом Ж О п р е д е л е н и е 15. Канонической матрицей над кольцом Ж называется диагональная матрица в которой Б1,..., Б~ Е Ио и Чг Е 1, 1 — 1: Б, ~ Б,+1. П р и м е р 3.
Из трех матриц йаф1,2,4,0), Йаф1,0,2,4), йаф1,-2,4,0) первая — каноническая, две другие — нет. Нулевая матрица — каноническая. Теорем а9. Для любой матрицы А = (а, ) „„надЖ существует эквивалентная ей каноническая матрица. Предварительно введем обозначение р(Х) для минимального по модулю ненулевого элемента любой целочисленной матрицы Х ф О и докажем вспомогательное утверждение.
Л е м м а. Для любой ненулевой матрицы А = (а,5)„,з~„над Ж существует эквивалентная ей матрица В = (6, )„,„„, удовлетворяющая условию: Чг Е 1,т, Ч~ Е 1,п: р(В) ~ 6,5. (21) П Докажем лемму индукцией по ~р(А)~. Если ~р(А)~ = 1, то утверждение очевидно.
Допустим, что оно верно при ~р(А)~ ( И и пусть ~р(А)~ = И, где И Е И и й ) 1. Выберем в А элемент аи = р(А) и рассмотрим три случая. 1) Зэ Е 1, п: аи ~ а~,. Разделим а~, на аи с остатком: а~, = аио+ + т, 0 ( т ( ~аи~. Прибавив к э-му столбцу матрицы А ее К-й столбец, умноженный на — о, получим матрицу А' с элементом г на месте (й, э). Так как 0 < т ( ~аи~, то ~р(А')~ ( ~р(А) ~, и по предположению индукции существует матрица В со свойством (21), эквивалентная А', а потому и А.
2) ЗФ е 1,т: аи 1 а~у. В этом случае рассуждения аналогичны, вместо преобразования столбцов используются преобразования строк. 3) Чэ Е 1,и, И Е 1,т: аи ~ а~„аи~ ~ а~е. Допустим, что аи ~ арф. Прибавим й-ю строку матрицы А, умноженную на — арф/аи, к ее р-й строке, а затем р-ю строку полученной матрицы — к ее Й-й строке: В итоге получим матрицу А' = (а', ), в которой а~~е — — аи, а~~ — — арф+ +акц~1 — арф(аи) и аи 1 а~~,~, поскольку а~~е ~ а~д и а~~, 1 арф..Следовательно, для матрицы А' выполнено одно из условий: или ~р(А')~ < ~р(А)~, или р(А') = р(А) и тогда р(А') = а~~е и а~~,е ~ а~~, .
Отсюда видно, что для матрицы А', а потому и для А, искомая матрица В существует или по предположению индукции, или по доказанному в случае 1). П ь ...о...о 0 Ьгг ..Ьг , гдеВ'= Вд = В' ьттвг ' ' ьттвв При этом Вд А, и по теореме 8 Ьы ~ Ь'," для всех д Е 2, т, ~ Е 2, п. По предположению индукции матрицу В' можно элементарными преобразованиями привести к канонической матрице Йад(бг,..., 6~) ~ д1„~„д1. Осуществляя соответствующие преобразования над строками и столбцами матрицы Вд, получим матрицу йац(Ьдд,дг,...,б~) „„= Р, удовлетворяющую по теореме 8 условию Ьдд ~ 6;, д Е 2, ~.
А так как Р А, то матрица Р— искомая. П Заметим, что доказательство теоремы 9 конструктивно. Из него легко извлекается алгоритм нахождения канонической матрицы, эквивалентной А. Алгоритм этот допускает вариации, связанные с неоднозначным выбором минимального по модулю элемента и не делящихся на него элементов в промежуточных матрицах. Вместе с тем, ниже будет доказано принципиально важное утверждение о единственности канонической матрицы, эквивалентной А.
Для этого понадобятся некоторые вспомогательные факты. О п р е д е л е н и е 16. Пусть А Е У „, 1 = дпдп(т,п) и й Е 1, 1. Инвариантным делителем й-го порядки, или й-м инвариантным делителем, матрицы А называется число Ид,(А), равное неотрицательному НОД всех миноров й-го порядка матрицы А. П Теперь докажем теорему 9 индукцией по т+ п. Заметим, что для нулевой матрицы А утверждение верно. Поэтому далее будем считать, что А ф О. Если т+ п = 2, то т = п = 1, и утверждение теоремы очевидно. Допустим, что оно верно при т+ п < й, и пусть т+ п = й, где й Е 1Ч и Й > 1. По лемме существует матрица В со свойством (21), эквивалентная А. Не теряя общности, можно считать, что ~р(В)~ = Ьдд, ибо этого можно добиться перестановками строк и столбцов (что, согласно утверждению 6, осуществимо с помощью элементарных преобразований) и умножением 1-й отроки на — 1.
Прибавив к д-й строке матрицы В ее 1-ю строку, умноженную на — Ь,д/Ьдд, для всех д е 2,т, а затем к д'-му столбцу — 1-й столбец, умноженный на — Ьд /Ьц для всех ~ Е 2, и, получим матрицу вида Заметим, что в силу следствия 1 теоремы Лапласа числа 4(А) удовлетворяют условию: % Е 1, ~ — 1: сЦ(А) ~ 4+д(А). (Докажите!) Оказывается, набор чисел (Ид(А),...,4(А)) является инвариантом класса всех матриц, эквивалентных А, а именно, справедливо У т в е р ж д е н и е 9. У эквивалентных матриц над У инвариантные делители одинаковых порядков равны. П Пусть А ° В,И~(А) = И,й~(В) = И'. Тогда по теореме 8 имеем: в' ~ И' и И' ~ И.
Отсюда, учитывая, что И > О, И' > О, получим И = И'. П У т в е р ж д е н и е 10. Если Р = йа~(бд,...,4) — каноническая матрица над У, то для любого й Е 1, ~ справедливо равенство (22) А~(Р) = бд...бд-.. И~ (А)/И~ д (А), если И~ д (А) ф О, Ь= О, если Иу, д~А) = О. Таким образом, элементы матрицы Р однозначно определяются мат- рицей А. П Из теорем 9, 10 следует, что корректно О и р е д е л е н и е 17. Каноническая матрица Жал(бд,..., Б~)~„„, эквивалентная матрице А е Ж~,„, называется канонической формой матрицы А и обозначается К(А). Элемент бд, этой матрицы называет- ся й-м инвариантным множителем матрицы А и обозначается через 6~(А),й Е 1,~. Таким образом, К(А) = йафдд(А) ° ° ° бй(А))тхв.
(23) П Легко видеть, что среди всех миноров й-го порядка матрицы Р не / дд...ц, д равными нулю могут быть лишь миноры Мд ~ . ' ' . ) = о,,... 6,, ~, дд ... дд- ) Отсюда и из условия о; ~ о;+д для д Е 1, 1 — 1 следуют соотношения од... Б~ ~ о;,...
Б,„, а потому — и равенство (22). П Теперь может быть доказана Т е о р е м а 10. Каждая целочисленная матрица А эквивалентна х,' единственной канонической матрице. П Если А эквивалентна канонической матрице (20), то по утверждению 10 для любого Й Е 1, $ справедливо равенство (22). Отсюда и из утверждения 8 имеем од — — Ид(А), и для й Е 2, 1: 130 131 В=УА~; (24) в) К(А) = К(В); г) й(А) = й(В) длп ппеп Й я 1, т1п~тп,п~; д) 6~(А) = 6~(В) для всех й е 1, ш1п(т, п). П Эквивалентность утверждений а), в), г), д) следует из существования и единственности канонической формы для любой матрицы над У и равенств (22), )',23).
Импликация а) ~ б) доказана утверждением б, и остается доказать импликацию б) ~ а). Пусть В = УАУ, где У, У вЂ” обратимые матрицы. Тогда по следствию 1 У и ~ представляются произведениями элементарных матриц. Отсюда и из утверждения 5 следует, что от А к В можно перейти с помощью конечной последовательности элементарных преобразований. Значит, А В. П С л е д с т в и е 4. Существует алгоритм, позволяющий для любых матриц А,В над У выяснять, эквивалентны они или нет, и в случае положительного ответа находить обратимые матрицы У, У, удовлетворяющие условию (24).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
