Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 116
Текст из файла (страница 116)
Следовательно, справедливо равенстио ссо (х) и* (х) = а (х) Д (х). Тогда из теоремы 8.40 следует, что производящую функцию б (х) нашей последовательности можно представить в виде де (х) а (х) а (х) с~ (х) а (х) с" (х) Я (х) л>* (х) л>ь (х) с" (х) ' 1' (х) Так как с(ей (а (х) с* (х)) = с(ед (а (х)) + с(ед (с* (х)) < < с(ед (и (х)) + с(ед (с (х)1 = с(ед (( (х)), то из второй части теоремы 8.40 следует, что ( (х) является характеристическим многочленом нашей последовательности. Очевидно, что суцсествует только один многочлен и (х) с указанными свойствами П Однозначно определенный в теореме 8,42 многочлен и (х) Р с Г, (х), соответствующий последовательности хо, х>, ..., называется минимальным многочлеиом этой последовательности.
Если хи = О для всех п ) О, то минимальный многочлен этой последовательности равен 1. для всех других однородных линейных Рекуррентных последовательностей и (х) является нормирован"ым многочленом степени с(еа (и (х)) ) 0 н представляет собой характеристический многочлен линейного рекуррентного соот"ошення минимально возможного порядка, которому удовлетво- 526 Гл. а.
Лннейные ренуррентные ноелелонательностн ряет наша последовательность. Другой метод вычисления мини' мального многочлена будет приведен в 4 6 настоящей главы. 8.43. Пример. Пусть последовательность эа, э,, ... являетсф линейной рекуррентпой последовательностью над полем определяемой рекуррентным соотношением энта энта + внтг + зн и ' 0 и вектором начального состояния (1, 1, О, 1).
Для того чтоб найти минимальный многочлен этой последовательности, будета действовать так же, как при доказательстве теоремы 8.42. Можно Взять )е (х) = ха — ха — х — 1 =- ха + ха + х + 1 б Ге (х). Тогда из (8.10) следует, что й, (х) = х'+ х. Наибольший общи делитель многочленов га (х) и Ь„(х) равен с( (х) = х'+ 1, таким образом, минимальный многочлен последовательности К,' э„...
равняется и (х) = га (х)Ыг((х) =- хе+ х+ 1. Легко пр ' верить, что наша последовательность удовлетворяет линейном рекуррентному соотношению э а=э г+э, п=О, 1„ что находится в соответствии с общей теорией. Заметим, ч огд (и (х)) равен 3 и совпадает с минимальным периодом наш последовательности (ср. с примером 8.41). В теореме 8.44 мы пока жем, что это справедливо и в общем случае.
Минимальный многочлеи играет ведущую роль при определе-', нии минимального периода линейной рекуррентной последова тельности. Это видно, например, из следующего результата;,. 8.44. Теорема. Пусть эе, э„... — однородная линейная рв.' куррентная последовательность над полем Еч с минимальнын мно;: гочленом т (х) Е (('ч (х). Тогда минимальйый период этной по-'. следовательности равняется огд (т (х)). Доказательство. Если г — минимальный период последова ( тельности эа, э,, ..., а п„— ее предпериод, то з„= з„для всех,. и ) гге. Значит, наша последовательность удовлетворяет одно-", родному рекуррентному соотношению в,+,+,=э,+,„п=О, 1, ....
Тогда по теореме 8.42 многочлен и (х) делит многочлен х'"+" — а — хае = хле (х' — 1). Отсюда получаем, что и (х) имеет виги(г и (х) = х" д (х), где Ь < и,, а д (х) Е ((', (х 1, у (0) Ф 0 и у (х)1 делит х' — 1. Из определения порядка многочлена следует, что„. огт( (т (х)) = огг((у (х)) ( г. С другой стороны, по творе 8.27 г делит огд (гп (х)), откуда и следует, что г = огд (т (хЦ, ( (," 4 4. Минимальный многочлен 527 8,45. ПРимеР. ПУсть аа, з,, ...
— линейнаЯ одноРоднаЯ по- следовательность над полем Ка, удовлетворяющая рекуррентному соотношению л„„= з„„+ з„, и =- О, 1..., с вектором на- чального состояния (1, 1, 1, О, 1). Следуя методу доказательства теоремы 8.42, возьмем га (х) = ха — х — 1 = х'+ х+ 1 ~ с !('„!х).
Из (8.10) получаем, что Ьа (х) =- ха+ ха + ха. Тогда ,! (х! =- х' + х + 1, и, таким образом, минимальный многочлен гл (х) нашей последовательности равен (е (х)Я (х) = ха + ха + 1. Так как огд (т (х)) =- 7, то отсюда по теореме 8.44 получаем, что минимальный период нашей последовательности равен 7 (ср, с примером 8.18). П.
Из приведенного только что примера видно, как можно на- ходить минимальный период линейной рекуррентной последо- вательности, не вычисляя ее членов. Этот метод особенно эффекти- вен, если в нашем распоряжении имеется таблица порядков ыногочленов. Так как такие таблицы обычно включают в себя лишь сведения о порядках неприводимых многочленов (см.
4 2, гл. 10), для нахождения порядка данного многочлена необходимо воспользоваться теоремами 3.8 и 3.9 (ср, с примером 3.10). 8.46. Пример. Метод, использованный в примере 8.45, мож- но также применять и в случае неоднородной линейной рекур- рентной последовательности. Пусть з, з„ ... — последователь- ность над полем !г'а, удовлетворяющая рекуррентному соотно- шению з„„=з„+а+а„„+з„+1, п=О, 1, ..., с вектором начального состояния (1, 1, О, 1). В соответствии с (8.5) эту же последовательность можно получить с помощью однородного линейного рекуррентного соотношения за~а = знеа+ знеа+ зн~ и = О выбирая вектор начального состояния равным (1, 1, О. 1, 0). Дей- ствуя так же, как в примере 8.45, находим соответствующий ха- рактеристический многочлен ! (х) = х'+ ха + ха + 1 == (х + 1)а (х' + х + П Е Ка 1х), который в данном случае совпадает с минимальным многочленом (х) нашей последовательности.
Так как по теореме 3.8 ого ((х+ 1)') =- 4, а огг((х'+ х+ 1) = 3, изтеоремы 3.9следует, что огг! (и (х)) = 12. Поэтому последовательность з„з„... яв- ляется чисто периодической последовательностью с минимальным периодом, равным 12. П 8.47. Пример. Рассмотрим линейную рекуррентную последо- вательность за, з,, ... над полем !Т„задаваемую рекуррентным соотношением а = О, 1, ". = за+а + за+и 528 Гл.
8. Лннейные ренуррентные ооеледонательностн с вектором начального состояния (1, О, 1, 0). Тогда хе) а+ (а — характеристический многочлен нашей последовательности' в силу того, что ни х, ни х'+ х + 1 не является характеристи ским многочленом зтой последовательности, получаем т (х~'" = х'+ х" + х, Таким образом, последовательность з,, з, является периодической, но не чисто периодической, а ее ми мальный период равняется огд (т (х)) =- 7. 8.48. Теорема. Пусть з„, з,, ... — однородная линейная '' куррентная последовательность над полем 1'ч, а Ь вЂ” некото натуральное число. Тогда минимальный многочлен т, (х) сдви тои последовательности зь, зь„, ... делит минимальный мн" член т (х) исходной последовательности зе, з,...,.
Если з, зы ...': чисто периодическая последовательность, то ап, (х) = т (х). ': Доказательство. Для того чтобы доказать первое утвержде ' в силу теоремы 8.42 достаточно показать, что любое однород" линейное рекуррентное соотношение, которому удовлетво исходная последовательность з,, з,, ..., также справедливо, для сдвинутой последовательности. Последнее очевидно.
Д доказательства второго утверждения рассмотрим однородное, нейное рекуррентное соотношение ьа,ь.ь = аь еза,ь,ь ~ + . -)- а,ьн,ь, и = О, 1, .„, которому удовлетворяет сдвинутая последовательность. Пу', г — период последовательности з,, з„ ..., так что з„,„ =- з„ всех п )~ О. Выберем целое число с, для которого сг ) Ь. Тог'' используя линейное рекуррентное соотношение, в котором',, заменено на п + сг — Ь, и учитывая свойство периодичности, лучаем, что з„,а — — окпз„,ь, + .
-1 аез„, п )О. Последнее означает, что последовательность з„з„... удо творяет тому же линейному рекуррентному соотношению, что:;; сдвинутая последовательность. Применяя вновь теорему 8. получаем, что т, (х) = т (х), 8.49. Пример. Пусть з„, з,, ... — линейная рекуррентная следовательность над полем ее рассмотренная в примере 84' Ее минимальный многочлен равен х'+ х'+ х, в то время к' минимальный многочлен сдвинутой последовательности з,, з,„" равняется х'+ х + ! и является делителем многочлена х"-, + х'+ х. Этот пример показывает, что второе утверждение ремы 8.48 может не выполняться в случае, если з,, з„...
является чисто периодической последовательностью. 4 4. Манив»ьльиыа иногочлен 529 8,8О. Теорема. Пусть 1' (х) Е Кч [х! — нормированный не- р»»вод»»мый многочлен над полел» Кч, и пус»пь э„, э», ... — одно- родное линейная рекуррентная последовательность над полем не являющаяся нулевой последовательностью. Если 1(х)— х»»ри»»»перистический многочлен последовательности эы л», ..., то ;и равняется ее минимальному многочлену т (х).
доказательство. Так как по теореме 8.42 минимальный ш»огочлеи т (х) нашей последовательности должен делить миогочлен »'(х), то в силу неприводимости )'(х) получаем, что либо т (х) =- 1, либо т (х) = — )' (х). Однако т (х) =- ! только для нулевой последовательности. Отсюда вытекает утверждение »»орсмы.
П Еуществует общий критерий для определения того, является ли харак геристический многочлен линейного рекуррентного соот- ношения, определяющего данную линейную рекуррентную по- следовательность, одновременно и минимальным многочленом »пгй последовательности. 8.51. Теорема. Пусть э,, э»,...— последовательность элементов поля Кч, удовлетворяющая линейному рекуррен»иному соо»пноше- нию )»-го» порядка с характеристическим многочленом»' (х) Р Гч (х1. Тогда ! (х) совпадает с минимальным многочленол» мной последа. еап»ельности в том и только том случае, когда векторы состоя- ний' з„, з», ..., вел линейно независимы над полем Гч.
Дока;»ательство. 1Тредположим, что 1 (х) является минималь- ным многочленом нашей последовательности. Если векторы а,, з,, ... ..., э„» линейно зависимы над полем Гл, то найдутся элементы Ьь, Ь!...., Ька р К», не все равные О, такие, что Ь,з„+ Ь!з, + ... .. -- Ьь»з„» =- О. Рассмотрим матрицу А из (8.3), соответствую- щую данному линейному рекуррентному соотношению. Умножая все члены приведенного выше равенства иа степени матрицы А, ит равенства (8.4) получаем Ьь»зп + Ь»вь»» + ° ° + Ьд»ап»д» = О, п = О, 1, В частности, + 1, , „, О для всех и = О» " < Ь 1 то э„ .
О дла всех »» Э. ч»о противоречит тому, что минимальный многочлен» (х) рассмат- риваемой последовательности не является постоянным (т. в. имеет положительную степень). Тогда пусть» ) ! — наибольший инала которого Ь» ~ О. Отсюда вытекает, что последователь- '»ост~ ь„, эы ... удовлетворяет однородному линейному рекурреит- иг"»у соотношению»тго порядка, где 1 < я. Это противоречит пред»»оложению, что 1(х) является минимальным многочленом.
аким образом, мы показали, что векторы а,, з»...., зьл ли- неино независимы иад полем Е . 2» Зми 2»3 Гл. ж Лннейные ренуррентные ооследовательностн Обратно. предположим. что зв, з,... з„, линейно незя симы над >' . Так как за эь О, минимальный многочлен нашей следовательностп имеет положительную степень.
Если ) (х);; является м>п<имальных< многочленом. последовательность э<о э,„; должна удовлетворять однородному линейному рекуррент соотношению т-го порядка с коэффициентами из Ге для некото ' 1 .. т к: я. Пусть это соотношение имеет вид эн<т ив< — >эн«н — > > ' ' + авв„, П О, 1, Однако отсюда следует равенство э а„,в„,, что противоречиг предположени>о о линейной независимости торов з<о з,, ..., аа,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
