Мінімальні та анулюючі многочлени для матриці

Date: 2015-10-07; view: 1237.

Многочленом від квадратної матриці над полем називається результат послідовності операцій, що записана у формі многочлена з коефіцієнтами з поля при . Нормованим, або унітарним многочленом називається многочлен зі старшим коефіцієнтом, що дорівнює одиниці.

Визначення. Анулюючим многочленом матриці називається многочлен , такий, що .

Визначення. Мінімальним многочленом матриці над полем називається нормований многочлен найменшого степеня, для якого .

Теорема 2.1. Степінь мінімального многочлена матриці не перевершує її порядку.

Теорема 2.2. Мінімальний многочлен матриці ділить будь-який анулю-ючий многочлен тієї ж матриці.

Нехай - квадратна матриця над скінченним полем і , .

Розглянемо послідовність -мірних векторів , , .

На кожнім кроці будемо перевіряти, чи є система отриманих векторів лінійно незалежною. Очевидно, що система векторів буде лінійно незалежною, якщо її ранг дорівнює кількість векторів в системі. Для обчислення рангу системи можна використовувати алгоритм зведення до трапецеїдального виду прямокутної матриці (див. далі).

На деякому кроці , , вектори уперше виявляться лінійно залежними, тобто ранг системи буде . Інакше кажучи, знайдуться коефіцієнти, не всі рівні нулю. що виконається співвідношення . Цьому співвідношенню відповідає многочлен , який залежить від матриці та вектора .

Визначення. Нормований многочлен мінімального степеня для якого називається мінімальним многочленом вектора відносно матриці .

Коли матриця є відомою з контексту, цей многочлен часто називають мінімальним многочленом вектора , або просто відносним мінімальним многочленом.

Мінімальний многочлен матриці іноді називають мінімальним многочленом всього простору відносно матриці , оскільки для довільного вектора .

Відносний мінімальний многочлен (як і мінімальний многочлен всього простору) визначається однозначно. Якщо довільний анулюючий многочлен відносно вектора , тобто, , то ділиться на .

Доведення просте. Якщо , - різні мінімальні поліноми, то поліном є анулюючим для вектора , але має степінь нижчу, ніж степінь кожного з двох мінімальних поліномів, тобто поліноми , не є мінімальними.

Теорема 2.3. Мінімальний многочлен суми векторів є найменшим спільним кратним мінімальних многочленів векторів - доданків.

Теорема 2.4.Мінімальний многочлен суми лінійно незалежних векторів є добутком їхніх мінімальних многочленів

Теорема 2.5. Мінімальний многочлен матриці ділиться на мінімальний многочлен довільного вектора .

Очевидно, найменше спільне кратне мінімальних многочленів базисних векторів відносно матриці є мінімальним многочленом цієї матриці.

Можна розглядати матриці, елементами яких є функції, скажемо, від змінної . У цьому випадку визначник матриці також є функцією від .

Многочлен називається характеристичним многочленом матриці .

Теорема 2.6 (Гамільтона-Келі). Кожна матриця є коренем свого характеристичного многочлена.

Таким чином, - анулюючий многочлен для , тому (кожний попередній многочлен діліть наступний).

Якщо незвідний, то відносні мінімальні многочлени співпадають з , оскільки повинни його ділити.

Послідовність , , є періодичною. Довжина періоду залежить від властивостей мінімального многочлена вектора .

Дійсно, з випливає , що дає . Але , тому кількість многочленів обмежена і у послідовності , , повинно з'явитися повторення.

1.4 Підстановочні матриці, визначник матриці над GF(2^t)

Підстановкою степеня на множині з элементів називається взаємно однозначне відображення множини на себе.

Нехай множина впорядкована, тоді їй відповідає послідовність номерів . Будемо вважати, що Після застосування підстановки послідовність номерів зміниться і матиме вигляд .

Підстановку записують у виді двох рядків (каноничному виді): .

Будемо трактувати цей запис як « елемент з номером переміщується на місце з номером ».

У множині підстановок можна ввести множення, що перетворює її у групу яка містить ! елементів і позначається через .

Добутком підстановок і називається результат їхньої послідовної дії: . Таким чином, якщо, , , то . Очевидно, існує , а також, одинична підстановка , для якої і дійсно є групою. Приклад: при і , , а .

Підстановку можна задати (представити) як матрицю.

Розглянемо квадратну матрицю порядка , у якої елементи з індексами дорівнюють одиницям, а решта елементів – нулі.

Наприклад, для , отримаємо .

Оскільки , то матриця реалізує підстановку .

Підстановочні матриці є оборотними. Якщо матриця підстановочна, то , тому, що .

Загальний критерій оборотності матриці формулюється за допомогою поняття визначника (детермінанта). Детермінант матриці над полем є елементом поля . Він є функцією всіх елементів матриці і позначається через . Детермінант записується також у виді .

Матриця оборотна тоді і тільки тоді, коли .

Спочатку розглянемо випадок, коли матриця порядку визначена над полем . У цьому полі операції додавання та віднімання співпадають.

Розглянемо всі ! підстановочних матриць порядку . Уявимо собі, що кожна з них записана у виді таблиці на окремому аркуші паперу у клітинку.

Проріжемо у кожній таблиці віконця в тих клітинках, де елементи відповідної матриці дорівнюють одиниці. Одержимо, таким чином, сукупність підстановок у виді трафаретів.

Накладемо трафарет для підстановки на матрицю і перемножимо всі елементи матриці, що з'явилися у віконцях. Результат назвемо членом визначника матриці, що відповідає підстановці .

Знайдемо суму над полем усіх ! членів визначника. Результат назвемо детермінантом (визначником) матриці над полем . У загальному випадку поля член визначника матриці, що відповідає підстановці , має вигляд . Загальне визначення розглянемо нижче.