Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 48
Текст из файла (страница 48)
4.10. Определение. Квадратную матрицу из многочленов будем называть нееырождеиной, если ее определителем является ненулевой многочлен, и унимодулярно~1, если ее определителем является ненулевой элемент поля Гл. 4. Рааложеиие многочленов иа множители г, О, . О О!а ... О В= ОО...(а эквивалентна матрице из многочленов О О й, — 1 О й, Π— 1 О О О Доказательство.
Из рассуждения, следующего из (4.3), кает, что существуют элементы еы ~ Г», такие, что !е, (х) ' : — ец (шое) ~» (х))„1 ~ 1, ! ( й. Обозначйм я х к-матрицу (ег через Е. Покажем, что матрица Е невырожденна. Если бы было не так, то существовали бы такие элементы й» ..., ад б !!'" не все равные нулю, что ~~ й»е» = О, !' = 1, ..., й. »=! 4.11. Определение. Квадратные матрицы из многочленов: и 4~ будем называть эквивалентными, если существуют та ' унимодулярная матрица из многочленов У и невырожден матрица Е с элементами из поля Г», что Р = УОЕ. Легко проверить, что введенное нами понятие эквивалентн матриц из многочленов действительно является отношением эк валентности в том смысле, что оно рефлексивно, симметрично, транзитивно. Мы видели в Э 1, что существуют миогочлены йе „, !га ' Е Г» (х), О < е(ед(й;) < е!ей(!), ! = 2, ..., А, которые вм ' с Ь, (х) = ! являются линейно независимыми над полем !Г шениями сравнения й» г— е Ь (щое! )').
Ясно, что многочленй, можно выбрать нормированными. Следующая теорема являет' основополагающей. й 4.12. Теорема. Пусть ! = ~, ... !ю где ~„..., !в — разли нормированные неприводимые многочлены из Г» (х), и п й„..., йь Е г !х) — нормированные много»лены сте <дед Д), которые вместе с Ьг =- 1 являются линейно независи над полем Ке Решениами сРавнениЯ й» =- й (шод(). Тогда ди пильпая матрица из миогочленов 4 2, Разложение многочленон над оольшнмн конечными полнмн 207 Зто означало бы, что Е г(А = — 0(тощ, 1=1„..., ь, Е=1 откуда следовалобы, что ~ 46~ = 0 (пгоб 7). Нотак какг(ей (й,)( з=! -- бек ф для всех!, 1 ~ 1 ~ й, то на самом деле мы получили бы равенство ~а бзй, = О, которое противоречит линейной незави- ~.=! самости многочленов й, ..., Ьь. Теперь заметим, что АЕ является невырожденной матрицей нз многочленов, так как де( (АЕ) = ( — 1)" — '7 сне! (Е).
Поэтому мы можем написать Р = (Р (АЕ)-') АЕ, и теорема будет доказана, как только мы покажем, что У = Р (АЕ) ' является унимодуляр- ной матрицей из многочленов. Пусть АЕ = (Ьм), где Ьгт ~ Гч (х). Тогда, так как Ь, = 1, то Ьы - — — ~е,~ — — 1' : — 0 (пгоб );) для 1 ( ! ~ й, а для 2 ~ ! ~ й имеем Ьм — — й;еы — еы = йг — е„= 0 (той ~г) при 1 ( !' ~ й, так что Ьы = 0(той(т) для всех ! ~ 1, !' ай. (4.!5) Далее, 1 ( — г!"-' (АЕ) з =, ( (Вп)1<ь1<ь =, ( (ВО)ьнь 7 -а, где „— алгебраическое дополнение элемента Ьы матрицы АЕ, так что У = Р(АЕ) аеГ(Е)1 (Д~Вй)1 г, Г~ь ( — !) Из (4.15) следует, что Вы = — 0 (юона Я), поэтому ~;В;; делится на 1, и каждый элемент матрицы У является многочленом над полем Гч.
Кроме того, де! (В) ( — 1)~ бе!(Р) = нег(АЕ) = нег(н) т е. Йе! (Р) — ненУлевой элемент полЯ Кч. Значит, У вЂ” Унимодулярная матрица из многочленов. П Теорема 4.12 обеспечивает теоретическую возможность нахождения неприводимых делителей многочлена 7' путем приведения "атрицы А к диагональному виду. Сама же матрица А (чнсло й и многочлены 6„..., йа из ее пеРвого столбца) относительно легко '~роится с помощью алгоритма Берлекэмпа.
Однако алгоритм, с помощью которого производится диагонализация матрицы А, довольно сложен. 208 Гл. 4. Разложение многочленон иа множители Алгоритм диагонализации основан на применении следую элементарных преобразований: (!) перестановки любой пары ст (столбцов) матрицы; (й) умножения любой строки (столбца) -.' любой элемент группы 1';; (ш) умножения любой строки (столб ' на произвольный элемент поля Г, и прибавления результ к любой другой строке (столбцу). Элементарные преобразования для строк можно осуществ'" умножением исходной матрицы слева на подходящим обра '' выбранную унимодуляриую матрицу из многочленов, тогда элементарные преобразования для столбцов можно осуществ)( умножением исходной матрицы справа иа подходящим обра выбранную невырожденную матрицу с элементами из этому новая матрица, получаемая применением любого эле тарного преобразования, всегда эквивалентна исходной рице. Можно показать, что матрица А эквивалентна такой матриц из многочлеиов, что для каждой ее строки степень диагональн '" элемента больше степеней остальных элементов строки.
Так матрицу т( можно получить из А, произведя не более (2Л + й— . (й — 1) элементарных преобразований, где Л --= бед (йе) +. ... + дед (Ьа). Заметим, что диагональные элементы матрицы Я можно пе ставлять, производя соответствующую перестановку строк и„ столбцов. Таким образом мы можем получить матрицу 5, котор ' обладая всеми свойствами матрицы )1, обладает следую|цим полнительным свойством: дед (зи) ) е)ей (зы) для 1 < ! <,1 й ' где зи — диагональные элементы матрицы 5. Кроме того, ум жением строк матрицы 5 на подходящие элементы из Ц мож добиться, чтобы многочлены зи были нормированными. Матрицу из многочленов, обладающую всеми этими свойствами, будем зывать нормализованной матрицей, Диагональные элементы матрицы 1л из теоремы 4.12 тоже мо переставить так, чтобы выполнялись неравенства с)ед (1;) =- бей для 1 < 1(1 < я.
В результате мы получим эквивалентн матрицу, которую тоже обозначим О и которая будет диагона ной и нормализованной. Можно показать, что из эквивалентн нормализованных матриц 5 и В вытекает, что бед (зн) — бей для всех 1, 1 < ! < и. Отсюда следует, что степени различных ' приводимых делителей многочлена ) совпадают со степенями дна нальных элементов матрицы 5. Более того, если натураль число й является степенью некоторого диагонального элем (многочлеиа) эн матрицы 5 и если 500 — квадратная подматр матрицы 5, главная диагональ которой состоит как раз из тех многочленов зи, степени которых равны д, то можно показа что определитель матрицы 5ы> равен определителю соответству щей подматРнцы О<ю матРицы Е).
ПоэтомУ йе1 (5ы>) = йл, где. 4 2, Разложение миогочленон над большнмн нонечнымн полями 209 ,сть пРоизвеление всех многочленов 1< степени <1. Таким обРазом мы приходим к частичному разложению многочлена 1: 1=Пй,, (4.16) где произведение берется по всем натуральным числам <1, являющимся степенями неприводимых делителей Г< многочлена 1.
В итоге матрица 5 позволяет получить следующие сведения о нормированных неприводимых сомножителях 1< многочлена Р: узнать степени этих сомножителей, число всех сомножителей данной степени и произведение всех сомножителей данной степе<ш.
Поэтому если степени всех сомножителей 1< различны, а это значит, что различны степени всех диагональных элементов (многочлеиов> зп матрицы 5, то разложение (4.16) уже является каноническим Разложением 1 в Гч (х1. Но если разложение (4.16) еще не является каноническим разложением многочлена Г, то мы можем продолжить его несколькими путями. Например, можно применить один из рассмотренных ранее методов для разложения миогочленов яа. А можно продолжать алгоритм диагонализации с тем, чтобы в итоге получить диагональную матрицу Р, эквивалентную нормализованной матрице 5. Выберем второй путь и будем считать, что матрица В имеет нормализованный вид. К упомянутым выше свойствам матрицы 5 можно добавить еще одно, а именно что каждая ее подматрица 5<"> эквивалентна соответствующей подматрице В<а> матрицы Р.
Поэтомудостаточно диагонализироватькаждуютакую подматрицу 5<и> отдельно. В силу эквивалентности матриц 5<а> и О<"> найдутся такие унимодулярная матрица из многочленов и и невырожденпая матрица Е с элементами из поля Кч, что 5<а> = иВ<">Е. <'(ы можем тогда записать 5<и> = 5,' '+ 5"'х+ + 5' 'х, и =- и, + и,х+ " + и„х-, О< >= В' '+ О,' >х+ .
+ Вн< >х, где 5~~>, 0<~> и и<, 0 ~ г а <1, 0 ~ 1 а т, — матрицы с элементами из поля г„и ~0 и 5л"> = Влю — — 1 — единичные матрицы соответствующего порядка. Сравнение матричных коэффи'<нентов при высших степенях переменной х в обеих частях равенства 5<~> = иВ<л>Е дает! = и 7Е, так что т = О. Поэтому и==и,=Е- и 5<а>=Е-В Е." Сравнивая матричные коэффициенты при одинаковых степенях переменной х в последнем равенстве, получаем 5~~> = Е 'В<">Е для всех г, 0 ~ г ~ <(.
Следовательно, матрицы 5<а> и О,'"' имеют зан. 222 210 Гл. 4. Рааложеине нногонленои иа л1ножители одинаковые характеристические многочлены, а значит, и один вые собственные значения; кроме того, поскольку В, — диа' оо нальная матрица, то ее собственные значения совпадают с ее гональнымн элементами. Поэтому эти диагональные элеме' можно найти как корни характеристического многочлена матри 5~~', причем все они должны принадлежать полю [Г . Таким об' зом, мы снова, как и в предыдущих способах, сводим проба ' разложения многочлена [ к задаче отыскания корней некотор'" многочленов в поле [['е.
Частичное разложение (4.16) можно получить также со другим способом. Расширим определение многочленов йш об чая через а„д =- 1, произведение всех нормированных непри димых многочленов степени д из Ке [х1, которые делят мн член Г. В частности, д; (х) = 1 в том случае, если многочле не имеет в кольце [['е [х! неприводимых дечителей степени:;" Тогда мы можем напйсать 1= П~, д~1 Ясно, что нужно рассматривать лишь те значения д, которые„ превосходят бед (1). Будем теперь, исходя из равенств г,(х) =х, ге(х) =Г(х), последовательно находить многочлены г (х), г (х), ..., а та ге (х), гд (х), ...
и д(д (х), д(а (х), ..., используя для д « 1 след' щие рекуррентные соотношения: гд(х) = гд д(х)е(пки[гд д(х)), д[ед(г,) < г[еи(гд д), г[д (х) = НОД(г"д д(х), г, (х) — х), гд (х) = и"д д (х)н(д (х). ! Этот процесс заканчивается, когда д; (х) = гд д (х). 4.13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
