Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 117

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 117)

8.52. Следствие. Если последова>пельноси>ь нульсноя <рунк>1ия. соответствуюи<с>я некоторому однородном»' нейному рекуррентному соотношению над полел< Гл, то.нини,н ' ный многочлен этой последовательности равен характерист' скому многочлену этого линейного рекуррентного соотноше Доказательство. Поскольку импульсная функция обл тем свойством, что первые я ее векторов состояний линейно и висимы, то сформулированное утверждение следует нз тео 8 51.

$ 5. Семейства линейных рекуррентных последовательностей Пусть 1 (х) Е Ке !х! — нормированный миогочлен поло' тельной степени. Через 5 Ц (х)) обозначим множество всех о' родных линейных рекуррентных последовательностей над лем К с характеристическим многочленом Г (х). Другими вами, 5 (1 (х)) состоит из всех последовательностей над полем,; которые удовлетворяют однородному линейному рекуррентн соотношению, определяемому многочленом ) (х). Если <)ед (~ (х) -- й, то 5 (! (х)) содержит ровно о' последовательностей, соот' ствующнх выбору в' различных значений вектора началь состояния.

Множество 5 (1' (х)) можно рассматривать как векторное странство над Кч, если <иределить соответствующим образом рации пад последовательностями элементов из поля Кч. если через о обозначена последовательность э,, э,, ..., а через последовательность йн йы ..., состоящие из элементов поля " то определим их сумму о -> т как последовательность д> + э, -,- гы ....

Далее, если с Е >)е. то пРоизведение со опРед ется как последовательность вида се<о сэ„ .. . Из рекуррент соотношения непосредственно следует, что множество 5 (г замкнуто относительно операций сложения и умножения на станту. Нетрудно проверить выполнение аксиом векторного 4 5, Семейства линейных последовательностей 53! транстза. Таким образом, 5 (г" (х)) действительно представляет бо1з вектоРное пРостРанство над полем г . Роль нУлевого векра и~рвет нулевая последовательность — последовательность, се члены которой равняются нулевому элементу поля Г». Так как 5 (1(х)) содержит дл элементов, размерность полученного векторного пространства равняется й.

Выберем й линейно независимых наборов длины А из элементов поля К». Если обозначить эти й-наборы через у,, ..., ул, то й линейно независимых элемензшз пространства 5 (~(х)) можно получить, рассматривая последовательности а,, ..., а„ из 5 (1(х)), такие, что вектор ум 1 ( является вектором начального состояния последовательности аго Наиболее естественным является выбор в качестве ул стандартного базиса векторов е, == (1, О, ..., О), е, = (О, 1, ..., О), ..., ел = (О, ..., О, !). Другой базис пространства 5 (! (х)), который часто бывает полезным, получается при рассмотрении импульсной функции де, й,, ... из 5 (! (х)), если в качестве у„..., у„выбрать первые й ее векторов состояний д», дз, ..., дл з.

Теперь рассмотрим соотношения между различными множествами 5 (1 (х)). 8,53. Теорема. Пусть 1' (х) и йг (х) — два нормированных много»лена над полем К», не являющиеся постоянными многочленами. Тогда 5 (~ (х)) является подмножеством множества 5 (я (х)) в том и только том случае, если 1" (х) делит д(х), Доказательство. Предположим, что 5 (! (х)) ы 5 (у (х)). Расгзнзтрнм импульсную функцию, принадлежащую 5 (! (х)). В силу следствия 8,52 ее минимальный многочлен равен ! (х). По предположению она лежит также и в множестве 5 (у (х)). Следовательно, по теореме 8,42 ее минимальный многочлен !" (х) делит йг(х). Обратно, если ~ (х) делит д (х), а зо, з,.... — произвольная последовательность из 5 ()' (х)), то по теореме 8.42 минимальный много»лен этой последовательности т (х) делит ) (х). Следовательно, и' (х) делит и д(х), и, применяя вновь теорему 8.42, получаем„ что последовательность э„, з,..., принадлежит 5 (у (х)).

Таким образом, 5 (! (х)) является подмножеством множества 5 (а (х)). ) 1 8 54. Теорема. Пусть ~, (х), ..., 1л (х) — нормированные мно'счлгны над полем г, ни один из которых не являгпзся постоянным л '"ого»ленам. Если 1, (х), ..., /л (х) взаимно пРосты, то пеРесе»' пгниг 5%(х)) П - П 5((л(х)) содгржигп лищь нулевую последовательность.

Если д(х) — норм"Рованный многочлен, бей (с( (х)) > О, являющийся наибольшим обЩим делителем многочленов ~, (х), ..., 1л (х), то 5 (6 (х)) () " П 5(~л(х)) = 5 (д(х)). 532 Гл. а. Линейные реиурреитиые последовательности Доказательство. Минимальный многочлен т (х) любой следовательностн, лежащей в рассматриваемом пересечении, д' жен делить ~, (х), ..., )'„(х). Если этн многочлены взаимно п сты. то т (х) — 1, а только нчлевая последовательность и минимальный многочлен, равный 1. Во втором случае мы зак чаем, что т (х) делит д (х), а тогда по теореме 8.42 5 (Г, (х)) П ..П 5 Дь (х)) ~ 5 (И (х)). В свою очередь, обратное включен 5 (с( (х)) ~с 5 (11 (х)) Г) ...

П 5 Ць Гх)1 следует нз теоре' 8.53. Обозначим через 5 (Г (х)) 1 5 Ги(х)) множество всех после" вательностей вида сг -'; т, где о Е 5 (Р (х)), т 6 5 Гд (х)). определение, разумеется, можно распространить на любое печное число слагаемых. 8.55. Теорема. Пусть Г, (х)...., Гь ( х) — нормированные м гочлены над полем Ео, нг Явлл~оиГиесл носточнными. Тогда 5 (), Гх)) -', ... 1 5 ГГк(х)) -- 5 (с (х)), где с (х) — — нормированный многочлен, являющийся наиненьш общим кратным многочлснов Г, (х), ..., гк Гх). Доказательства.

Достаточно рассмотреть случал й = 2, так К общий случай легко получить по индукции. Прежде всего, за тнм, что по теореме 8.53 последовательность нз 5 (Г, (х)) из 5 Г~в (х)) обязательно принадлежит и 5 (с (х)). Отсюда следу' что 5 ф (х)) 4 5 ГГе (х)) = 5 (с (х)). Сравним теперь размерно этих множеств как векторных пространств над полем т . Пола $', =- 5 (Г, (х)), Р'в = 5 (Ге (х)), обозначая через д (х) норм ванный многочлен, являющийся наибольшим общим делите Г, (х), Ге (х), и пРименЯЯ теооемУ 8.54, полУчаем й п1 (~'1 -1 1~в) = й п1 (1',) + й п| (Р'в) - - д ип (У, Г) $'в) .=- =- деа(Г",(х))+ дед(Гв(х)) — дея(д(х)), Но с (х) =-- Г, (х) Г", (х) д (х), откуда йш ($', + 1~в) = <!ед (с (х)) = йш (5 (с (х))). Таким образом, линейное надпространство 5 (), (х)) + 5 ГУе (х))' с=- 5 (с (х)] имеет ту же размерность.

что и линейное простран 5 Гс (х)), откуда следует равенство 5 (Г, (х)) + 5 (Ге (х)):: =- 5 (с (х)). В частном случае, когда многочлены,г (х) и а (х) являю взаимно простыми нормированными многочленами над полем не являющимися константами, имеет место соотношение 5 () (х) д (х)) — 5 (Г (х',) + 5 (к (х)). Так как в этом случае из теоремы 8.54 следует, что 5 ГГ' (х)),1 П 5 (д (х)) содержит только нулевую последовательность, 4 5.

Семейства линейных последоветеяьносгеа 533 оворя языком линейной алгебры, пространство 5 (г (х) а (х)) ~вляется прямой суммой своих надпространств 5 Д (х)) и 5 (а (х)). другими словами, любую последовательность о Е 5 (~ (х) а (х)) можно единственным образом представить в виде о = а, + ае ,.де о., Е 5 (г* (х)), а о, Е 5 (у (х)). Вспомним теперь, что 5 () (х)) является векторным пространством над полем Го и что размерность этого векторного пространства равняется степени многочлена ) (х).

Это векторное пространство обладает еще одним интересным свойством: если последовательность во, в,, ... лежит в множестве 5 ()' (х)), то для любого целого числа Ь у О сдвинутая последовательность вь, в„а, ... также лежит в 5 () (х)). Это свойство немедленно вытекает из соответствующего линейного рекуррентного соотношения. Ь)ы сформулируем это свойство в виде утверждения о том, что множество 5 (г" (х)) замкнуто относительно сдвига входясцих в него последовательностей. В совокупности перечисленные свойства полностью характеризуют множества 5 (~ (х)). 8.56.

Теорема. Пусть Š— некоторог множество последовательностей над полем Г . Тогда Е = — 5 ()'(х)) для некоторого нормированного многочлена 1(х) Е Ге (х1, дед О (х)) ) О, в том и сполько пюлс случае, если множество Е является конечномерным векторным пространство,и над полем т о (относительно стандартных операций сложения последовательностей и умножения их на константу), которое замкнуто относительно операции сдвига последовательностей.

Доказательство. Как мы уже отмечали, условия этой теоремы являются необходимыми. Чтобы доказать их достаточность, рассмотрим произвольную ненулевую последовательность о Е Е. Если о обозначает последовательность з,, з,, ..., а Ь ) Π— произвольное целое число, то через Фи обозначим сдвинутую последовательность зь, вь„, .... По предположению все последовательности ою>, оо), о<'>, „. лежат в Е.

Но Š— конечное мно>кество, откуда следует, что существуют неотрицательные целые числа ~' < )', такие, что а<о .— аи>. Отсюда вытекает, что исходная последовательность а удовлетворяет однородному линейному рекуррентному соотношению в„,г — — з„„, и =- О, 1, .... По теоРеме 8.42 последовательность о имеет минимальный многочлен (х) Е Ко (х1, и пусть й = дед (т, (х)). Тогда в силу теоремы " 81 векторы состояний зо, з,, ..., а„, последовательности о являются линейно независимыми над полем то.

Значит, последовательности амц ою, ..., ом и являются линейно независи"ыми элементами пространства 5 (т, (х)) и, следовательно, обР~~уют базис пространства 5 (т, (х)). Так как о~о>, а~'>, ... " принадлежат также и векторному пространству Е, то (гп, (х)) является линейным подпространством пространства Е.

Характеристики

Список файлов книги