Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 90

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 84 85 86 87 88 89 < 90 > 91 92 93 94 95 96 .. 371 >> Следующая

(-1)
к-1
U = D (ЛЕГ1 = W '<*
(4.15) следует, что Ви = 0 (mod f!ft)t поэтому ftBij делится на /, и
каждый элемент матрицы U является многочленом над по-лем f д. Кроме того,
det (U) - det ^ = 1~~1 1
det (Л?) det(?) *
т' е. det (U) - ненулевой элемент поля Fg. Значит, U - унимо-Дулярная
матрица нз многочленов. ?
Теорема 4.12 обеспечивает теоретическую возможность нахождения
неприводимых делителей многочлена f путем приведения матрицы Л к
диагональному виду. Сама же матрица Л (число к и многочлены А*, hk из ее
первого столбца) относительно легко троится с помощью алгоритма
Берлекэмпа. Однако алгоритм, с помощью которого производится
днагоналнзацня матрицы Л, Довольно сложен.
208
Гл. 4, Разложение многочленов на множители
•"ЦрйяЗ
Алгоритм диагонализации основан на применении следую элементарных
преобразований: (i) перестановки любой пары ст (столбцов) матрицы; (ii)
умножения любой строки (столбца) любой элемент группы (iii) умножения
любой строки (столб на произвольный элемент поля ЕГд и прибавления
результ к любой другой строке (столбцу).
Элементарные преобразования для строк можно осуществи умножением исходной
матрицы слева на подходящим обра выбранную унимодулярную матрицу из
многочленов, тогда элементарные преобразования для столбцов можно
осуществи умножением исходной матрицы справа на подходящим образ
выбранную невырожденную матрицу с элементами из fq этому новая матрица,
получаемая применением любого элем тарного преобразования, всегда
эквивалентна исходной рице.
Можно показать, что матрица А эквивалентна такой матри из многочленов,
что для каждой ее строки степень диагональн элемента больше степеней
остальных элементов строки. Тащ матрицу R можно получить из .4, произведя
не более (2Д + k •(k - 1) элементарных преобразований, где Д = deg (ht)
deg (hk).
Заметим, что диагональные элементы матрицы R можно п ставлять, производя
соответствующую перестановку строк столбцов. Таким образом мы можем
получить матрицу S, котор обладая всеми свойствами матрицы /?, обладает
следующим полнительным свойством; deg (su) ^ deg (sjf) для 1 < / << } где
sn - диагональные элементы матрицы S. Кроме того, ум жением строк матрицы
S на подходящие элементы из мо добиться, чтобы многочлены su были
нормированными. Матриц^ из многочленов, обладающую всеми этими
свойствами, будем зывать нормализованной матрицей.
Диагональные элементы матрицы D из теоремы 4.12 тоже мо переставить так,
чтобы выполнялись неравенства deg (/*) ^ deg для 1 с t < / с А. В
результате мы получим эквивалентй матрицу, которую тоже обозначим D и
которая будет диагона ной и нормализованной. Можно показать, что из
эквивалентн нормализованных матриц S и D вытекает, что deg (su) - deg для
всех i, 1 < i < k. Отсюда следует, что степени различных приводимых
делителей многочлена f совпадают со степенями диЩ| нальных элементов
матрицы S. Более того, если натураль число d является степенью некоторого
диагонального элеме (многочлена) 5ц матрицы S и если SH> - квадратная
подматр матрицы 5, главная диагональ которой состоит как раз из тех
многочленов $и, степени которых равны d, то можно показу что определитель
матрицы равен определителю соответстй; щей подматрицы D{d) матрицы Ь.
Поэтому det (S(d)) •
§ 2. Разложение многочленов над большими конечными полями 209
есть произведение всех многочленов степени d. Таким образом мы приходим к
частичному разложению миогочлеиа f\
f = n?d> (4.16)
d
где произведение берется по всем натуральным числам d, являющимся
степенями неприводимых делителей ft многочлена f.
В итоге матрица S позволяет получить следующие сведения о нормированных
неприводимых сомножителях ft многочлена f: узнать степени этих
сомножителей, число всех сомножителей данной степени и произведение всех
сомножителей данной степени, Поэтому если степени всех сомножителей
различны, а это значит, что различны степени всех диагональных элементов
(многочленов) 8ц матрицы S, то разложение (4.16) уже является
каноническим разложением f в Fg [х).
Но если разложение (4.16) еще не является каноническим разложением
многочлена /у то мы можем продолжить его несколькими путями. Например,
можно применить один из рассмотренных ранее методов для разложения
многочленов^. А можно продолжать алгоритм диагонализации с тем, чтобы в
итоге получить диагональную матрицу D, эквивалентную нормализованной
матрице 5.
Выберем второй путь и будем считать, что матрица D имеет нормализованный
вид. К упомянутым выше свойствам матрицы S ' можно добавить еще одно, а
именно что каждая ее подматрица эквивалентна соответствующей подматрице
матрицы D. Поэтому достаточно диагонализировать каждую такую подматрицу
отдельно. В силу эквивалентности матриц > и Dнайдутся такие унимодулярная
матрица из многочленов U и невырожденная матрица Е с элементами из поля
Fg, что - UD^E. Мы можем тогда записать
S"0 =. Sid) + S{d) SjV,
?/ = ?/e+?/i*+ +!/"**,
D^= D(0d) + D\d)x H + DSV,
где D(d) и Ut, 0 < r < d,-0 <. t <. m, - матрицы с элементами из поля Fg,
Предыдущая << 1 .. 84 85 86 87 88 89 < 90 > 91 92 93 94 95 96 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed