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

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

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

Искомый зультат вытекает теперь из леммы 8.68, $ 6. Характериаапаа ланейиых последоаательиостей о47 ф 6. Характернзация линейных рекуррентных последовательностей Важной задачей является выяснение того, будет данная последовательность элементов поля Кр линейной рекуррентной последовательностью нлн нет. С теоретической точки зрения этот вопрос можно разрешить немедленно, так как линейные рекуррентние последовательности над полем Ер и только они являются периодическими последовательностями.

Однако периоды некоторых линейных рекуррентных последовательностей (даже сравнительно небольшого порядка) могут быть очень длиннымн, и на практике часто бывает невозможным определить природу данной последовательности на основании лишь этого критерия. Другие способы характеризации линейных рекуррентных последовательностей используют понятия линейной алгебры. Пусть за, в,, ... — произвольная последовательность элементов поля Гр. Для целых чисел и ) О, г ~» 1 введем понятие ганкелева определителя Вл За+1 ° гл+г-1 За+1 ° ° Варе Пл' = о> Ев+е 1. Зврс ° ° Вв«ас-1 связанного с этой последовательностью.

Как мы увидим дальше, линейные рекуррентные последовательности можно охарактеризовать в терминах обращения в нуль достаточного числа ганке- левых определителей, связанных с этой последовательностью. 8.73. Лемма. Пусть цв з,, ... — произвольная последовательность над полем Кр, и пусть и ) О, г )» ! — целые числа. Тогда из равенств !)»1 = Р» " = О следует равенство П„"+»1 — — О.

Доказательство. Для т)»О введем вектора = (з, д„м, ... ", 1 +, ~). Из равенства О„' = О следует, что векторы з, а„+1, .. , а„,, линейно зависимы над полем г . Если а„+,, ..., з„„, тоже линейно зависимы над г'р, то мы тут же получаем равенство о) Пл„~ =- О. В противном случае вектор з„является линейной комбинацией векторов а„+,, ..., зв+, ь Пусть з,'„= (з, вл«ьс) для т )» О.

Тогда векторы зл~ зл-ь1 " зл+е будучи строками равного нулю определителя рл»+", линейно ~анисимы над полем рр, Если з„', з,',+ь ..., з,'ч., 1 линейно зависимы над К, то, применяя линейное отображение ( ~. '(аа, а„..., а,) ~ Ер+ « — «(а1, ..., а,) ~ 'гр, ~~вручаем, что з„~1, з„,а, ..., з„„тоже линейно зависимы иад гр и, следовательно, !:)»!~.1 = О, В противном случае (если а„, а» 848 Гл.

8. Линейные ренуррентные последовательности з„',„..., з„'4, ) линейно независимы) получаем, что вектор а„' ' является линейной комбинацией з,'„з„' ь), „з,',+, ), и тогд применяя линейное отображение йт. (ао и„..., а, ), а,) Е Кд"' «-«(ао а), ..., а — )) Е К;)ю получаем, что з„„является линейной комбинацией векторов а з„„, ..., з„„,.

Йо в рассматриваемом случае ап есть линейна комбинация векторов з„„, ..., зн„,, Таким образом, вектор' з„.)), ..., з„, ), з,.).„являющиеся строками определителя 0'„+)'( линейно зависимы над Ке, откуда следует, что Р„'е) == О. о) 8.74. Теорема. 17оследовательность зо, в„... элементов поля . является линейной рекуррентной последовательностью тогда только тогда, когда суи(ествует положительное целое число г, кое, что Рм) =- О для всех (кроме, может быть, конечного чис ' и >»О. Доказательство. Предположим, что последовательность в„... удовлетворяет однородному линейному рекуррентному с ношению й-го порядка.

Для любого фиксированного п > О ра м+) ) смотрим определитель Р„'+ ' . В силу линейного рекуррентн соотношения, которому подчиняются элементы последоватед ности в,, з,, ..., (к + 1)-я строка определителя 0'„+ ' явля м+) ) линейной комбинацией первых я строк, и, следовательно, 0', м+) ) = О. Неоднородный случай сводится к однородному по форму (8,5). Необходимость доказана. Докажем достаточность. Пусть й + 1 — наименьшее н ральное число, такое, что Р„'+ ' = О для всех, кроме, мо й+) ) быть, конечного числа и > О.

Если й + 1 =- 1, то теорема до: зана. Рассмотрим случай я > 1. Тогда найдется целое т )» „ такое, что Р~~ "" =- О для всех п > т. Если Р,'~',~ =- О для не торого и, т, то по лемме 8.73 О) ' = — О для всех п > п„ противоречит выбору й+ 1. Следовательно, 0',"' Ф О для в и > т. Положим во =- (в„, вн,,, ..., з„,о). Заметим, что для в, И > т ВЕКТОРЫ В„З„„, ..., З„,ю бУДУЧИ СтРОКаМИ ОПРЕДЕЛ, теля 0~, ~~' = О, линейно зависимы над полем !о. В силу то. что О„~ О, векторы з„, зл,, о„+е ) линейно независн )е) над г'о, и, значит, з„,д является линейной комбинацией векто .

а +), ..., з„,о т. По индукции легко получить. что для вс и :. т вектор з„ является линейной комбинацией векторов а а „, ..., в ,„,. Последние представляют собой я векторов п странства Г +, а следовательно, существует ненулевой некто е-(-! (ао а). ", ае) Е Ке)', для которого выполняются равенст авва+ а)в м+ ° ° + аванта = 0 при т <и < т+А — 1 ° $6. Харантернаанна линейных последовательностей о49 Отсюда вытекает, что аоэ + ахен,~ + + ааэ„,а = О для всех и > т нли аеэа+ +ааэ + 1+ '' ' +ааэ а = О для всех и) О. 1 аким образом, показано, что последовательность э,, э„ ...

удовлетворяет однородному линейному рекуррентному соотношению, имеющему порядок не более чем т + я, П 8. 75. Теорема. Последовательность э,, в,, ... элементов из поля К является однородной линейной рекуррентной последовательностью с минимальным многочленом степени й тогда и только тогда, когда О~о' = — О для всех г )~ й + 1 и й + 1 — наименьшее натуральное число, для которого выполняется это равенство.

Доказательство. Докажем необходимость. Если данная рекуррентная последовательность является нулевой последовательностью, то необходимость условий очевидна. В случае когда последовательность отлична от нулевой, мы имеем я ) 1, и тогда Ва"' = О для всех г ) й + 1, так как (й + 1)-я строка определителя По"' является линейной комбинацией пе~вых й строк. В свою очередь из теоремы 8.51 следует, что 7)оо ' чь О. Таким образом, необходимость условий доказана для всех случаев.

Для доказательства достаточности допустим, что выполняются приведенные условия для ганкелевых определителей. Пользуясь леммой 8.73, индукцией по п можно показать, что 0~'1 = О для всех г ) й + ! и всех и ) О. В частности, Т)~ ~ 1 = О для всех п ). О, и тогда по теореме 8.71 последовательность ~, э,, ... является линейной рекуррентной последовательностью. Если ее минимальный многочлен имеет степень й, то, как мы уже показали выше, !7а~' = О для всех г ) д + 1 и й+ 1 является наименьшим натуральным числом, для которого выполняется это равенство.

Отсюда получаем, что й = я. (:) Если известно, что однородная линейная рекуррентная последовательность имеет минимальный многочлен степени я )~ 1, то сам минимальный многочлен полностью определяется первыми 2Я членами этой последовательности. Чтобы убедиться в этом, запишем уравнения (8.2) для и = О, 1, ..., й — 1 н получим систему из к линейных уравнений относительно неизвестных аа, .. аа ы являющихся коэффициентами искомого минимального многочлена. Определитель этой системы равняется 0оц ~, по теореме 8.51 17~~ю чй О.

Таким образом, рассматриваемая 'истема уравнений имеет единственное решение. зво Гл. 8. Линейные рекуррентные последовательностн Важным вопросом явлнется нахождение практического мета для вычисления минимального многочлена данной однородн линейной рекуррентной последовательности. Один такой м уже был предложен в процессе доказательства теоремы 8.4 Этот метод предполагает предварительное знание характерист ' ческого многочлена данной последовательности и основываетс на нахождении наибольшего общего делителя миогочленов н ' полем ((' .

Ниже мы приведем и обсудим другой метод нахождени минимальных многочленов. Этот метод представляет собой реку сивный алгоритм (так называемый алгоритм Берлекэмпа — Месса который после конечного числа шагов дает искомый минимальны многочлен при условии, что нам заранее известна верхняя гр . ница для степени искомого минимального многочлена. Пусть во, з,, ... — последовательность над полем Еч и 6 (х) = ~' л„х" — соответствующая производящая функция.

Для 1 а=о = О, 1, ... определим многочлены ух (х), )тз (х) С Г, (х), цел числа т; и элементы Ь, С 1'ч следУющим обРазом, Дла 1= полагаем ссо(х) =- 1, Ь„(х) = х, то =- О. (8.1 Затем последовательно полагаем Ь) равным коэффициенту п х) в у) (х) 6 (х) и арл (х) — — хс) (х) — Ь))тз (х), ~ Ь) ~ху)(х), если Ь)ФО, тн) оО, ( хй, (х) в противном случае, (8.

~ — т,, если Ьт~б, т; . О, тмт - —— 1 т, + 1 в противном случае, Если з„ в,, ... — однородная линейная рекуррентная послед ' вательность с минимальным многочленом степени Ь, то в резуль, тате мы получим, что два (х) равняется возвратному минималь, ному многочлену. Таким образом, искомый минимальный мно член т (х) определяется равенством т (х) =- хед,в (!)х).

Есл ' заранее известно лишь, что с(ед (т (х)) ч Ь. то положим г == ~й +' + 1)2 — твв)2~, где (у.( означает наибольшее целое число, и превосходящее у. Тогда минимальный многочлен т (х) анре ляется равенством т (х) =- х"ув„(!)х). В обоих случаях из ал ритма сразу же видно, что тл (х) зависит только от первых членов последовательности з,, з,, ..., з,„,. Следовательно, проч нзводящую функцию 6 (х) в алгоритме можно заменить многж членом 6„,(х) = ~; анхо. а=о 4 6.

Харантериаациа линейных цоследоаательиостей 551 8.78. Пример. Первые 8 членов однородной линейной рекуррентной последовательности над полем Кз порядка й ( 4 имеют „ид ф, 2, 1, 0„1, 2, 1, О. Для того чтобы найти ее минимальный миогочлен, применим алгоритм Берлекэмпа — Мессн с много- членом бт(х) = 2х+хз+ха+ 2хз+х' Е Гз(х1 вместо производящей функции б (х).

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

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