Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
533
говоря языком линейной алгебры, пространство 5 (/ (я) g (ж)) является
прямой суммой своих подпространств S (f (х)) и S (g (а)). Другими
словами, любую последовательность сг ? S (f (a) g (а)) можно единственным
образом представить в виде а = + о.г,
где aL ? S (f (а)), а ет2 ? S (g (а)).
Вспомним теперь, что S (f (а)) является векторным пространством над полем
и что размерность этого векторного пространства равняется степени
многочлена / (а). Это векторное пространство обладает еще одним
интересным свойством: если последовательность v si> лежит в множестве S
(/(а)), то для любого целого числа b 0 сдвинутая последовательность sb,
sb+i, ... также лежит в S (f (а)). Это свойство немедленно вытекает из
соответствующего линейного рекуррентного соотношения. Мы сформулируем это
свойство в виде утверждения о том, что множество S (f (а)) замкнуто
относительно сд&ига входящих в него последовательностей. В совокупности
перечисленные свойства полностью характеризуют множества S (f (х)).
8.56. Теорема. Пусть Е - некоторое множество последовательностей над
полем |рч. Тогда Е - S (/ (а)) для некоторого нормированного многочлена /
(а) ? \х], deg ([ (а)) > 0, в том
и только упои случае, если множество Е является конечномерным векторным
пространством над полем (относительно стандартных операций сложения
последовательностей и умножения их па константу), которое замкнуто
относительно операции сдвига последовательностей.
Доказательство. Как мы уже отмечали, условия этой теоремы являются
необходимыми. Чтобы доказать их достаточность, рассмотрим произвольную
ненулевую последовательность сг ? Е. Вели а обозначает последовательность
Sq, а 6>0~ про-
извольное целое число, то через a*fc> обозначим сдвинутую
последовательность sb, 5ь+ь ... . По предположению все последовательности
сг*0), сг0), сг<2), ... лежат в Е. Но Е - конечное множество, откуда
следует, что существуют неотрицательные целые числа i < /, такие, что
его) = сг о). Отсюда вытекает, что исходная последовательность сг
удовлетворяет однородному линейному рекуррентному соотношению sn+^ sn+l,
n ~ 0, 1, ... . По теореме 8.42 последовательность сг имеет минимальный
многочлен т<! (а) ? [х \, и пусть k - deg (ma (а)). Тогда в силу теоремы
8.51 векторы состояний s0l sb ... , sk_x последовательности a являются
линейно независимыми над полем fq. Значит, последовательности сг*°),
сг°), о(й-|) являются линейно независи-
мыми элементами пространства S (тв (а)) и, следовательно, образуют базис
пространства S (mG (а)). Так как сг*°>, а°>, ... V*' °{к~]} принадлежат
также и векторному пространству Е, то ^ (П1о {•*)) является линейным
подпространством пространства Е.
534
Гл. S. Линейные рекуррентные последовательности
Обозначим через ?* множество последовательностей, получен из Е путем
отбрасывания нулевой последовательности. Прово приведенные выше
рассуждения для всех nf Р, приход
к тому, что конечная сумма векторных пространств 2 S (та
является линейным подпространством пространства Е. С друг стороны,
очевидно, что В ^ 2 ^ (та W) и' значит, Е
О ? ?*
2 ^ (tnQ (х)). Применяя теорему 8.55, получаем
о ? ?*
Е = 2 5 (та (х)) - S (/ (х)),
•Су
•Ж
I5*/.
<!:
I
а
Л
где f (х) ¦- наименьшее общее кратное многочленов пга (х), щ пробегает
конечное множество Е*.
Из теоремы 8.55 следует, что сумма двух и более однородн линейных
рекуррентных последовательностей над полем является однородной линейной
рекуррентной последовате|| ностью. Характеристический многочлен суммарной
последов; тельности тоже легко получается из этой теоремы. В важных чд
ных случаях минимальный многочлен и минимальный пер суммарной
последовательности можно непосредственно получ| из соответствующих
характеристик суммируемых последа тельностей.
8.57. Теорема" Пусть ot, i- 1, 2, h, - однородные нейные рекуррентные
последовательности над полем fqi a т$ (ж б !Fg [ х ] - соответствующие м
и н им ал ьные мн ого члены.
и*'
Ш
-.Л.
многочлены тЛ (х)у mh (х) попарно взаимно просты, то ми мальный многочлен
суммы о, -}- ... 4- oh равен произведен
тх (а:) ... mh (х).
Доказательство. Для доказательства достаточно рассмотр случай h - 2, так
как доказательство в общем случае легко лучить но индукции. Если один из
многочленов тг (х) или тг является постоянным многочленом, равным !, то
результат виален. Аналогично, если минимальный многочлен т (х| б Fq
соответствующий сумме ох-Н аг, является постоян многочленом, равным !, то
результат получается непосредствен! Предположим, что все многочлены гщ
(х), т2 (х), т (х) явля многочленами положительной степени. Так как в
силу теоремы 8
ot f ь.2 ? S (гщ (х)) -f S (т2 (х)) - S (тг (х) т, (х)),
т (х) делит (Щ (х) гщ (х). Пусть ог последовательность ..., а а,г -
последовательность t0, и пусть
то
т (х) -- xk - ah._iXk~~l
а
о
§ 5, Семейства линейных последовательностей
535
Тогда
Sn+k ~Ь Gi+h ~ ak-l (sn+h-1 + tn+k-l) {- f ' г "о(^п ~Е
п - 0, 1, ...
Е о л и МЫ II олож и м
