Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
1,2, m* имеет кратность ех фр. Пусть et - 1, еслн 0. Тогда
.XI
¦Ш
¦
• " •
I" • .s SC'
т
$
п
2 Р( (rt) a?, п = 0, 1,
I-I
где Pit i - 1,2, m, - многочлен степени не более чем
коэффициенты которого однозначно определяются начальными
§ 2. Импульсная функция. Характеристический многочлен
509
значениями последовательности и лежат в поле разложения многочлена f (я)
над полем При этом целое число п естественным образом отождествляется с
соответствующим элементом поля Fg. Читатель, знакомый с дифференциальными
уравнениями, заметит определенную аналогию с общим решением однородного
линейного дифференциального уравнения с постоянными коэффициентами. ?
В случае когда характеристический многочлен является неприводимым,
элементы линейной рекуррентной последовательности могут быть представлены
с помощью соответствующей функции следа (определение функции, следа н ее
основные свойства приведены во второй главе, ем. определение 2.22 и
теорему 2.23).
8.24. Теорема. Пусть s0, ... -однородная линейная рекур-
рентная последовательность k-го порядка нрд полем К - !F\,
удовлетворяющая уравнению (8.7), а соответствующий характеристический
многочлен f (я) является неприводимым многочленом над полем К. Пусть а -
корень многочлена f (х) в расширении F fF9* поля К. Тогда существует
однозначно определенный
элемент 0 ? F, такой, что
sn ~ Тгр/кфап), п = 0, 1, ... .
Доказательство. Так как элементы {1, а, а*"1} образуют базис ноля F над
/С, то можно задать однозначно определенное линейное отображение L: F -
К, полагая L (an) - sn Для и ^ =- 0, 1, ..., k - 1. По теореме 2.24
существует однозначно определенный элемент 0 ? F, такой, что L (у) =
TrFIK (0у) для всех у б F. В частности,
sn ~ n = Q, 1, . . k- 1.
Остается показать, что элементы Тг^/к (0а'1), п = 0, 1, ..., образуют
однородную линейную рекуррентную последорательиость с характеристическим
многочленом f (х). Но если
/(*) = ** - ak_xxk~~l ~~ ¦**.- Оо € A'lJtl,
то, используя свойства функции следа, получаем Ггед(8ап+А) -
"fe__iTrF/K(6a'1+fe-1) - ... - а0 TrF/K(dan) =
- TrFfx;(Qan+k - afc_i0an+fc"I - ¦ ¦ * - а,о0а'1) =
= TrF/K(0an/(a)) = 0 для всех п > 0. П
Другие соотношения между линейными рекуррентными последовательностями и
их характеристическими многочленами могут
быть получены из следующего полиномиального тождества.
л?
510
Гл, 8, Линейные рекуррентные последовательности
8.25. Теорема. Пусть s0,
* Ш
- однородная линейная ре кур рентная последовательность k-го порядка над
полем Тф удщ влетворяюищя рекуррентному соотношению (8.7) и являющат
чисто периодической последовательностью с периодом г. Пустщ f (X) -
характеристической многочлен этой последовательности Тогда имеет место
равенство
/ (х) s (х) (I - хг) k (х),
(8.
Ч
где
Ч" $Г~%Х -j" Sr_i ? JE [Х]
s (х) - So*r-! Ч SiX^2 д-
k~\-/
h (x) ? ?
.fo
i :
' 'Mi
. VS
i.
(8.
/~о i=0
Доказательство. Сравним коэффициенты при одинаковых сте пенях х в обеих
частях равенства (8.9). Пусть ct (соответственно! dt) - коэффициент при
х', 0</ < fe -f- г - 1, в левой (соответ!
\ Щ
ственно правой) части равенства (8.9). Так как f(x)
S aix
i
я
т
получаем
ct -
? aiSr_i^j> 0 -Х t Я k я с - 1.
/+/=*
Sift
(8.П1;
Заметим, что линейное рекуррентное соотношение (8.7) може^ быть также
записано в виде
halS
(=0
. j
П + l
0 для всех п > 0.
(8.1$
ы*?.
Выделим теперь для отдельного рассмотрения следующие четыре случая. Если
k ^ г - 1, то из (8.11) и (8.12) следует
Аг
Q? " ^ - 0 -
i ~-0
Щ
Если / < г - 1 и / < k, то из (8.11), (8.12) н периодичности нашей
последовательности получаем
t k
Ct ~ aiSr_i_t+i = chsr-iM+i ~
?=0 iW+1
k k'-X-t
• ^ A
Ж ; № 'Ш
г;
; *U5v
? - db
l=t- f-i /=0
Если / > г и t ^ k, из (8.11) следует, что
k k-] - t-\-r
Ci -- - 2] СЦ$т~\М+\ " ? U
t 1 1=0
%
i+j-r+l
Si = d
t
.¦As?
§ 2. Импульсная функция. Характеристический многочлен 511
Если г -< / < k, то нз (8.11) и периодичности нашей последовательности
вытекает, что
t ; r-i
Ct " ^ ~ ^ ~~
t=t-r+1 i=0
ff-- \- t-\-r
f=r f=0
= ? fff+<+lsi+f ? ai+t-r+lsi "
i-O i=0
A1-!-/ ? - l-7-f-f/-
i- 0 0
Таким образом, теорема доказана. ?
-S
Лемма 3,1 утверждает, что для любого многочлена f (х) ? € UK f (0) # О,
найдется натуральное число е, такое, что / (х) делит - 1. Это приводит к
понятию порядка многочлена / (х) (см. определение 3.2), который
обозначается через ord (f (х)).
8.26. Лемма. Пусть
f (х) - х* - ah^xk~l - ak^xk~Q - ¦ • • - а0 € [х],
к > 1, aQ ф 0. Тогда ord (f (х)) равняется порядку матрицы А,
определяемой формулой (8.3) и рассматриваемой как элемент группы GL (k,
IF,,).
Доказательство. Ввиду того что А - сопровождающая матрица многочлена f
(х), то f (х) в свою очередь является минимальным многочленом матрицы А.
Следовательно, если / - единичная k х &-матрица над полем IF9, то
равенство Ае - I для некоторого натурального числа е выполняется тогда и
только тогда, когда многочлен / (х) делит хе- 1. Искомый результат
следует теперь из определений порядка многочлена / (х) и порядка матрицы
