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

22. (1 из 3) Свойства графа линейного преобразования, заданного с помощью нильпотентной матрицы

22. (2 из 3) Свойства графа линейного преобразования, заданного с помощью нильпотентной матрицы

Утверждение: Пусть A:L_pL_p , тогда  М – матрица линейного оператора: М=, где А₀ – нильпотентная матрица (т.е.  rN: ); A₁ – обратимая матрица (т.е. |A₁|0); такая что МА и G(M)G(A)

◄ Рассмотрим N₂(A)=, p_i – неприводимые многочлены из P[x].

Преобразуем N₂(A): p₁=…=p_s=x; p_s+1,…,p_k – отличны от x. Получим: N₂(A)=, где А₀= и А₁=.

Рассмотрим |А₁|=;

Заметим, что |S(p^)|0, где р(х)х.

Действительно: (S(p^))=|Е-S(p^)|=p^, но |S(p^)|=p^(0) (p^(0) – является условной записью свободного коэффициента многочлена p^), но так как р(х)х, то р(0)0  |A₁|0.

Рассмотрим А₀=, но S(x^k)=

S(x^k)^k=0 

 A₀ – нильпотентна.►

Утверждение: (свойство) Пусть А₀ L_pL_p, |Р|<∞,А₀ – нильпотентная. Тогда G(A₀) – дерево.

◄Т.к. А₀=, то Утв достаточно доказать для случая А₀=S(^).

Пусть  uциклу графа G(A₀), причем длина которого k>1, т.е. для некоторого kN выполняется u=u или (-Е)u=0 (где -Е – нильпотентная-единичная = обратимая) u=0  нет циклов  G(A) – дерево, где u=0 – корень дерева.►

Утверждение: Пусть А=, А₀ – нильпотентная матрица, А₁ – обратимая матрица. Пусть С(А) – подграф графа G(A), состоящий из всех вершин графа G(A), принадлежащих какому либо циклу. еV_C(A) рассмотрим подграф графа G(A) – D_e(A) вида:

а) = {e}{vV_G(A)|vV_C(A) и  путь (e,v) в графе G(A)}

б) rrE_G(A)

22. (3 из 3) Свойства графа линейного преобразования, заданного с помощью нильпотентной матрицы

23. (1 из 2)Построение графа линейного преобразования, заданного с помощью нильпотентной матрицы

Рассмотрим граф , полученный из D_e(A) добавлением ребра (е,е). Тогда:

1) С(А)  G(A₁)

2) eC(A),  G(A₀)

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

Утверждение: Пусть А₀:L_pL_p и  rN т.ч. =0, |P|=q₀, т.е. поле конечно. Для того, чтобы построить G(A₀) надо найти значение следующих параметров:

1) L – число слоев (уровней) дерева G(A₀)

2) N_i – число вершин слоя i, i=1…L

3) K_i – число концевых вершин слоя i, i=1…L (концевые – в них не входят ребра, но из них могут выходить )

4) R(v) – число ребер, входящих в вершину v.

Утверждение: Пусть A₀=S(^k), тогда:

1) L=k

2) N₀=1; N₀+…+N_i=qⁱ, i=1…L

3) k_i=0, ik

4) R(v)={0,q}

◄

=, т.е. L=k (здесь - вектор (вершины)).

23. (1 из 2)Построение графа линейного преобразования, заданного с помощью нильпотентной матрицы

24. (1 из 1)Свойства графа линейного преобразования, заданного с помощью обратимой матрицы

Найдем число вершин графа G(A₀), из которых корень дерева достижим за не более чем I шагов. Легко видеть, что эти вершины имеют вид . Таких векторов qⁱ.

Покажем, что R(v){0,v}. Рассмотрим вершину =v. Легко видеть, что:

1) если S₁0, то R(v)=0

2) если S₁=0, то переходит в , где bP, т.е. R(v)=q►

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

◄Пусть . Рассмотрим последовательность , где ;

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

25. (1 из 2) Цикловые термы. Сведение задачи построения графа линейного преобразования, заданного со помощью обратимой матрицы, к задаче построения линейного преобразования, заданного с помощью сопровождающей матрицы степени неприводимого многочлена.

25. (2 из 2) Цикловые термы. Сведение задачи построения графа линейного преобразования, заданного со помощью обратимой матрицы, к задаче построения линейного преобразования, заданного с помощью сопровождающей матрицы степени неприводимого многочлена.

Теорема: Пусть А₀:L_pL_p, |P|=q, A₀, 1₁…_kL

Положим m₁ – число элементов последовательности ₁…_k, равных 1, m₂ – равных 2 и т.д. до m_k – число элементов данной последовательности, равных L (например последовательность 2,3,3,5, тогда m₁=0,m₂=1, m₃=2, m₄=0, m₅=1). Тогда G(A₀) определяется следующими параметрами:

1) L=max(₁…_k)

2) R(v){0,}

3) N₀=1, N₀+…+N_L=

4) K_i=N_i-

◄Доказать самим►

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

Цикловой структурой преобразований - называется формальная сумма:

, где - число всех циклов графа длины

- все возможные длины циклов графа .

- называется цикловым термом.

Определение: Пусть - цикловые структуры; , - цикловые термы

Определим произведение

а) Сумма цикловых термов.

б) Произведение цикловых термов

в) , где - результат применения операции а) к .

Утверждение: Пусть матрица ; - обратимы .

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

//Для матрицы вида чтобы построить соответствующий граф есть соответствующее утверждение.//

26. Построение графа линейного преобразования, заданного с помощью сопровождающей матрицы степени неприводимого многочлена (без доказательства)

26. Построение графа линейного преобразования, заданного с помощью сопровождающей матрицы степени неприводимого многочлена (без доказательства)

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

Тогда , где - минимальное натуральное число такое, что , а определяется из неравенств .

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

Алгоритм построения графа линейного преобразования

1) - строим вторую нормальную форму матрицы

- неприводимые и

2) Для построим - дерево

3) Для пользуясь теоремой строим (цикловая структура)

4)Пусть =>

5) К каждой вершине добавляем .