Детермінант мтариці.

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

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

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

Теорема (критерій оборотності матриці). Матриця оборотна тоді і тільки тоді, коли .

Щоб визначити поняття детермінанту матриці порядку , введемо наступні поняття.

Нехай – скінченна множина з елементів.

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

Підстановку можна представити у вигляді дворядного запису: .

Очевидно, обернене перетворення має вигляд .

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

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

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

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

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

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

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

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

Означення. Цикл довжини 2 називається транспозицією.

Транспозиції не обов'язково є незалежними циклами.

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

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

В розгорнутому вигляді формула для обчислення визначника матриці має вигляд:

.

Ця формула називається формулою повного розгортання визначника.

У деяких криптографічних застосуваннях виникає задача Лагранжа, яка полягає в знаходженні всіх розв’язків рівняння при заданих , тобто в знаходженні всіх спряжених підстановок. Розв’язки рівняння можна отримати за допомогою «оператора Лагранжа» .

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

Нехай – довільний циклічний зсув вліво. Тоді можна записати ще у більшій кількості варіантів. Множину цих варіантів запису у виді позначимо через .

Оператор Лагранжа задає множину розв’язків рівняння , що будуються наступним чином:

1) виписуємо одну довільну перестановку циклів з множини , під нею почергово записуємо перестановки циклів з , але такі, щоб над відповідним циклом довжини з циклічного запису підстановки був розташований цикл з циклічного запису підстановки тієї ж довжини ;

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