Теорія визначників n-го порядку.

 

Для введення поняття визначника -го порядку потрібна інформація з теорії перестановок і підстановок.

Перестановки з nсимволів.

Означення 1. Перестановкою з символів називається розташування цих символів в деякому порядку.

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

Теорема 1. З символів можна скласти перестановок.

Доведення.

Застосуємо метод математичної індукції по кількості символів n.

1. При це твердження є правильним, бо маємо дві перестановки: 1 2, 2 1.

2. Зробимо індуктивне припущення: з символів можна скласти перестановок.

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

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

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

Запишемо всі перестановки, що починаються з двійки, трійки, тощо.

Останньою буде група перестановок, що починаються з .

Таким чином всі перестановки розбиваються на k+1 клас, в кожний з яких входить k перестановок. Отже всього буде k!(k+1)=1ˑ2ˑ…ˑkˑ(k+1)=(k+1)! перестановок. З доведеного за принципом математичної індукції дане твердження є правильним при довільному натуральному .

Теорема 2. Усі перестановок з символів можна записати таким списком, в якому кожна наступна перестановка може бути отримана з попередньої шляхом однієї транспозиції.

Доведення

Застосуємо метод математичної індукції по кількості символів n.

При це очевидно: 1,2;

2,1.

Зробимо індуктивне припущення: вважатимемо правильним дане твердження при . Доведемо справедливість твердження при . Запишемо всі перестановки, що починаються з 1.

1, 2, 3,..., ,

1,...

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

На стикуванні отриманих груп перестановок першу перестановку наступної групи отримаємо з останньої за рахунок транспозиції символів, що є першими у цих групах.

Теорему доведено.

Означення 3. Два символи та складають інверсію, якщо , але в перестановці знаходиться раніше.

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

Теорема 3. Кожна транспозиція змінює парність перестановки.

Доведення.

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

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

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

Отже парність перестановки змінюється.

2. Між елементами та , над якими здійснюється транспозиція, знаходяться інші елементи:

Зробимо транспозицію поступово.

Будемо міняти місцями та сусідній справа, поки не поміняється із . Для цього буде необхідно зробити t+1 транспозицій.

Щоб поставити на місце , необхідно зробити транспозицій із сусідами зліва. Загалом буде зроблено 2t+1транспозицій, тобто в наслідок попереднього випадку парність перестановки змінюється.

Теорему доведено.

Теорема 4. При n≥2 кількість парних перестановок дорівнює кількості непарних перестановок, тобто .

Доведення. Запишемо всі перестановок так, як це пропонує теорема 2. Тоді за теоремою З у цьому списку буде чергування парних і непарних перестановок.

При n≥2 – парне число, тому список має парну кількість перестановок, половина з яких є парними, половина – непарними.

Теорему доведено.

Підстановки n-го степеня.

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

Будемо записувати підстановку у два рядки: у першому будуть вихідні елементів, а у другому – їх образи.

Наприклад:

Поставимо 2 питання:

1) Скільки форм запису однієї ї тієї підстановки.

2) Скільки різних підстановок n-го степеня можна скласти.

На обидва питання відповідь:

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

Розглянемо друге питання. Зафіксуємо елементи у першому рядку. Очевидно, що підстановки будуть різними, якщо відрізняються відповідно образи у другому рядку. Отже кількість підстановок дорівнюватиме кількості перестановок елементів другого рядка, а їх, як відомо, n!.

Означення. Підстановка називається парною, якщо парності верхньої і нижньої перестановок однакові, тобто обидві перестановки або парні або непарні.

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

Теорема. При n≥2 кількість парних підстановок дорівнює кількості непарних підстановок, тобто дорівнює .

Запишемо всі підстановки у вигляді:

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

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