Шпоры по дискре (3 семестр)

10. (2 из 2) Способы вычисления обратного элемента конечного поля

11. (1 из 1) Существование и единственность конечного поля

Теперь узнаем как пункт 2 связан с пунктом 3

Пример 2: – конечное поле, – простые числа. , (найти обратный), ,

, - корень ,

такие, что , т.е

.

/продолжение примера 1/

4)

, т.к. многочлены неприводимы.

По алгоритму Евклида:

|

x³+x²+x |

-x²+1

-x²-x-1

Теорема: – простого числа и – конечное поле, т.ч. | (с точностью до изоморфизма)

◄Рассмотрим над .

Пусть – минимальное поле разложения многочлена над .

Пусть - минимальное поле разложения многочлена над . Рассмотрим множество .

Покажем, что – поле. Достаточно показать, что :

(все это замкнутость)

Рассмотрим случай а):

Т.к. , , то .

б) Покажем, что

Индукция по параметру : – утверждение верно.

Пусть верно для //т.к. по биному Ньютона: //, т.к. (здесь - биноминальный коэффициент).

Итак , т.е. -поле, но - минимальное поле разложения .

Проверим, есть ли в кратные корни. Найдем кратных корней нет

Единственность: пусть . Но и - минимальные поля разложения многочлена над по теореме о единственности минимальных полей разложения ►

12. (1 из 3) λ -матрицы над полем. Элементарные преобразования. Канонический вид λ –матрицы

12. (2 из 3) λ -матрицы над полем. Элементарные преобразования. Канонический вид λ –матрицы

Определение: -матрица над полем – матрица над , т.е. ее элементы принадлежат . (будут рассматриваться квадратные матрицы) (-матрицей над полем назывется матрица, которой принадлежат )

Пример: , ,

Определение: Элементарными преобразованиями -матрицы называются:

1) умножение строка (столбца) на ненулевой элемент из

2) прибавление к любой строке (столбцу) другой строки(столбца), умноженной на элемент из .

Пример:  /ко 2 столбцу + 1 столбец /

Замечание: преобразования 1 и 2 позволяют осуществить произвольную перестановку столбцов (строк). Действительно:

Определение: -матрицы и называются эквивалентными, если -матрица получается из -матрицы с помощью элементарных преобразований -матрицы . Обозначение: .

Замечание: Элементарному преобразованию 1) соответствует исходная матрица, умноженная на матрицу =(см ниже) (CP^* - обратимые элементы ) слева для строк (справа для столбцов). Элементарному преобразованию 2) – на матрицу =(см ниже) для строк слева (столбцов – справа) (к -ой строке прибавляется -ая строка умноженная на .

А₁= А₂= A=

Определение: -матрицы -матрицы и такие, что:

а) , – обратимые -матрицы (т.е. -обратимая, если , такая что )

б)

Замечание: (критерий) -матрица обратима <=> является обратимым элементом в (элементы поля Р являются обратимыми элементами кольца многочленов, например - необратима, т.к. , а - обратимая, т.к. ).

12. (3 из 3) λ -матрицы над полем. Элементарные преобразования. Канонический вид λ –матрицы

13. (1 из 4) Существование канонического вида -матрицы

Определение: -матрица над полем называется канонической (или имеет канонический вид), если она имеет следующий вид: , где

1) – унитарные многочлены (т.е. старший коэффициент равен 1)

2) если , то и .

Пример: A=(см выше) - делят друг друга

Определение: -матрица над полем называется канонической (или имеет канонический вид), если она имеет следующий вид: , где

1) – унитарные многочлены (т.е. старший коэффициент равен 1)

2) если , то и .

Пример: - делят друг друга

Теорема:  -матрица над полем – -матрица в канонической форме, т.ч. .

◄Пусть – -матрица размера . Доказательство проведем индукцией по параметру :

1) утверждение очевидно

2) Пусть верно для , докажем для :

Если – нулевая, т.е. – каноническая -матрица. Если – ненулевая (т.е существует элемент матрицы, отличный от 0), то выберем элемент матрицы , такой что и – min элемент среди всех элементов матрицы . Перестановкой строк и столбцов добьемся чтобы стоял в левом верхнем углу , т.е.

13. (2 из 4) Существование канонического вида -матрицы

13. (3 из 4) Существование канонического вида -матрицы

. Рассмотрим 1-ый случай: , . Тогда умножаем 1-ый столбец на и вычтем из -го столбца получим, что столбец с номером I имеет вид , где . В результате добьемся .

Рассмотрим 2-ой случай: (не делит). Тогда поделим на с остатком, т.е. , . Тогда вычитая из -го столбца 1-ый столбец, умноженный на получим . Т.о за конечное число элементарных преобразований добьемся того, что . Аналогичным образом добьемся того, что

. Далее возможно два случая:

1) , где

2) такие что . Тогда к 1-ой строке матрицы прибавим строку с номером , т.е. .

Пусть , . Тогда из -го столбца вычтем -ый столбец, умноженный на и получим: . Выполняя соответствующие элементарные преобразования, добьемся того, чтобы , причем , . При этом было выполнено конечное число элементарных преобразований, т.к. , , где – какой либо многочлен.

По предположению индукции для матрицы т.ч.

13. (4 из 4) Существование канонического вида -матрицы

14. (1 из 2) Инвариантные делители λ-матрицы. Свойства инвариантных делителей

Но свойство делимости элементов матрицы на не зависит от элементарных преобразований над . Тогда делит любой элемент . Т.о. , причем если – унитарный многочлен, то - матрица в канонической форме►

Пример: над

Берем элемент ненулевой минимальной степени: . Делим с остатком на , частное 1, остаток 1.

А~~~~. Выполняя эти элементарные преобразования, но уже для получим

Определение: K-тым инвариантным делителем -матрицы над полем называется унитарный НОД всех миноров матрицы порядка , если не все они равны , и в противном случае. Обозначается .

Замечание: (Th Лапласа об определителе)

, где

– алгебраическое дополнение к минору . Дополнительный минор – определитель матрицы без элементов, входящих в минор.

Утверждение 1: |

◄По Th Лапласа:

Но |  | |►

Утверждение: (инвариантность инвариантных делителей) Пусть – две эквивалентные -матрицы, тогда = для всех соответствующих значений .

◄Легко видеть, что Утв достаточно показать для случая, когда В полученная в результате применения элементарных преобразований типа 2), т.е. -ая строка, умноженная на и добавленная к -ой строке ().

Покажем, что делит . Возможны случаи:

а)  = 

14.(2 из 2) Инвариантные делители λ-матрицы. Свойства инвариантных делителей

15. (1 из 1) Единственность канонического вида λ-матрицы

|

б) . Возможно 2 случая:

1) т.е. =

2) =+, где получен из заменой j-той строки на i-тую строку.

Например:

| Тогда |. Но матрица получена из В в результате тех же элементарных преобразований (вобратном порядке)  |  (т.к. унитарные делители инвариантны)  =.►

Теорема: (о единственности) -матрицы над полем ! – каноническая -матрица: .

◄Пусть (Diag – главная даигональ, все остальные 0, к тому же ).

Найдем инвариантный делитель

Т.о.:

…

(если с -ой строки идут одни нули)

Тогда

…

►

Следствие: Пусть - -матрицы над 

1)  

2) ; и – обратимые -матрицы. 1)3)4)

3) ; для . 

4) 2)

1)  2)  3)  4)