Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 33
Текст из файла (страница 33)
Отсюда следует, что ~~~~~ ЬйЯ = ~ЕЬй(!й~ =О для 1=0, 1, ..., п, й=! й=! так что первые и строк определителя, представляющего много- член Р (х), линейно зависимы над Кч, Поэтому 0 (х) = О, и равенство (3.14) выполняется в любом случае. Отсюда получаем л о„„=оо„„!= о„п !鄄— И,,й„), что и доказывает формулу (3.13).
П так что этот определитель отличен от нуля в том и только том случае, если элементы р„р„..., '(й„линейно независимы над полем Кч. Доказательство, Пусть 0„— определитель из левой части равенства (3.13). Докажем это равенство индукцией по и. Заметим, что при и = 1 формула тривиальна, если пустое произведение в правой ее части интерпретировать как 1. Теперь допустим, что формула (3.!3) доказана для некоторого и ~ !.
Рассмотрим мно- гочлен Гл. 3. Многочлеям яга яьяе жнмп яьлямя 3.52. Теорема. Пусть 11 - произвольное надпространство век- ) торного пространства 'К „, над полем ~в. Тогда для каждого1 неотрицательного целого числа 1г многочлен ь 1.1х) == П (х — р)' а~о является ц-многояленом над полем ~Г „,. Доказательство. Поскольку в результате возведения о-многочлена над полем 1г „в д'кз степень слова получаем о-многочлен " над К, то достаточно рассмотреть лишь случай и = О. Пусть )))„..., р„) — базис векторного пространства 11 над 1т"я Тогда ' определитель В„левой части равенства (3.13) отличен от нуля " по лемме 3.51; поэтому 1.
1х) =- 11 1х - ))) = аСо ввиду (3.14), а это уже доказывает, что 1, (х) является д-многочленад полем г 1:) Установленные нами свойства лннеаризовапных многочленов приводят к следующему методу нахохвдения корней таких мпого- " членов. Пусть и 1. 1х) = ~~ а;х~ — некоторый д-многочлен над полем г, и требуется найти все ' его корни в некотором конечном распиренип Р поля К „. Как уже отмечалось выше, отображение 1; )1 Е Р -э 1 ф) ~ Р, является линейным оператором в векторном пространстве Е над:; полем К . Поэтому 1.
можно представить некоторой матрицей над полем 1г,. Пусть )))о ..., 1Ц вЂ” базис Р пад полем 1гч; тогда" каждый элемент 1) ( г" можно задать и ниде линейной комбинации . )) =- ~~ ~сфр где стС~Г для 1 -, 1< з, 1=1 и, значит, 4 4. Лииезризовзиные многочлены 143 Теперь пусть 1- Ф1) = Е Ь1з()н для 1 < ! < и, з=! где Ьз (. !!ч Дла 1 < !', Ь < з, и пУсть В = (Ь,„) — квадратная матрйца порядка з над г .
Тогда Т.(5) = Е (з5з, где коэффициенты е(з определяются условием (с1, .", с ) В = (А,, е(,). В частности, уравнение з. (5) = 0 зквивалентно условию (с„..., с,) В = (О, ..., 0). (3.15) Это однородная система из з линейных уравнений относительно з неизвестных с„, „с,. Если ранг матрицы В равен г, то система (3.15) имеет дз — ' линейно независимых решений — векторов (с„.,., с,). Каждое решение (с„..., с,) соответствует некоторому корню д-многочлена 1. (х) в поле г. Таким образом, задача нахождения корней линеаризованного миогочлена Т., лежащих в поле г, сводится к более легкой задаче решения однородной системы ли- нейных уравнений.
3.53. Пример. Рассмотрим линеаризованный многочлен 1. (х) = хз — хз — ах ~ гз !х), где а — корень примитивного многочлена х'+ х — 1 над полем Гз, Для нахождения корней миогочлена Т. (х) в поле Кзз рассмотрим базис !1, ь, ьз, поля !!'зз как векторного пространства над полем Кз, где ь — корень примитивного многочлена х' + хз + х' — х — ! над !! з (ср. с примером 3.44).
Учитывая, что порядками элементов а и в мультипликативной группе Ц, являются соответственно числа 8 и 80, получаем равенство вида а = Ь'~1, где !' принимает значе- ния 1, 3, 5 или 7; но поскольку ьзз + ь'з — 1 = — О, то мы можем взять а = ьзз = — 1 + ь + ьз — ьз. Затем находим В (!) = — а = 1 — ь — ьз + ьз, ( р р, ~з ~ ~ р вез Т-(Р) = Р— Р— аР = — 1+ Г, г (гз) гзз гз агз ! гз Гл.
3. Многочлены нал конечными полнил 144 и, следовательно, получаем, 1 О В --. —.1 1 что — 1 — 1 1 — 1 †! — 1 ΠΠΠΠ— 1 Однородная система линейных уравнений (3.15) имеет диа линейно независимых решения, например (О, О, 1, 1) и ( — 1, 1, О, 1), Любое решение этой системы получается как линейная комбинация указанных двух векторов с коэффициентами из поля Ка, Следовательно, корнями многочлена ! (х) в иоле (Га, являются Этот метод нахождения корне!1 можно применять и для более общего класса многочленов, а именно длн так называемых аффинных многочленов. 3.54.
Определение. 5(ногочлен вида Л (х) -- 5 (х) — х, где Е (х) есть д-многочлен над полем К,„, а я (- К „„называется гы' аффинным 4-лгногочлсном над 'У „,. Элемент () из некоторого конечного расширения Р' поля !)' м является корнем мпогочлена Л (х) в том и только том случае, если Е ())) -- га. В обозначениях формулы (3.15) равенство 5 (!)) = =- се эквивалентно равенству (с,, ..., са)  — (г(ы ..., И,), (3.16) где се ==- ~а г(а()а. Система (3.16) линейных уравнений разрешима а=-~ относительно с„..., са, и каждый ее вектор-решение (с,, ..., с,) 5 соответствует некоторому корню )) =-- ~~са()з многочлена А (х), 1=-1 лежащему в поле г. Сравнительная легкость отыскания корней аффинных много- 4 членов подсказывает следуюгцнп метод нахождения корней произвольного многочлена Г (х) положительной степени над К „ в некотором расширении г" поля 'Г „,. Сначала находим какой- нибУдь ненУлевой аффпнный е)-многочлен А (х) пад Гчоо котоРый 3 делится на 1 (х); он называется шргринногм кратным атигачлена: 1(х).
Затем описанным выше способом получаем все корни много- члена А (х) нз г. Поскольку среди этих корней находятся н корни многочлена 1 (х) пз Р, то достаточно подсчитать значения ) (()) для всех корней 13 (- г многочлепа А (х), н мы выделим все корни .:, миогочлена! (х) в поле Р. 145 4 4. Линеаризоаанные много«лены Остается выяснить лишь, как находить аффинное кратное А (х) многочлена ~ (х).
Существует следующий способ. Пусть и ) !— степень многочлена ~ (х). Для каждого ! = — О, 1, ..., и — 1 вычисляем однозначно определенный многочлен г, (х) степени !г ( и — 1, удовлетворяющий условию х" = г! (х) (шоб 1 (х)). Затем находим такие элементы а! ~ ~~ м, не все равные нулю, « — ! чтобы линейная комбинация ~ я;г; (х) была постоянным много=о членом.
С этой целью приравниваем нулю и — 1 коэффициентов ппи положительных степенях х1, 1 ( 1 ( и — 1, переменной х. Так мы получаем однородную систему из и — 1 линейных уравнений относительно и неизвестных а„а„..., а„,. Такая система всегда имеет нетривиальное решение.
Зафиксировав некоторое нетривиальное решение (я„я„..., а„,) этой системы уравнений, « — ! мы получаем ~, я;г! (х) = а для некоторого а ~ Ром, Это пэна!=о чает, что « — ! л — ! ~ а;хе = ~ сс;г; (х) = — а (щос(1(х)), а=о г=о так что А(х) = ~ а;хе — я 1=о есть ненулевой аффинный д-многочлен над 7 , делящийся на 1 (х). Ясно, что этот многочлен А (х) можно выбрать нормиро- ванным. 3.55. Пример. Пусть 1(х) = х'+ 0'х'+ Ох'+ х+ 8 ~ !с ~74 (х1, где 0 — некоторый корень многочлена х'+ х + 1 ~ с Кз (х1. Требуется найти корни многочлена 1 (х), лежащие в поле г'зе.
Сначала найдем какое-нибудь аффинное кратное А (х) многочлена ~(х), применяя описанный выше метод при д = 2. По модулю 1 (х) имеем х— : х = г;(х), х' = — х' = г, (х), х':— .-: 0 ° + Ох + х + 0 = ., (х), = О.''+ 0 з + х +'0 ='., (х). Условие, состоящее в том, что линейная комбинация а,г, (х) + + я!г, (х) + язгз (х) + азг, (х) с коэффициентами а, Е Ге должна быть постоянным многочленом, приводит к следующей однородной системе линейных уравнений относительно коэффициентов я„, а„яз, аз: а + аз=О, сс, -1- 0 я, + Оаз = О, 0'аз + Ояз = О.
146 Гл. 3. Многочлены нед конечнымн нолкмн Выберем яе = 1, и тогда получим и, = 0', и, = 0', ие = О.,' Таким образом, искомым постоянным многочленом является и — инге (Х) + ияГя (Х) + ЯФГ2 (Х) + изГЗ (Х) = 0 и, значит, А (х) = иахе + иехЯ + и,х' + и,х — и = , = ° + в;+е'х + е,+ е.,: Теперь подсчитаем корни аффинного 2-многочлена А (х» в поле Кяя. Это значит, что для 2-многочлена ь (х) = ° + в' ° + е*х'+ ех над гя мы должны решить уравнение Е (х) = 0'. Пусть ь — ка( кой-нибудь корень примитивного многочлена х' + х + 1 над Кк,;: Тогда (1„ь, ье, ье, ьЯ, ье( — базис поля Кяя над г,. Так как 0 произвольный первообразный корень третьей степени из единиц над К„то можно взять е = Р' = 1+ ~ + Р + Г.
+ Р. Пользуясь тем, что 0' = 0 + 1 = ь + ье + ьЯ + ье, получим Г(П ~ ( ~а ( ~Я+~Я ~(1) = 1+ Р + ~я ((д р ( ~я+~я+~я (- (1') = 1 + Г + Р, )- (~') = ~я ) (р) р+~а ( ~я Таким образом, матрица В из (3.16) имеет вид О 1 О 1 1 1 О 1 1 О О 1 О О 1 1 1 1 В 010110 ° О О О О О 1 О О 1 1 1 О Из указанного выше представления элемента и = 0' получа, что вектор (я(я, ..., я(,) из (3.16) равен (О, 1, О, 1, 1, 1). Тепе' нетрудно найти общее решение системы (3.16): (1, О, О, О, О, О) + а, (О, 1, 1„ 1, О, О) + + а, (1, 1, 1, О, 1, 0) + 'а, (1, 1, О, О, О, где а„а,, а, — произвольные коэффициенты из поля (г"е. Ит корнями аффинного многочлена А (х) в поле Кяя являются 1)я =" 4 4.
Лннеэрнэовэнные многочлены 147 Чэ -' ь + ь Чэ ь + ь + ь г Ч4 1 + ь + ь + ь Чэ 1 + р + ~э „ р + ~э + р ~э + ~э „ 1 1 ~ + ,","' + Ь' + Ь' =- О. Вычисляя значения 7" (Ч,) для ) = 1, ..., 8, полУчаем окончательно, что коРнЯми многочлена 7 (х) в поле Кээ являются элементы Чэ Чэ Чэ и Чэ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
