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

16. (1 из 1) Подобие матриц над полем. Критерий подобия матриц над полем

17. (1 из 3) Сопровождающая матрица многочлена над полем и ее свойства

Определение: , – матрицы над полем называются подобными, если – обратимая матрица над полем (обозначается ).

Теорема: (критерий) Пусть , – матрицы над полем .

  --, Е-А, - - -матрицы над , – ед. матрица

◄без доказательства►

Следствие:  k-)=k-) , k=1,2,…

Определение: Пусть :L_pL_p – линейное преобразование, заданное с помощью матрицы А. Пусть А()={q()Р[] | q()()=0, L_p}. Множество А() называется множеством аннулирующих многочленов линейного преобразования .

q()=C_k^k+C_k-1^k-1+…+C₀E, где q()=C_k^k+C₀

В матричной форме: q(A)()=0 L_p.

Утверждение: А() – идеал кольца Р[], Р[] – кольцо главных идеалов

◄а) если f₁,f₂A(), то (f₁-f₂)A()

б) gР[] и fA()  g*fA()

Проверим: g()*f()=(g*f)() (g()=Q, f()=F)

Q*F=F*Q

(g*f)()()=(g()*f())()=(g())(f()())=g()(0)=0  g*fA()►

Сл А()=<m()>, m()Р[].

Определение: Унитарный многочлен m_(x) аннулирующий преобразование  и имеющий минимальную степень называется минимальным многочленом преобразования .

Если  задано с помощью матрицы А, то m_() или m_A() – минимальный многочлен матрицы А.

Утверждение: А – матрица над полем Р. m_A()=, где () – характеристический многочлен матрицы А размером nxn.

(()=|E-A|)

- есть n² миноров (n-1)-ого порядка.

Если в условии утверждения k(E-A)=Diag(1,…1,f,…,f_k), то m_A()=f_k.

◄()=f₁…f_k

17. (2 из 3) Сопровождающая матрица многочлена над полем и ее свойства

17. (3 из 3) Сопровождающая матрица многочлена над полем и ее свойства

=f₁…f_k ►

Определение: Матрица S(f)=- называется сопровождающей матрицей многочлена f()=ⁿ-C_n-1^n-1-…-C₀, f()P[], P-поле

Утверждение: K(E-S(f))=

◄E-S(f)=

Найдем .Заметим, что 

=1, =1,…,=1. Найдем =det(E-S(f))=

=

= =(-C_n-1)^n-1-, т.е. =f()►

18. (1 из 2) Существование и единственность представления матрицы над полем в 1-ой нормальной форме

18. (2 из 2) Существование и единственность представления матрицы над полем в 1-ой нормальной форме

Определение: -матрица над полем размером nxn; А называется матрицей в первой нормальной форме, если , где , f_iР[] (каждый предыдущий многочлен делит последующий)(размер матрицы nxn)

Теорема:  А-матрицы размером nxn над полем Р ! N₁(A) – матрица в первой нормальной форме: АN₁(A).

◄Пусть К(E-A)=Diag, где f_iP[],deg f_i1, S0, f_i|f_i+1.

Заметим, что f_t()0 (если бы f_t()=0, то характеристический многочлен был бы равен 0, а это невозможно в силу определения характерестического многочлена или |k(E-A)|=|E-A|=f₁…f_t=ⁿ+…0). Рассмотрим матрицу:

Для доказательства утверждения достаточно показать, что SA. Для этого найдем каноническую форму. Но

=

=~=K(E-S(f))=K(E-A)  AS, но S – в первой нормальной форме.

Докажем единственность: Допустим, что АS’=, S’≠S. Тогда K(E-A)=Diag(1..1,f’₁…f’_ξ)= =Diag(1…1,f₁…f_t)ξ=t и f’_i=f_iS’=S►

Алгоритм: требуется построить матрицу в первой нормальной форме, для заданной А, т.е. :

1 K(E-A)=Diag (1,…,1,f₁,…,f_t)

2) N₁(A)=

т.е нахождение 1-ой нормальной формы сводится к нахождению канонической формы.

19. (1 из 6) Существование и единственность представления матрицы над полем во 2-й нормальной форме

19. (2 из 6) Существование и единственность представления матрицы над полем во 2-й нормальной форме

Определение: Пусть –матрица размера над полем . Матрица во второй нормальной форме, если:

, где ,

- неприводимые многочлены над полем , ,.

// число блоков //

Теорема: Пусть – матрица над полем , тогда – матрица во второй нормальной форме, такая что (единственность с точностью до перестановки блоков).

◄ Пусть

, где

Пусть , - неприводимые многочлены над , где .

При этом:

(*)

Рассмотрим сопровождающие матрицы

Рассмотрим . Покажем, что . Рассмотрим матрицу





Найдем . Для этого вычислим.

19. (3 из 6) Существование и единственность представления матрицы над полем во 2-й нормальной форме

19. (4 из 6) Существование и единственность представления матрицы над полем во 2-й нормальной форме

Но

Тогда, , , т.е. . Тогда ►

ЕДИНСТВЕННОСТЬ.

◄Пусть , где k_ij удовлетворяет системе неравенств (*), p₁,…,p_s – неприводимые многочлены.

Построим матрицу N₁(N₂(A)).

ВНИМАНИЕ. В матрице ниже, мы сгруппировали сопровождающие матрицы следующим образом: взяли многочлен р₁ минимальной степени и поместили его матрицу наверх, затем взяли многочлен р₂ минимальной степени, и его матрицу поставили следующей по диагонали, и так далее до р_к минимальной степени. Затем операция повторяется с оставшимися сопровождающими матрицами (смотри пример ниже).

Рассмотрим матрицу: 

Т.к. приводимые преобразования однозначны, то и матрица N₂(A) – единственна.►

Пример:

19. (5 из 6)Существование и единственность представления матрицы над полем во 2-й нормальной форме

19. (6 из 6) Существование и единственность представления матрицы над полем во 2-й нормальной форме







Алгоритм. Построение по

Пусть А – матрица над полем размера . Надо построить .

1. Пусть все неприводимы многочлены, которые встретились в записи .

2. Выбираем все в максимальных степенях . Получим многочлен и вычеркнули из .

3. В полученной матрице выполнить действия по пункту 2); получим многочлен и т.д.

4. В результате =

Пример:



N₁(A)=S(²+1)=; N₂(A)= =N₁(A)

Пример:



N₁(A)=

20. (1 из 2) Минимальный многочлен линейного преобразования и способы его вычисления

20. (2 из 2) Минимальный многочлен линейного преобразования и способы его вычисления

Пусть - линейное преобразование линейного пространства ( - поле) и заданное с помощью матрицы .

Пусть , где или

// - преобразование -раз самого себя//

, где

- множество аннулирующих многочленов линейных преобразований (или матрицы )

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

Множество аннулирующих многочленов является идеалом кольца многочленов.

◄Надо проверить:

1) (т.у. что это подкольцо)

2) (проверка определения идеала)►

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

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

1) - унитарный

2) , т.е. - аннулирующий многочлен линейных преобразований (или матрицы )

3)

Определение: Пусть - линейное преобразование (задано с помощью матрицы ).

Тогда , где - характеристический многочлен ; - минимальный многочлен ; - матрица размера .

◄Без доказательства►

Следствие: Пусть , тогда .

21. (1 из 4) Граф линейного преобразования линейного пространства над конечным полем. Циклы и деревья.

21. (2 из 4) Граф линейного преобразования линейного пространства над конечным полем. Циклы и деревья.

Пусть - множество, , . Пара , где - называется графом, где - множество вершин, - множество ребер.

Определение: Пусть - множество, - граф, где , - множество вершин, - множество ребер (это определение учитывает петли), т.е. - множество всех двух элементов подмножеств множества (это определение не учитывает петли).

О

Пояснение:

,

// - двух элементные множества (т.е. двух различных элементов ; ; пара из одинаковых элементов сюда не входит)//

- ориентированный граф.

Определение: Пусть - линейное преобразование линейного пространства над полем .

- граф линейного преобразования , где

1)

2) ;

Замечание: В существуют петли, т.е.

Пример:

Определение: Рассмотрим последовательность элементов т.ч. :

а) если все различные и , то будем говорить, что имеет цикл длины (просто цикл)

б) если все различны и для некоторого , то имеет цикл длины и подход длины .

Определение:

а) Подграф графа называется деревом, если:

21. (3 из 4) Граф линейного преобразования линейного пространства над конечным полем. Циклы и деревья.

21.(4 из 4) Граф линейного преобразования линейного пространства над конечным полем. Циклы и деревья.

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

2. не содержит циклов; - корень дерева

б) т.ч. и , , где - корень дерева ровно за шагов в корень . Будем говорить, что элементы образуют -ый ярус дерева .

Определение: Графы и изоморфны, если - биективное отображение, т.ч.

Проверить на изоморфизм:

- в графе такого преобразования нет графы не изоморфны

Утверждение: Если , то .

◄Пусть //из подобия//

Рассмотрим т.ч. , где - обратная матрица

- ребра графа , т.е.

Проверим , т.е. , но и ►