Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 143
Текст из файла (страница 143)
Теорема (формула полной реакции). Если дана ДМС с характеристическими матрицами А, В, С, )9, то с вЂ~ (1) з(1) = А'з(0)+ ~~ А'-' — 'Ви(1), 1=- 1, 2, ..., с-е ! (й) у(!) =СА'з(0)+ ~ Н(1 — !)и(1), ! =-О, 1, ..., 1 е где ~0, если !=О, (СА' — 'В, если ! )» 1. Доказательство. (!) Пусть в определении 9.90(5) Г = О, тогда з(1) = Аз(0)+ Вц(0), что доказывает (1) для 1 =- 1. Предположим, что (!) выполняетсн. для некоторого Г )» 1; тогда с-1 з(! ! 1) = А ~Агз(0)+ ~ А~ — ' — ~Ви(!) +Вы(1) = а=о = А~+'з(0)+ ~ А' — 'Вн(!), 1=о т е (!) справедливо и для Г+ 1.
648 Гл. 9. Приложения конечных полей (11) В силу и. (1) и определения 9.90(5) получаем, что с — ~ у (1) = С ( А 'з (0) + ~~ А ' — ' 'Вн (() ~ '- Оп (Г) = г=-о = СА'а(0)+ ~~ Н(1 — 1) и(!), 1.— -0 где Н (à — г) -:- СА' — ' — 'В для à — (,ъ 1 и Н (1 — 1) =- В дпя 1 — (=О.
П', В силу теоремы 9.92 (11) мы можем разложить выход произволь»' ной ЛМС на две компоненты; свободную компоненту у(1)е, = СА'з(0), и получаемую, когда и (г) — О для всех 1) О, и вынужденн компоненту у(Г)„„„- — — Д; Н((--!)н(1) а=О получаемую для случая а (0) = О. Если дана произвольная вх" ная последовательность и (г), 1 = О, 1, ..., и произвольное нача ное состояние а (0), то эти две компоненты можно определить отдельности, а затем сложить.
Оставшаяся часть этого параграфа будет посвящена изучен поведения ЛМС в автономном случае, т. е. когда и (г) =- О всех 1,е- О, Лля этого нам окажутся полезными некоторые по тия из теории графов. Если дана ЛМС .Х порядка н над полем с основной характеристической матрицей А, то графом состоян,' системы 4(' (или графом матрицы А) называется ориентированн ' граф, имеющий о" вери~ни, которые поставлены во взаимно одн, значное соответствие со всеми возможными внутренними сос ниЯми ЛМСи(г. Е!Ри этом веРшииы з, и зе соединены дУгой, ид щей из а, в з,, тогда и только тогда, когда ае =-- Аа„. В этом сл чае мы говорим, что а, переходит в а,. Путем длины г в гра состояний называется последовательность из г дуг бы Ь„..., Ь, и г+ 1 вершин ш, о,, ..., о„,, такая, что для всех! == 1, 2, ...,, дуга б; направлена из вершины о, в вершину о„,.
Если все ве: различны, за исключением того, что о„„= о„то такой путь на зывается циклом длины г. Если о; для любого 1 —.— 1, 2, ..., г — 1. является единственной вершиной, переходящей в и;„, а един;„ ственной верн~иной, переходящей в о,, является о„, то такой цик,, называется циклом без подходов. Так, на рис. 9.8 изображен цнк,, без подходов длины 8.
4 5. Лннейные мояулнрные системы Рнс. 9.8. Порядок данного состояния в равняется наименьшему положительному числу 1, таиому, что А'а =- в. Таким образом, порядок в совпадает с длиной цикла, содержащего в. Далее, пусть матрица А невырожденна, т. е, бе( А ~ О. Очевидно, что в этом случае соответствующий граф состояний состоит из циклов без подходов. Порядок характеристической матрицы А равняется наименьшему положительному числу 1, такому, что А' =- 1, где 1 — единичная матрица размера и ха. 9.93. Лемма.
Если 1,, ..., 1ь — все значения, принимаемые порядками состояний некоторой ЛМС с невырожденной характеристической матрицей А, то порядок матрицы А равняется НОК (1„..., 1„). Доказательство. Пусть 1 — порядок матрицы А, а — НОК (1,, ..., тд). Таи иак А'з = з для всех в, то величина должна делиться на 1'.
Кроме того, (А' — 1) в = 0 для всех а, отсюда А' =- 1. Таким образом, 1' ) 1 и, следовательно, 1= 1'. ( ) 9.94. Лемма. Пусть матрица А имеет вид А=( где А, и Ае — квадратные матрицы, а ( ' 1 и ( ) — два состояния, представленных в соответствии с разбиением матрицы А и имеющих порядки соответственно 1, и 1,.
Тогда порядок состояния з = 1 е' 1 равняется 1 = НОК (1,, 1е), ~ ее/ Доказательство. Утверждение леммы непосредственно вытекает из того, что Ас( "1 = / '1 тогда и только тогда, когда 4,'з, =-.. е, и А',з, = з„. П Пусть ик будет ЛМС с невырожденной основной характеристической матрицей А. Тогда граф состояний системы ич с точностью до изоморфизма определяется формальной суммой вида Х =(п„1,)+(и,, 1,)+ с(пя, 1„), Гл.
9. Приложения конечкых полей где пара (по (Д означает, что число циклов длины 1, равно и,.'" Х называется цикловой суммой системы и(г (или матрицы А) а пара (п;, ~;) называется ее цикловым членом. Предполагается, что цикловые члены перестановочны относительно операции -Г,, и при этом (и', 1) + (и", т) = (и' .+ п", Е~). Пусть матрица А имеет вид 0 А, где А, и А, — квадратные матрицы, и пусть граф состояний, сор ответствующий матрице Ао ~ =- !, 2, имеет п~ циклов длины Таким образом, имеется п1~1 состояний вида (,') порядка гот и п,(к состоЯний вида ( ) поРЯдка (,.
По лемме 9,94 гРаф сот 'ч кч стояний матрицы А должен содержать п,пч(1г, состояний пори НОК (т„ге) и соответственно тт п,пч(1(,~'НОК (Г„~,) = п,п,НОД (го ~,) циклов длины НОК (~„, 1,). Произведение двух цикловых членов является циклов членом, определяемым формулой (п,, Г,). (п,, Гч) = (пхп,НОД (Г„Г,), НОК ((,, 1,)). Произведение двух цикловых сумм определяется как формал' ная сумма всех возможных попарных произведений циклов членов из соответствующих цикловых сумм.
Другими словам' это произведение вычисляется в соответствии с законами дистриб ' ти в ности. 9.95. Теорема. Если А=~О А,) а цикковые суммы, соответствующие А1 и А„обозначены рез Х1 и Х„то цикловая сумма, соответствующая матрице А' равняется Х„Х,. Наша задача — найти алгоритм для вычисления цикловойй суммы, соответствующей ЛМС над полем Гч с невырождениой' характеристической матрицей А.
Для этого йам потребуются не.' которые понятия из теории матриц. Характеристический много",. член квадратной матрицы М над полем гч определяется каи, де( (хУ вЂ” М). Минимальным многочленом т (х) той же матрицы М' называется нормированный многочлен минимальной степени иадк 65. 1 5. Линейные модулнрные системы полем Ге, такой, что т (М) --= О, где 0 — нулевая матрица. Если дая нормированный многочлен над полем Ге а (х) =: х" 1 а„тх~ — '; а,х + а,, то его еонровоткдаюи!ая матрица определяется как матрица вид, гО 0 0 ...0 — а, 1 0 0 ...Π— -а, 0 ! 0 ...0 — ае М (д(х)) 0 0 0 ...1 — а„„ В этом случае многочлен а (х) является и характеристическим и минимальным многочленом матрицы М (а (х)).
Пусть М вЂ” квадратная матрица над полем !)'е, а а, (х), . , д (х) — ее нормированные элементарные делители, Тогда про пзведение дт (х) ... д (х) равняется характеристическому много члену матрицы М, и матрица М подобна матрице М (дт (х)) 0 0 М (де (х)) 0 0 О 0 М(а (х)) т. е, М = Р 'МеР, где Р— некоторая невырожденная матрица пад полем г . Матрица М* называется рациональной канонической формой матрицы М, а подматрицы М (а; (х)) называются элементарными блоками матрицы М'. Пусть невырожденная матрица А является основной характеристической матрицей ЛМС над полем Ге.
Для того чтобы найти ес цикловую сумму, матрицу А можно заменить подобной матрицей. Таким образом, вместо А можно рассматривать рациональную каноническую форму А * матрицы А. Применяя теорему 9.95, по индукции получаем следующее. Пусть |т (х), ..., й„(х) — нормированные элементарные делители матрицы А, и пусть Х;— цикловая сумма сопровождающей матрицы М (хч (х)).
Тогда цикловая сумма Х матрицы А*, а следовательно, и матрицы А определяется формулой Пусть характеристический многочлен ) (х) матрицы А представлен в виде Г ) (х) = П р;(х)'т, ао2 Гл. 9. Приложения конечных полей где рг (х) — различные нормированные неприводимые многочленЫ~ над полем Гч. Тогда элементарные делители матрицы А имеют! вид О» рг(х)'и, рг(х)'и, ..., р;(х) г, 1 = 1, 2, . е„) е;.,) . ).е;»,.'- О, ем+ем+ +ех»! —— е,. Минимальный многочлен матрицы А равняется т(х) = 1! р~(х)'п. !=о Остается определить цикловые суммы элементарных блоко М (йц (х)) матрицы А ", где йц (х) --= р (х)', а р (х) — некоторый нормированный неприводимый делитель многочлена ! (х), Слеч',.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
