Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Тогда sn = с% для всех п = О, I, ...
и
:Л
k
i
n+t
О, n = 0, 1, ..
f=0
Отсюда
*
*
I
(-с)'
С*+\ 2
k
t
it
(-
iy-ч
n+t
0
f=0
("=0
для всех n
0, 1, .
k
I *
н тогда
5*'$ *. >A<
и s
•
<><
№
k
i
(-C)
о
$
- характеристический многочлен последовательности s04> **
Значит, векторное пространство $ (x - с) S ((x - 1)^) явля
подпространством пространства S ((х - c)ft). Так как с
первое векторное пространство имеет над полем Fg размерност и, таким
образом, совпадает с пространством S ((х - c)k), к рое имеет ту же
размерность над Fg.
8.72. Теорема. Пусть f (х) ? F? UI - нормированный щ гочлен, не
являющийся константой и не имеющий кратных кор и / (0) Ф 0. Пусть k -
целое положительное число. Тогда
S {(} (дг))*) = S (/ (х)} S {{х - 1)*).
44
¦т
"Н
Доказательство. Пусть F - поле разложения многочле f (х) над полем Тогда
если а пробегает все корни многочле| / (х), то по теореме 8.55
s""n*))*)= 2 sp <(*-")*).
а
Используя лемму 8.71 и закон дистрибутивности, установлен"; при
доказательстве теоремы 8.67, получаем
Sp ((/ (*))*) = ? $f ((* - l)fe) Sp (х - а) =
•К
а
• <
= SF ((X - 1)*) 2 Sp(x а) = SF((x - l)k)Sp(f(x<
а
-Xi
где последнее равенство следует из теоремы 8,55. Искомый зультат вытекает
теперь из леммы 8.68,
§ 6. Характеризация линейных последовательностей
547
§ 6. Характеризация линейных рекуррентных
последовательностей
Важной задачей является выяснение того, будет данная последовательность
элементов поля Fa линейной рекуррентной последовательностью или нет, С
теоретической точки зрения этот вопрос можно разрешить немедленно, так
как линейные рекуррентные последовательности над полем Fg и только они
являются периодическими последовательностями. Однако периоды некоторых
линейных рекуррентных последовательностей (даже сравнительно небольшого
порядка) могут быть очень длинными, н на практике часто бывает
невозможным определить природу данной последовательности на основании
лишь этого критерия. Другие способы характеризации линейных рекуррентных
последовательностей используют понятия линейной алгебры.
Пусть s0, Sj, ... - произвольная последовательность элементов поля |Fg.
Для целых чисел п 0, г 1 введем понятие ганкелева определителя
D{r)~
Un -
* i
* * * f
^n+r-1 4 * ¦ * ?га+2г-2
связанного с этой последовательностью. Как мы увидим дальше, линейные
рекуррентные последовательности можно охарактеризовать в терминах
обращения в нуль достаточного числа ганке-левых определителей, связанных
с этой последовательностью.
8.73. Лемма. Пусть v slt ... - произвольная последовательность над полем
Fg, и пусть п > 0, г Д 1 - целые числа. Тогда
из равенств Dn] ггг - 0 следует равенство Di+i ~ 0.
Доказательство. Для 0 введем вектор sm - (sm, sm+1, ...
. Из равенства Djf * = 0 следует, что векторы sn, sn+b ...
(r)n+r-i линенно зависимы над полем Fg. Если
(r)В+1" * (r)я+г-1
тоже линейно зависимы над Fg, то мы тут же получаем равенство
0|/lj - - 0. В противном случае вектор &п является линейной комбинацией
векторов sn+i, .sn+r_i. Пусть = (smt
s^i t> ..., sm+r) для m > 0. Тогда векторы
будучи строками равного нулю определителя D?+1>, линейно зависимы над
полем Fg. Если s^, sn+u Sn+r-г линейно зависимы над Fg, то" применяя
линейное отображение
L\. (а0, Gj, ..аг) ? Fg~^* '-*{аи * * ¦" &г) ? Fg"
Получаем, что s^i, $п+2> • ••, sa+r тоже линейно зависимы НаД Fg и,
следовательно, Dj?+i ~ 0. В противном случае (еслн $п,
ь*
548
Гл, 8, Линейные рекуррентные последовательности
$л+ь • ••> Sn+r-j линейно независимы) получаем, что вектор является
линейной комбинацией s'nt s^+ь ..., sB_j-r_i, и тогд: применяя линейное
отображение
L2* (&0i @li
Ur- ь ar) ? 1 ь~> (<20, Щ,
к * к
#r-i) € §>>
получаем, что s?l+r является линейной комбинацией векторов $
sB+r_!. Но в рассматриваемом случае $п есть линейна
. Г . *
комбинация векторов sn+1} Таким образом, вектор.
$njtь ... , 5Л^.Г__t, sп+r, являющиеся строками определителя линейно
зависимы над F*, откуда следует, что DnU ~ 0.
8.74. Теорема. Последовательность $Li ... элементов поля является
линейной рекуррентной последовательностью тогда только тогда, когда
существует положительное целое число г,
кое, что D(nr) = 0 для всех (кроме, может быть, конечного час. п > 0.
Доказательство. Предположим, что последовательность
s
1*
* * к
удовлетворяет однородному линейному рекуррентному о ношению k-ro порядка.
Для любого фиксированного п > 0 ра
смотрим определитель D{n+]) , В силу линейного рекуррентн! соотношения,
которому подчиняются элементы последователе
(k + 1)-я строка определителя D{n+l) явля
НОСТИ So,
линейной комбинацией первых k строк, и, следовательно,
- 0. Неоднородный случай сводится к однородному по формуй (8.5).
Необходимость доказана.
Докажем достаточность. Пусть k + 1 - наименьшее н.
ральное число, такое, что Djf'1 ?) - 0 для всех, кроме, мо; быть,
конечного числа п е> 0. Если k + I = 1, то теорема до; зана. Рассмотрим
случай С Тогда найдется целое т ^
