Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
А как элемента группы GL (k. IF^). ?
8.27. Теорема. Пусть s0, su ... - однородная линейная рекуррентная
последовательность над полем F9 и f (х) ?fq[x] - характеристический
многочлен этой последовательности. Тогда минимальный период этой
последовательности делит ord (f (х)), а минимальный период
соответствующей импульсной функции равняется ord (/ (х)). При этом если f
(0) Ф 0, то обе последовательности являются чисто периодическими.
Доказательство. Если f (0) Ф 0, то в силу леммы 8.26 результат является
простой переформулировкой утверждений теорем 8 13 и 8.17. В этом случае
чистая периодичность будет следовать из теоремы 8.11. Если же f (0) = 0,
то представим / (х) в виде / (*) xhg (х), где g (0) Ф 0 (как в
определении 3.2), и положим
512
Гл. 8, Линейные рекуррентные последовательности
• .7^
и sni.iH, п =¦-- 0, 1, ... . Если deg (g (х)) > 0, то tt. ... - одно
родная линейная рекуррентная последовательность с .характери стическим
многочленом g(x). Ее минимальный период совпадав с минимальным периодом
последовательности s0, sx, ... . Значит как было показано выше,
минимальный период последователе1 ностн slt ... делит число ord (g (х)) -
ord (/ (х)}. Соответству щее утверждение для импульсной функции
доказывается а нал: гнчным образом. Если же g (х) - постоянный м по
гочлен, то те~ рема становится тривиальной.
Заметим, что при f (0) Ф 0 минимальный период нмпульснс? функции можно
также получить из равенства (8.9) следующцг способом. Для импульсной
функции, характеристический мног4 член которой равен / (х), многочлен h
(х), появляющийся в фо^
муле (8.10), равен просто - 1. Значит, еслн г - минимально пернод
импульсной функции, го на основании (8.9) / (х) дел|| хг 1, и,
следовательно, r> ord {f (х)). С другой стороны, основании первой части
утверждения теоремы 8.27 г должен делит , ord (/ (х)). Таким образом,
получаем искомое равенство г щ
ord (/ (л)).
-f'.h
8.28 Теорема. Пусть s0. s{, ... - однородная линейная реку/jj рентная
последовательность над полем fq с ненулевым вектора начального состояния.
Пусть ее характеристический многочлф f (*) ? [х] является неприводимым
многочленом над полем Ц
и удовлетворяет условию f (0) Ф 0. Тогда последовательность s| slt ...
является чисто периодической последовательностью и Ц* минимальный период
г равен ord (/ (х)).
Доказательство. Из теоремы 8.27 вытекает, что рассматр||% ваемая
последовательность является чисто периодической и минимальный период г
делит ord (/ (х)), С другой стороВД из (8.9) следует, что / (х) делнт
(хг - 1) h (х). Так как s (х),
следовательно, и Н(х) являются ненулевыми многочленами f
так как deg (h (х)) < deg (/(х)), то из неприводимости /(4
вытекает, что многочлен / (х) делнт хг- 1, и, значит, г ||
>ord(/(x)).
Даднм теперь другое доказательство следствия 3.4. Для удрб ства приведем
еще раз его формулировку.
8.29. Теорема. Пусть / (х) ? fx] - неприводимый гочлен над полем и deg (/
(х)) = к. Тогда ord (/ (х)) делшп|
Доказательство. Не теряя общности, можно считать, чЩ f (х) является
нормированным многочленом и / (0) Ф 0. Расемо-у
§ 2. Импульсная функция. Характеристический многочлен
513
трнм однородную л и йен ну ю рекуррентную последовательность над полем с
характеристическим многочленом / (х) и ненулевым вектором начального
состояния. По теореме 8.23 эта последовательность является чисто
периодической, и минимальный период этой последовательности равняется ovd
(f (х)). Тогда в ней встречаются ord (/(х)) различных векторов состояний.
Если ord ([ (*)) меньше qk- 1, общего числа ненулевых ^-мерных векторов
над полем Тд, то можно выбрать k-мерный вектор, который ие встречается в
качестве одного из векторов состояния указанной выше последовательности.
Возьмем этот вектор в качестве вектора начального состояния другой
однородной линейной рекуррентной последовательности над полем с тем же
характеристическим многочленом f (х). Ни один из е = ord (/ (х))
различных векторов состояния этой последовательности не равняется ни
одному вектору состояния предыдущей последовательности. В иро-тнвном
случае эти две последовательности, начиная с какого-то места, должны были
бы совпадать, и тогда вектор начального состояния второй
последовательности должен был бы встретиться в первой последовательности
в качестве одного из ее векторов состояния, что противоречит его выбору.
Продолжая указанным выше образом строить новые рекуррентные
последовательности, получаем разбиение множества, состоящего из qk - 1
ненулевых А-мерных векторов над полем f9, на подмножества мощности е •=
•• ord (/ (х)) каждое, что и доказывает утверждение теоремы. ?
8.30. Пример. Рассмотрим линейное рекуррентное еоотно*
шение sn+)i = sn+4 -f нп+г + sn+l +'sn, n - 0, t, над полем F-.,
Соответствующий характеристический многочлен / (х) -
- Xе - х1 - хг - х - 1 ? Fa UI является неприводимым многочленом над
полем F-ь Кроме того, f (х) делит г*1 - 1 и не является делителем
