Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
последовательности sx, s2^f равняется хЧ х 4 1 и является делителем
многочлена х^-4 ха 4 х. Этот пример показывает, что второе утверждение
ремы 8.48 может не выполняться в случае, если s0, sx, ... является чисто
периодической последовательностью.
§ 4. Минимальный многочлен
529
8.50- Теорема. Пусть / (х) ? \х \ - нормированный неприводимый многочлен
над полем fq, и пусть %, ... - одно-
родная линейная рекуррентная последовательность над полем р не являющаяся
нулевой последовательностью. Если / (я) -
характеристический многочлен последовательности sQt Si то
он равняется ее минимальному многочлену т (л*).
Доказательство. Так как по теореме 8.42 минимальный многочлен т (х) пашей
последовательности должен делить многочлен / {х), то в силу
неприводимости / (х) получаем, что либо т (я) - I, либо т (х) = / (х).
Однако т (л:) - I только для нулевой последовательности. Отсюда вытекает
утверждение
теоремы. I S
Существует общий критерий для определения того, является ли
характеристический многочлен линейного рекуррентного соотношения,
определяющего данную линейную рекуррентную последовательность,
одновременно и минимальным многочленом этой последовательности.
8.51. Теорема. Пусть s0, Sj,...- последовательность элементов ноля fq,
удовлетворяющая линейному рекуррентному соотношению к- го порядка с
характеристическим многочленом / (я) ? F? \х]. Тогда / (х) совпадает с
минимальным многочленом этой последовательности в том и только том
случае, когда векторы состояний s0, Sj sk_i линейно независимы над полем
Fg.
Доказательство. Предположим, что / (х) является минимальным многочленом
нашей последовательности. Если векторы So-st" *¦•
sft_! линейно зависимы над полем то найдутся элементы bQ, hi bk^i ? не
все равные 0, такие, что bnsfl f ^st -{-...
т = 0. Рассмотрим матрицу Л из (8.3), соответствую-
щую данному линейному рекуррентному соотношению. Умножая все члены
приведенного выше равенства на степени матрицы Л, из равенства (8.4)
получаем
Мл ~\~ &lsn*l "Ь ¦ ' * I bfe_1Sn+fe"1 - 0f п ^ 0, 1, ... .
В частности,
Ь^п ^ Ь^а Д- ¦ • ¦ -f Ьк_г$п+к~1 •= 0 для всех п - О, I.......
Сели = 0 для всех 1 < / <; к - 1, то sn - 0 для всех пД> О, что
противоречит тому, что минимальный многочлен f (х) рассматриваемой
последовательности не является постоянным (т. е. имеет положительную
степень). Тогда пусть j I - наибольший индекс, для которого bj Ф 0.
Отсюда вытекает, что последователь-il0CTi> V Д, ... удовлетворяет
однородному линейному рекуррентному соотношению /-го порядка, где / < к.
Это противоречит предположению, что / (я) является минимальным
многочленом.
\ким образом, мы показали, что векторы s*,, slf .... sA_j ли-,,еиио
независимы над молем Fq.
7 Зак. 243
530
Гл. 8. Линейные рекуррентные последовательности
Обратно, предположим, что s0, st, .$h_i линейно неза симы над ijq. Так
как Ф 0, минимальный многочлен нашей; следовательностн имеет
положительную степень. Если / (х) является минимальным многочленом,
последовательность sit, должна удовлетворить однородному линейному
рекуррент! соотношению m-го порядка с коэффициентами из для иекотор; I <
т < к. Пусть это соотношение имеет вид
'Ч ч->
п - 0, Е ... -
= а
Однако отсюда следует равенство s
га
+
что противоречит предположению о линеинои независимости торов s0, slT
8.52. Следствие, Если последовательность s.
О" S>1 *
S: :<
f ,v
пульсная функция, соответствующая некоторому однородному нейному
рекуррентному соотношению над полем f9, то мин им ный многочлен этой
последовательности равен характерной скому многочлену этого линейного
рекуррентного соотноше*
Доказательство. Поскольку импульсная функция обл тем свойством, что
первые k ее векторов состояний линейно н виснмы, то сформулированное
утверждение следует из теор
8 51.
§ 5. Семейства линейных рекуррентных
последовательностей
Пусть f(x)?f"[x] - нормированный многочлен поло гельной степени. Через S
(f (хI) обозначим множество всех родных линейных рекуррентных
последовательностей над л ем с характеристическим многочленом f (у).
Другими
вами, S {/ (х)) состоит из всех последовательностей над полем которые
удовлетворяют однородному линейному рекуррентй соотношению, определяемому
многочленом f (х). Если deg (f (х) " k, то S (f (х)} содержит ровно qh
последовательностей, соот ствующих выбору qk различных значении вектора
начали состояния.
Множество S (/ (х)) можно рассматривать как векторное странство над если
определить соответствующим образом рацин иад последовательностями
элементов из поля если через а обозначена последовательность s0, slt ....
а через последовательность /0, состоящие из элементов поля
то определим их сумму о + т как последовательность s0 ~Ы Si Ч- (jp ...
Далее, если с ? Fi?, то произведение со опред ется как последовательность
вида csu ... . Из рекуррент соотношения непосредственно следует, что
множество S if замкнуто относительно операций сложения и умножения на
станту. Нетрудно проверить выполнение аксиом векторного
