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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 Цикли і транспозиції

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

Нехай і - підстановка степеня , причому,. Підстановканазивається-членним циклом, якщо вона не переміщуєелементів, а її дію на рештуелементівможна представити у вигляді циклічної діаграми переходів:. У цій діаграмі дозволяється тільки один перехід від елемента з більшим індексом, до елемента з меншим індексом, а саме:. Зазвичай діаграму записують як.

Наприклад, тричленний цикл п’ятого степеня .

Тут ,, причому,,,, а елементиінерухомі.

Циклічна діаграма переходів може бути виписана, починаючи з будь-якого свого елемента. Цикли записують у виді, аналогічному діаграміам переходів: . Нерухомим елементам співставляються так звані одиничні цикли виду. Одиничну підстановку розглядають як добуток одночленних циклів.

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

Наприклад, деяка підстановка може виглядати як. Тут кількість циклів. Як правило, одночленні цикли при такому записі ігноруються, тобто.

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

Цикловою структурою підстановки Називається запис виду, який означає, щорозкладається в добутокциклів довжини 1,циклів довжини 2, і так далі,циклів довжини.

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

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

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

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

Підстановка називається парною (непарною) якщо її декремент парний (непарний) відповідно. Знаком (характером) підстановки називається значення.

Сформулюємо тепер визначення детермінанту для довільного поля.

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