Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 125
Текст из файла (страница 125)
21, а с еще более общей точки зрения — в Э 5 гл. 9 настоящей монографии. Теорема 8.7 в сущности была получена в работе Мап!е[ 1! !. Теорема 8. ! ! является частным случаем результата, доказанного в статье Магд 115 ]. Матрица А из (8.3), являющаяся сопровождающей матрицей характеристического мпогочлена рекуррентной последовательности, была введена в работе Вгеппег (1 1; там же можно найти доказательство теоремы 8.!3. Позднее матричные методы начали интенсивно использоваться при проведении исследований в этой области (см. Оо!опзЬ [!!. В!г<ЬаП, К]з!епЫа!! (! ). Е!враз 1! 1, РПед!апг1 (11.
5!егп, РНегйапд (! 1 и Мепбе]зоЛп [! И Эти методы имеют то преимущество, что они могут быть 'гакже применены к линейным рекуррентным последовательно- Гл. 8. Линейные реиуррентные последовательности стям над более общими алгебраическими структурами (см., н пример, Ьйедегге)1ег [6 !). Вычислительные аспекты матричны методов обсуждались в работах Ката!, ЯппЬ, Рви, 5[аида [1 и [.а1ав!ес [1 !. Доказательства формулы для порядка группы 6Е (л, [р ' можно найти, например, в книгах Аг1)п [7, сЬ. 4 ), Саггп)сЬ [4, сЬ. !О), [т)скзоп [7, раг1 !1, сЬ.
! ! или )ч[евгпап [1, сЬ. 7. В иих можно также обнаружить формулы для порядков друг ' матричных групп над полем [Ге, таких, как специальные лине ные группы, ортогональные группы или симплектические групп " Теоретико-групповой аспект этих матричных групп обсуждаетс например, в работах Аг1!и [5 ), [6), Сагв!сЬае! [4, сЬ. 10), С ча!1еу [2), [т)с)своп [7, раг1!1), Р!ецдоппе [2! и 0)хоп [1!. следние исследования по теории представлений таких гру можно найти в статье Вг~шчазап [! ). Формула для поряд группы 6Е ()т, Ге) является частным случаем формулы для чис гн х л-матриц ранга г иад полем Ги, которая имеет вид т — ! Ч< '- Мгт П (Чы — ! ) (Чи — ! ) (Ч ч-1 ..
! ) — 1, где 1 ( г '. 1п!и (т, и), Этот результат для случая простого, был получен в работе 1.апс[зЬегд [! !. Доказательства этой форму," момсно найти также в работах АгдЬ!г)аг[е, Ре1егВ [1), Вогор [[; Р!зЬег, А!ехапс[ег [! !. В статье Рог1ег, к)че!апс[ [! ) аналогичн' формула доказана для случая. когда задано фиксированное чис з ~~ г линейно независимых строк в матрице. В работе К!е)п [ . рассматривается число т х п-матриц над полем Г„, для котор все миноры порядка ппп (тл, и) или все миноры порядка не б пйп (тп, л) являются ненулевыми. Ли в работе 1.ее А. [! ! показйьне что не существует матрицы размера (Ч вЂ” 1) х Ч над полем Г: в которой все миноры порядков Ч вЂ” ! и Ч вЂ” 2 являются иену вымя.
В работе Саг!Вг. Нос[нез [4 ! получено число прямоугол'' ных матриц заданного ранга. у которых ранги подматриц им предписанные заранее значения, а в работах ВгаМеу, СагИх П и РВЬег, А!ехапдег [1 ! получено число таких матриц с предии санными значениями сумм по строкам и столбцам. Другие перй) числительные задачи для прямоугольных матриц над полем г) изучались в работах СагИг, Нодцез [2), Оаук!п [2 ), Гцйоп ).
[8), [!О), Нос)нез [7! и К!пч [1). Для квадратных матриц зада[44 ного порядка над почем [Г, рассматривались более специальн, перечислительные задачи. Так, в работе Вцс)сЬ!ез1ег [1 ! определен число таких матриц с заданными значениями ранга и следа (сМ( также статью )оЬпзоп, Рог1ег, ьтаг!пеац [! ), где рассматриваетсМ случай полного ранга). Райнер (Ке)пег [1)) и Герстенхабер (ьае „, з1епЬаЬег [1 !) нашли число матриц. имеющих заданный характе Коммеитарии 56э Ристический многочлен, а Карлиц и Ходжес (СагИг, Ног[дев [3)) получилн формулу для числа простых матриц.
В статьях Г!пе, Негз1е!п [11 и бегз1еппа(зег 1! 1 доказано, что имеется в точности Ч ' —" нильпотентных и х и-матриц над полем гч, а в статье ВоПгпап, Йаш!гег [! ) получено число нильпотентнйх матриц над х;(т) заданного порядка и ранга. Число циркулянтных матриц с заданным рангом подсчитано в работе Вег[е[сагпр 121, а в статьях СагП1г 1511, [541, СагП1г, Ног(дев [! 1 получены соответственно число кососимметрических, симметрических и эрмитовых чзтриц заданного ранга, Дальнейшее развитие этого направления проведено в работе МасФППашз (31. В работе Вгав(еу, СагИг 111 изучались те же вопросы с дополнительными ограничениями па суммы по строкам и столбцам. Приложения полученных результатов можно найти в статье Мас0оийаП (11, В статье Ре!1, Р!пе [ ! ! определено число упорядоченных пар коммутирующих и х и- матриц над полем Гч, аналогичные вопросы рассматривались Карлицом (СагП1г [921).
В работе Кипя [11 получено число не- вырожденных матриц, коммутирующих с данной блочно-диагональной матрицей. Эквивалентность и классы подобия для матриц изучались в работах Вгав (еу [! 1, СагП!г (!04 1, СагИг, Нодяез [3! н бои [! 1, В статье Вгав!еу, МцПеп [! 1 найдено число диагонализируемых матриц, имеющих заданное число различных собственных значений.
Для фиксированной квадратной матрицы А над полем Гч Дайкин ((Заук1п 11 1) определил число различных матриц вида г (А), имеющих заданный ранг, когда 1 пробегает К [х[. По поводу результатов о числе решений матричных уравнений мы отсылаем читателя к комментариям к $ 2 гл, 6 настоящей монографии.
С этими перечислительными задачами о матрицах непосредственно связана задача перечисления подпространств векторных пространств над полем Еч. В этой связи Диксон (Э!с[гзоп 17, раг1 1, с!1. 4]) и Мур (Мооге [4 1) показали, что число г-мерных подпространств л-мерного векторного пространства над полем [(',, задается формулой Ц(де — ' — !)(д' — ' — 1) — ', где 1~(г <и. ю=-0 Как определил Нивен (Кбчеп 11 1), наименьшее общее кратное поридков всех элементов гРУппы 6Ь (й, Гч) Равно Р'М, где Р— характеристика поля гч, е — наименьшее целое число, для которого р > л, а й4 — наименьшее общее кратное чисел д — 1, ч' — 1, ..., де — !.
Эти результаты были дополнены и обобщены в Работе МагзЫ[ 1! ). Так, утверждение о том, что порядок матрицы А в 6(. (й, Кч) делит 570 Гл. З, Лннеяные рекуррентные аостедоватевьностн можно усилить до утверждения, что этот порядок делит р'М, Аналог результата Нивена для ОЕ й. 31(и)) был получен в ра,' потах Оау|з 1! )и Мах!]е!б [11. Кроме того, Нивен в той же работ М!уеп 1! 1 получил алгоритм для определения порядка элемента. из бЕ (тт, [',). Исследованию порядков матриц посвящены такж " работы Во!]шап [11, Оа! 1!1, РП]тпоге, Магх !11, Оагц 1! ! и ! !]пеЬогд !2, сЬ. 32, 33]. Теория линейных рекуррентных последовательностей на ' конечными полями помимо применения к анализу и синтезу р, гистров сдвига с обратной связью имеет еще одно важное при, менение, а именно в теории кодирования„особенно в теориц,' циклических кодов (см. э" 2 гл.
9 настоящей монографии). Пе ',", вымн работами по связи линейных рекуррентных последователь' ностей н регистров сдвига с обратной связью с теорией кодир ' ванна были работы АЬгашзоп [! 1, Огееп, 5ап 5оцс!е 1! 1, НцЛта П 1, 12], Казаяй [! 1, Ма!!зоп, 5о!опюп 1! 1, Ре]егэоп 1! 1, Ргап ' [11, 5!егп, Гг]ед!апд [!1, т'а!е 1!1, Ее(!егЬегй [11 и Е]ег!ег !1 ' 131. См. также Маээеу [31, Му]с]се!!уе!! 1! ), Е!ег!ег [51 и Габид.
лин [! ], а кроме того, монографии АзЬ 11, сЬ. 51, 1 ш [2, сЬ. 4) Ре!егэоп, Ъе]т]оп 111. Приложения к вычислениям в Гч и Г [ ' рассматривались в работах Ваг!ее, 5сЬпербег 11]„Вег[е]са [4, сЬ. 21, ВЬапц Мцгйу, 5атрай [! 1, ОП1 12, сЬ. 61, Тапа КазаЬага, Техн]са, КазаЬага !! 1и 1ЧП]е!1 161, Алгоритм Минь (М|япо!!е !1 1) для определения степени поля разложения мно члена над полем Ге также основывается на свойствах линейн" рекуррентных последовательностей. Другие связи линейных куррентных последовательностей с разложением многочленов множители можно найти в статье %П!е!! [51. Свойства линейн рекуррентных последовательностей 2-го порядка над конечн простыми полями применялись в работе ЬПебегге!!ег, РоЬ]пз" 11) для анализа конечных луп Вола.
Применения линейных р, куррентных последовательностей над полем Кт в криптографи, обсуждаются в работе Ве]сег. Р]рег [! 1. Слоэн (5!папе [21) уп ' минает о связях между криптографией и регистрами сдвига с обр ратной связью. Обзор практических приложений линейных ре куррентных последовательностей дается в работах Оо!ошЬ [3" сЬ. 11, [4, сЬ. ! 1. О некоторых специальных приложениях посл ., довательностей максимального периода будет упоминаться нижеФ в комментариях к э 2 настоящей главы.
Линейные рекуррентные последовательности можно рассматд) ривать н над более общими алгебраическими структурами. Уор (Юагт] 11 1) изучал рекуррентные последовательности над произ' вольными полями, а позднее в работах Фагд 1!31, 1!5) он иачаттт изучать линейные рекуррентные последовательности иад комму тативными кольцами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
