Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
состоящ системы Ж (или графом матрицы А) называется ориентирована граф,
имеющий qn вершин, которые поставлены во взаимно однЦ значиое
соответствие со всеми возможными внутренними соста ниями ЛМС Ж, При этом
вершины s2 и s2 соединены дугой, щей из Si в s2, тогда и только тогда,
когда s2 = A$L. В этом сл| чае мы говорим, что переходит в s2. Путем
длины г в гра состоянии называется последовательность из г дуг Ьъ Ь2,
&
и г "г 1 вершин Vu v2, ..., иг+ь такая, что для всех i ~ 1,2, дуга
направлена из вершины vL в вершину ui+l. Если все различны, за
исключением того, что ur+i = щ, то такой путь на*# зывается циклом длины
г. Если vt для любого i - 1, 2, г является единственной вершиной,
переходящей в ui+1, а едийу ственнон вершиной, переходящей в уь является
vr, то такой дик называется циклом без подходов. Так, на рис. 9.8
изображен дик без подходов длины 8.
ft
§ 5. Линейные модулярные системы
649
Рис, 9.8,
Порядок данного состояния s равняется наименьшему положительному числу tt
такому, что A*s = s. Таким образом, порядок s совпадает с длиной цикла,
содержащего s, Далее, пусть матрица А невырожденна, т. е. det А ф 0,
Очевидно, что в этом случае соответствующий граф состояний состоит из
циклов без подходов. Порядок характеристической матрицы Л равняется
наименьшему положительному числу t, такому, что А* = /, где / - единичная
матрица размера пхп.
9.93. Лемма. Если tiy ,,,, tk - все значения, принимаемые по-рявками
состояний некоторой ЛМС с невырожденной характеристической матрицей А, то
порядок матрицы А равняется
НОК (tt> tk).
Доказательство. Пусть t- порядок матрицы Л, а - - НОК ...,4)* Так как = s
для всех s, то величина t должна делиться на С, Кроме того, (А1' - I) s =
0 для всех s, отсюда А1' = /. Таким образом, t'^ t и, следовательно, t~t\
?
9.94. Лемма. Пусть матрица А имеет вид
л-И 0
~ \ О А%,
где Л* и Л2 - квадратные матрицы, а ^ q1 ) и ) - два
состояния, представленных в соответствии с разбиением матрицы А и имеющих
порядки соответственно tx и 12. Тогда порядок состояния s ^ равняется
t = НОК {h, h).
Доказательство. Утверждение леммы непосредственно вытекает из того, что
тогда и только тогда, когда
и A*2$s - s3. ?
Пусть JC будет ЛМС с невырожденной основной характеристической матрицей
Л. Тогда граф состояний системы JC с точностью До изоморфизма
определяется формальной суммой вида
^ " (rtn ^i) ~\~ 4* * ¦ '
650
Гл. 9. Приложения конечных полей
-
где пара (nit 4) означает, что число циклов длины 4 равно ? называется
цикловой суммой системы JC (или матрицы Л) а пара (я*, 4) называется ее
цикловым членом. Предполагается
что цикловые члены перестановочны относительно операции и при этом (п\ ()
4- (ft\ t} = (п ~Ь 0-
¦ Ш
Й
¦Щ * %
иш
\
Пусть матрица Л имеет внд
At 0
о
Лз
•
• >L 'I'a
*ч*Д
stK ¦ <ь
• я
¦у?щ
t
т
порядка
где Лх и Л3 - квадратные матрицы, н пусть граф состояний, сой
ответствующий матрице Ai} I -¦ I, 2, имеет nt циклов длины i
Таким образом, имеется пА состояний вида ^ *г
и n%t% состояний вида ^ s j порядка t2. По лемме 9.94 граф
стояний матрицы Л должен содержать П\пАА состояний поряд НОК (tt, 4) и
соответственно
т
Ж
:-т
nyn^tJHQК (4> У = пфг)АО]Х (4* А)
циклов длины НОК (У 4)-
Произведение двух цикловых членов является циклов! членом, определяемым
формулой
(ft-i> 4)'{п3, А) - (п^п-зНОД {A, 44 НОК (4т 4))-
(Л
Mt. f, *
¦\t}k
Произведение двух цикловых сумм определяется как формам ная сумма всех
возможных попарных произведений циклов членов из соответствующих цикловых
сумм. Другими слова это произведение вычисляется в соответствии с
законами дистрнб тивности.
V*:
¦II
Ш
9.95. Теорема. Если
• Н
А
А
0
о
•• i
-г-
к1:?
Ф&I
if
&
а цикловые суммы, соответствующие Ах и Л2, обозначены рез Ej и 2а, то
цикловая сумма, соответствующая матрице А равняется XiX2.
>
Наша задача - иайти алгоритм для вычисления цикловоЦ суммы,
соответствующей ЛМС над полем Тя с невырожденной? характеристической
матрицей Л. Для этого нам потребуются которые понятия из теории матриц.
Характеристический мноЩ член квадратной матрицы М над полем Fg
определяется ка# del (*/ - М). Минимальным многочленом т (х) той же
матрицыМ называется нормированный многочлен минимальной степени над
-л К
•ЛП)
§ 5. Линейные модулярные системы
полем такой, что т (Л1) - 0, где 0 - нулевая матрица, дан нормированный
многочлен над полем Fg
г. сл и
ё(х)
•к
dk-lX
к- S
!- алх -f- и0,
о его сопровождающая матрица определяется как матрица вида
* G 0 0 ... О -я0
10 0 , . , 0 ах
М (g (х)) - 0 10 ... О -а2
И к
&k-l j
В этом случае многочлен g (ж) является и характеристическим и минимальным
многочленом матрицы М (g (х)).
Пусть М - квадратная матрица над полем |р9. a gx (ж), . ¦¦¦" gw (А) - ее
нормированные элементарные делители. Тогда про изведеиие gx (ж) ...&г,(х)
равняется характеристическому много члену матрицы Л1, и матрица М подобна
матрице
М (ft (х)) 0
о М (ft (х))
О
О
О
о
м (gw (X))
