3: Симетричні групи

Нагадаємо, що якщо\(n\) є натуральним числом,\([n]=\{ 1, 2, \ldots, n \}\). Перестановка\([n]\) є один на один, на функцію від\([n]\) до\([n]\) і\(S_n\) є сукупністю всіх перестановок\([n]\). Якщо ці терміни не знайомі, було б непогано витратити деякий час, щоб вивчити Додаток B, перш ніж продовжити.

Давайте обговоримо різні способи вказати функцію від\([ n ]\) до\([ n ]\) і як визначити, коли ми маємо перестановку. Традиційно (але не обов'язково) використовувати малі грецькі літери, такі як\(\sigma\),\(\tau\),\(\alpha\)\(\beta\), і т.д., для позначення елементів\(S_n\). Бути конкретним нехай\(n = 4\). Ми можемо визначити функцію,\(\sigma:[4] \to [4]\) вказавши її значення в елементах\(1,2,3,\) і\(4\). Наприклад, скажімо:\[\sigma(1) = 2 \qquad \sigma(2) = 3 \qquad \sigma(3) = 1 \qquad \sigma(4) = 4.\nonumber \] Інший спосіб вказати\(\sigma\) - експонувати таблицю, яка дає її значення:\[\nonumber \sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 2&3&1&4 \end{array} \right ).\] Ми називаємо це два рядки або два рядки позначення. \(\sigma\)Тільки що визначена функція один до одного і onto, тобто це перестановка\([4]\).

Для іншого прикладу, нехай\[\nonumber \tau = \left ( \begin{array} {cccc} 1&2&3&4\\ 1&3&1&4 \end{array} \right ).\]\(\tau\) Функція не один до одного, так як\(1 \ne 3\) але\(\tau(1) = \tau(3)\). Цю задачу завжди можна ідентифікувати за існуванням одного і того ж елемента більше одного разу у другому рядку двох рядкових позначень. \(\tau\)також не на, оскільки елемент\(2\) не відображається у другому рядку.

\[\sigma= \left ( \begin{array} {cccc} 1&2&\cdots&n\\ \sigma(1)&\sigma(2)&\cdots&\sigma(n) \end{array} \right ).\]Дозволяти два рядкові позначення довільної функції\(\sigma: [n] \to [n]\). Потім:

1. \(\sigma\)один до одного тоді і тільки тоді, коли жоден елемент не\([n]\) з'являється більше одного разу у другому рядку.
2. \(\sigma\)знаходиться на тоді і тільки тоді, коли кожен елемент\([n]\) з'являється у другому рядку хоча б один раз.

Таким чином,\(\sigma\) є перестановкою тоді і тільки тоді, коли другий рядок є просто перестановкою або перетасуванням чисел\(1, 2, \ldots, n\).

Склад двох перестановок

Якщо\(\sigma\) і\(\tau\) є елементами\(S_n\), то\(\sigma\tau\) визначається склад функцій\(\sigma\) і\(\tau\). Тобто,\(\sigma\tau\) це функція, правило якої задається:\[\sigma\tau(x) =\sigma(\tau(x)), \quad \mbox{ for all $x \in [n]$.}\] Ми іноді викликаємо\(\sigma\tau\) просто добуток\(\sigma\) і\(\tau\). Давайте розглянемо приклад, щоб побачити, як це працює. Дозвольте\(\sigma\) і\(\tau\) визначитися наступним чином:\[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ), \quad \quad \tau = \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right )\] Звідси випливає, що\[\begin{array} {c c c c c c c} \sigma\tau(1) &=&\sigma(\tau(1))&=&\sigma(2)&=1 \\ \sigma\tau(2) &=&\sigma(\tau(2))&=&\sigma(3)&=3\\ \sigma\tau(3) &=&\sigma(\tau(3))&=&\sigma(1)&=2 \end{array}\] Таким чином, ми\[\sigma\tau = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&2 \end{array} \right )\] також можемо знайти добуток перестановок безпосередньо з двох рядкових позначень наступним чином:\[\mbox{First Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&-&- \end{array} \right )\]\[\mbox{Second Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&- \end{array} \right )\]\[\mbox{Third Step:} \quad \left ( \begin{array} {ccc} 1&2&3\\ 2&1&3 \end{array} \right ) \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right ) = \left ( \begin{array} {ccc} 1&2&3\\ 1&3&2 \end{array} \right )\]

Проблема 3.1 Обчислити такі продукти в\(S_4\):

\[(1) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\1&2&3&4 \end{array} \right )\]\[(2) \quad \left ( \begin{array} {cccc} 1&2&3&4\\1&2&3&4 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right )\]\[(3) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&3&2&1 \end{array} \right )\]\[(4) \quad \left ( \begin{array} {cccc} 1&2&3&4\\ 1&4&3&2 \end{array} \right ) \left ( \begin{array} {cccc} 1&2&3&4\\ 4&1&2&3 \end{array} \right )\]

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

Визначення 3.1:

Якщо\(\sigma:A \to B\) і\(\tau:A\to B\) є функціями то\(\sigma= \tau\) якщо і тільки якщо\[\sigma(x)=\tau(x), \quad \mbox{for all $x \in A$}.\] Зокрема, якщо\(\sigma\) і\(\tau\) знаходяться в\(S_n\) то\(\sigma=\tau\) якщо і тільки якщо\[\sigma(x)=\tau(x), \quad \mbox{for all $x \in [n]$}.\]

ідентичність\(S_n\)

Ідентичність\(S_n\) - це так звана функція ідентичності,\[\iota:[n] \to [n].\] яка визначається правилом:\[\iota(x) = x, \quad \mbox{ for all $x \in [n]$.}\] У двох рядках позначення\(\iota\)\(\iota\) описується\[\iota = \left ( \begin{array} {cccc} 1&2&\cdots&n\\ 1&2&\cdots&n \end{array} \right )\] Функція чітко один-на-один і на і \(\iota\)задовольняє\[\iota \sigma= \sigma\quad \mbox{and } \quad \sigma\iota = \sigma, \qquad \mbox{ for all $\sigma\in S_n$}.\] Так ідентичність\(S_n\) стосовно двійкової операції композиції.

Обернене елемента\(\sigma \in S_n\):

Якщо\(\sigma\in S_n\), то за визначенням\(\sigma:[n] \to [n]\) один до одного і на. Звідси правило\[\sigma^{-1}(y) = x \quad \mbox{ if and only if } \quad \sigma(x) = y\] визначає функцію\(\sigma^{-1}: [n] \to [n]\). \(\sigma^{-1}\)Функція також один-на-один і на (перевірте це!) і задовольняє\[\sigma\sigma^{-1}= \iota \qquad \mbox{ and } \qquad \sigma^{-1}\sigma= \iota,\] так це зворотне\(\sigma\) в груповому сенсі також.

З точки зору двох рядків опису перестановки, якщо\[\sigma= \left ( \begin{array} {ccc} \cdots&x&\cdots\\ \cdots&y&\cdots \end{array} \right)\] тоді\[\sigma^{-1} = \left ( \begin{array} {ccc} \cdots&y&\cdots\\ \cdots&x&\cdots \end{array} \right)\]

Обернену перестановку в двох рядкових позначеннях можна отримати шляхом зміни двох рядків, а потім переупорядкування стовпців так, щоб числа у верхньому рядку були в числовому порядку. Ось приклад:\[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 2&3&1 \end{array} \right )\] Зміна двох рядків, які ми маємо: Зміна\[\left ( \begin{array} {ccc} 2&3&1 \\ 1&2&3 \end{array} \right ).\] порядку стовпців, які ми отримуємо\[\sigma^{-1} = \left ( \begin{array} {ccc} 1&2&3 \\ 3&1&2 \end{array} \right ).\]

Задача 3.2 Знайти обернення кожної з наступних перестановок у двох рядкових позначеннях. Перевірте в кожному випадку, що\(\sigma\sigma^{-1} = \iota\) і\(\sigma^{-1}\sigma= \iota\).

\({\displaystyle \sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 2&3&1&4 \end{array} \right )}\)

\({\displaystyle \sigma= \left ( \begin{array} {ccccc} 1&2&3&4&5\\ 2&3&4&5&1 \end{array} \right )}\)

Теорема\(\PageIndex{1}\)

Для будь-яких трьох функцій у\[\alpha:A \to B, \quad \beta: B \to C, \quad \gamma: C \to D\] нас є\[(\gamma \beta)\alpha = \gamma(\beta \alpha).\]

Доказ нехай\(x \in A\). Потім\[(\gamma \beta)\alpha(x)=\gamma \beta(\alpha(x)) = \gamma(\beta(\alpha(x))).\] і З цього\[\gamma (\beta\alpha)(x)=\gamma ( \beta \alpha(x) ) = \gamma(\beta(\alpha(x))).\] випливає, що\[(\gamma \beta) \alpha(x) = \gamma (\beta \alpha)(x) \quad \mbox{ for all $x \in A$}.\] Звідси\((\gamma \beta)\alpha = \gamma(\beta \alpha)\).

Наслідок 3.2 Бінарна операція композиції на\(S_n\) асоціативна.

Цим слідством ми завершуємо доказ того, що\(S_n\) під двійковою операцією композиції знаходиться група.

Циклічна діаграма перестановки

Важливий спосіб візуалізації\(\sigma\) елемента\(S_n\) полягає в наступному. \(n\)Розставте точки в площині. Пронумеруйте точки 1 через\(n\). Для всіх\(i \in [n]\), якщо\(\sigma(i) = j\) намалювати стрілку від числа точки\(i\) до номера точки\(j\). Ми називаємо цю картину циклічною діаграмою\(\sigma\). Щоб вийшла симпатична картинка, найкраще використовувати наступну техніку для нанесення схеми.

1. Намалюйте точку і пронумеруйте її 1. Нехай\(i_1 = \sigma(1)\). Якщо\(i_1 \ne 1\) намалюйте іншу крапку і позначте її\(i_1\).
2. Намалюйте стрілку від точки 1 до точки\(i_1\). (Зверніть увагу, що\(i_1=1\) це можливо.)
3. Припустимо, що пронумеровані точки\(1, i_1, i_2, \ldots, i_k\) були намальовані. Розглянемо два випадки:

   (i)

   Існує стрілка, яка залишає кожну крапку, намальовану досі. У цьому випадку нехай\(i_{k+1}\) буде найменшим числом в ще\([n]\) не маркування крапки. Якщо таких немає, то зупиніться, ви завершили схему, інакше намалюйте нову крапку і позначте її\(i_{k+1}\)

   (ii)

   Існує точка,\(j\) пронумерована без стрілки, що залишає її. У цьому випадку нехай\(i_{k+1} = \sigma(j)\). Якщо немає точки з позначкою,\(i_{k+1}\) намалюйте нову точку та позначте її\(i_{k+1}\). Намалюйте стрілку від точки\(j\) до точки\(i_{k+1}\).

4. Тепер повторіть крок 3 із\(k+1\) заміною\(k\).

Приклад 3.1: Циклічна діаграма наступної перестановки наведена на малюнку 3.1. \[\alpha = \left ( \begin{array} {ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\ 13&11&7&6&5&4&3&10&2&12&14&1&15&9&8 \end{array} \right ).\]

Зверніть увагу, що схема складається з п'яти «циклів»: один «6-цикл», один «4-цикл», два «2-цикли» і один «1-цикл». Кожна діаграма циклу буде виглядати приблизно так. Ось чому ми називаємо це діаграмою циклу.

[діаграма йде тут]

Циклічна діаграма\(\alpha\) з вправи 3.1

Завдання 3.3 Намалюйте циклічні діаграми для всіх 24 елементів\(S_4\). Вам знадобиться систематичний спосіб перерахувати елементи,\(S_4\) щоб переконатися, що ви не пропустили жодного.

Ми зараз дамо більш точне визначення «циклу».

Визначення 3.2:

\(i_1, i_2, \ldots, i_k\)Дозволяти список\(k\) різних елементів з\([n]\). Визначте перестановку\(S_n\) наступним\(\sigma\) чином:\[\begin{array} {rcl} \sigma(i_1) &=& i_2 \\ \sigma(i_2) &=& i_3 \\ \sigma(i_3) &=& i_4 \\ \vdots & \vdots & \vdots \\ \sigma(i_{k-1}) & =& i_k \\ \sigma(i_k)& =& i_1 \end{array}\] а якщо\(x \notin \{ i_1, i_2, \ldots, i_k \}\) тоді\[\sigma(x) \ = \ x\] Така перестановка називається циклом або \(k\)циклом і позначається\[(i_1 \ i_2 \ \cdots \ i_k).\] Якщо\(k=1\) тоді цикл\(\sigma=(i_1)\) - це лише функція ідентичності, тобто\(\sigma= \iota\).

Наприклад, нехай\(\sigma\) буде 3-цикл, визначений\(\sigma= ( 3 \ 2 \ 1)\). \(\sigma\)може розглядатися як елемент цього випадку\(S_3\) в двох рядках позначення ми маємо\[\sigma= \left ( \begin{array} {ccc} 1&2&3\\ 3&1&2 \end{array} \right ).\] Примітка, що згідно з визначенням if\(x \notin \{ 3, 2, 1\}\) then\(\sigma(x) = x\). Таким чином, ми могли б\((3 \ 2 \ 1)\) також розглядати як елемент\(S_4\). У цьому випадку ми мали б:\[\sigma= \left ( \begin{array} {cccc} 1&2&3&4\\ 3&1&2&4 \end{array} \right ).\] Або ми могли б розглядати\((3 \ 2 \ 1)\) як елемент\(S_5\). У цьому випадку ми мали б:\[\sigma= \left ( \begin{array} {ccccc} 1&2&3&4&5\\ 3&1&2&4&5 \end{array} \right ).\] Аналогічно,\((3 \ 2 \ 1)\) може бути елементом\(S_n\) для будь-якого\(n \ge 3\). Зверніть увагу також, що ми могли б вказати ту ж перестановку будь-яким з наступних\[\sigma= ( 3 \ 2 \ 1), \quad \sigma= ( 2 \ 1 \ 3), \quad \sigma= ( 1 \ 3 \ 2).\] У цьому випадку є три числа 1, 2, 3 в циклі, і ми можемо почати цикл з будь-якого з них. Взагалі, існують\(k\) різні способи написання\(k\) -циклу. Починати можна з будь-якого числа в циклі.

Проблема 3.4 Нижче перераховані 5 різних циклів в\(S_5\).
(a) Опишіть кожен із заданих циклів у двох рядкових позначеннях.
(b) Намалюйте діаграму циклу кожного циклу.

1. (4)
2. (3 4)
3. (4 1 5)
4. (1 3 5 4)
5. (1 3 5 4 2)

Визначення 3.3:

Два цикли\((i_1 \ i_2 \ \cdots \ i_k)\) і\((j_1 \ j_2 \ \cdots \ j_{\ell})\), як кажуть, нез'єднані, якщо\(\{i_1, i_2, \ldots, i_k\}\) набори і\(\{j_1, j_2, \ldots, j_{\ell}\}\) нез'єднані.

Так, наприклад, цикли\((1 \ 2 \ 3)\) і\((4 \ 5 \ 8)\) розмежовуються, а ось цикли\(( 1 \ 2 \ 3)\) і\((4 \ 2 \ 8)\) не розмежовуються.

Теорема\(\PageIndex{3}\)

Якщо\(\sigma\) і\(\tau\) є нероз'єднаними циклами, то\(\sigma\tau = \tau\sigma\).

Доказ Нехай\(\sigma= (a_1 \cdots a_k)\) і\(\tau = (b_1 \cdots b_{\ell})\). Дозвольте\(\{c_1, \cdots, c_m \}\) бути елементи\([n]\), які є ні в ні в\(\{a_1, \dots, a_k \}\) ні\(\{ b_1, \cdots, b_{\ell} \}\). Таким чином\[[n] = \{a_1, \dots, a_k \} \cup \{ b_1, \cdots, b_{\ell} \} \cup \{c_1, \cdots, c_m \}.\] Ми хочемо показати\(\sigma\tau(x) = \tau \sigma(x)\) для всіх\(x \in [n]\). Для цього ми розглянемо спочатку випадок\(x=a_i\) для деяких\(i\). Тоді\(a_i \notin \{ b_1, \cdots , b_{\ell} \}\) так\(\tau(a_i) = a_i\). Крім того\(\sigma(a_i) = a_j\), де\(j=i+1\) або\(j=1\) якщо\(i=k\). Так і\(\tau(a_j) =a_j\). Таким\[\sigma\tau(a_i) = \sigma(a_i) = a_j = \tau(a_j) = \tau(\sigma(a_i) = \tau\sigma(a_i).\] чином,\(\sigma\tau(a_i) = \tau\sigma(a_i)\). Залишено читачеві показати, що\(\sigma\tau(x) = \tau\sigma(x)\) якщо\(x=b_i\) або\(x=c_i\), який завершить доказ.

Проблема 3.5 Покажіть на прикладі, що якщо два цикли не роз'єднані, вони не повинні їздити на роботу.

Теорема\(\PageIndex{4}\)

Кожен елемент\(\sigma\in S_n\)\(n \ge 2\), може бути записаний як продукт, \[\label{eq3.1} \sigma= \sigma_1 \sigma_2 \cdots \sigma_m\]де\(\sigma_1, \sigma_2, \ldots ,\sigma_m\) є попарно нероз'єднані цикли, тобто для\(i \ne j\),\(\sigma_i\) і\(\sigma_j\) є нез'єднаними. Якщо всі 1-цикли\(\sigma\) включені, фактори є унікальними, крім замовлення. \(\blacksquare\)

Факторизація (3.41) називається розрізненим циклом розкладання\(\sigma\).

Для економії часу опускаємо формальне доказ цієї теореми. Процес знаходження нероз'єднаного циклу розкладання перестановки досить схожий на знаходження циклової діаграми перестановки. Розглянемо, наприклад, перестановку\(\alpha \in S_{15}\)\[\alpha = \left ( \begin{array} {ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15 \\ 13&11&7&6&5&4&3&10&2&12&14&1&15&9&8 \end{array} \right ).\] Роз'єднаний цикл розкладання\(\alpha\) є\[\alpha = (1 \ 13 \ 15 \ 8 \ 10 \ 12)(2 \ 11 \ 14 \ 9)(3 \ 7)(4 \ 6) ( 5).\] Порівняйте це з діаграмою циклу, наданою для цієї ж перестановки на сторінці. Щоб отримати це, починається цикл з 1, оскільки у\(\alpha(1) = 13\) нас є частковий цикл\((1 \ 13\). Далі ми це спостерігаємо\(\alpha(13) = 15\). Це дає частковий цикл\(( 1 \ 13 \ 15\). Ми продовжуємо таким чином, поки не отримаємо цикл\((1 \ 13 \ 15 \ 8 \ 10 \ 12)\). Потім ми вибираємо найменше число в\([15]\) не використовуваних досі, а саме, 2. Ми починаємо новий цикл з 2: Відзначаючи, що у\(\alpha(2) = 11\) нас є частковий цикл\((2 \ 11\). Продовжуючи отримуємо цикл\((2 \ 11 \ 14 \ 9)\). І ми продовжуємо таким чином, поки всі елементи\([15]\) знаходяться в якомусь циклі.

Задача 3.6 Знайти розбійний цикл розкладання наступних перестановок в\(S_{6}\):

\( \sigma= \left ( \begin{array} {cccccc} 1&2&3&4&5&6\\ 2&3&4&1&6&5 \end{array} \right) \)

\( \sigma= \left ( \begin{array} {ccccccc} 1&2&3&4&5&6\\ 3&2&4&6&5&1 \end{array} \right )\)

\( \sigma= \left( \begin{array} {ccccccc} 1&2&3&4&5&6\\ 1&2&5&4&3&6 \end{array} \right ) \)

Задача 3.7 Знайти розбійний цикл розкладання наступних перестановок в\(S_{6}\): [Кожна перестановка задається як добуток циклів. Спробуйте зробити це, не перетворюючи позначення циклу в два рядкові позначення.]

(1)\((1 \ 2 \ 3)(2 \ 4 \ 5)\)
(2)\((3 \ 4 \ 5 \ 1 \ 2)( 4 \ 5 \ 6) (1 \ 2 \ 3)\)
(3)\((1 \ 3)( 1 \ 2)\)
(4)\((1 \ 4)(1 \ 3)( 1 \ 2)\)

Проблема 3.8 (a) Переконайтеся, що якщо\(a,b,c,d,e\) є різними елементами,\([n]\) то кожен з наступних циклів може бути записаний як добуток 2-циклів: [Підказка: подивіться на (3) і (4) у задачі 3.7.] (b) Переконайтеся, що обернене кожного з цих циклів є циклом однакового розміру.

(1) (а б в).
(2) (а б с г)
(3) (а б с д е).

Визначення 3.4:

Елемент\(S_n\) називається транспозицією тоді і тільки тоді, коли це 2-цикл.

Зверніть увагу, що транспозиція\((i \ j)\)\(i\)\(j\) розв'язок і залишає інші елементи\([n]\) нерухомими. Він транспонує\(i\) і\(j\).

Визначення 3.5

Ціле число\(n\) є парним, якщо\(n=2k\) для деякого цілого числа\(k\). Це непарно, якщо\(n=2k+1\) для деякого цілого числа\(k\). Парність цілого числа - це властивість бути парним або непарним. Два цілих числа мають однакову парність, якщо вони обидва парні або якщо вони обидва непарні. Вони мають різний паритет, якщо один парний, а інший непарний.

Теорема\(\PageIndex{4}\)

Кожен елемент\(S_n\) може бути записаний як добуток транспозицій. Фактори такого твору не є унікальними, однак, якщо\(\sigma\in S_n\) можна записати як твір\(k\) транспозицій і якщо те ж саме\(\sigma\) можна записати як добуток\(\ell\) транспозицій, то\(k\) і \(\ell\)мають однаковий паритет. \(\blacksquare\)

Перша частина цієї теореми проста. Узагальнюючи задачу 3.7, ми бачимо, що кожен цикл може бути записаний як добуток транспозицій наступним чином:\[(i_1 \ i_2 \ i_3 \ \cdots i_k) = (i_1 \ i_k) \cdots (i_1 \ i_3) (i_1 \ i_2).\] Тоді, оскільки кожна перестановка є добутком циклів, ми можемо отримати кожну перестановку як добуток транспозицій. Другу частину складніше довести і, в інтересах часу, ми опускаємо докази. Гарний доказ можна знайти в Fraleigh (, стор. 108.)

Задача 3.9 Запишіть перестановку\(\alpha\) на сторінці як добуток транспозицій. Робіть це не одним способом. Скільки транспозицій є в кожному з ваших продуктів?

Задача 3.10 Дайте нероз'єднаний цикл розкладання кожного з 6 елементів\(S_3\). Також запишіть кожен елемент\(S_3\) як добуток транспозицій.

Визначення 3.6:

Перестановка є парною, якщо вона є добутком парного числа транспозицій і непарна, якщо вона є добутком непарної кількості транспозицій. Визначаємо функцію\(\mathrm{sign}: S_n \to \{ 1,-1 \}\) за допомогою\[\mathrm{sign}(\sigma) = \left \{ \begin{array}{r l} 1 & \mbox{if $\sigma$ is even} \\ -1 & \mbox{if $\sigma$ is odd} \end{array} \right.\] If,\(n=1\) то транспозицій немає. У цьому випадку, щоб бути повним, ми визначаємо\(\iota\) перестановку ідентичності рівною.

Задача 3.11 Показати, що функція\(\mathrm{sign}\) задовольняє\[\mathrm{sign}(\sigma\tau) = \mathrm{sign}(\sigma)\mathrm{sign}(\tau)\] для всіх\(\sigma\) і\(\tau\) в\(S_n\).

Зауваження

\(A=[a_{i j}]\)Дозволяти бути\(n \times n\) матрицею. Визначник\(A\) може бути визначена сумою\[\det (A) = \sum_{\sigma \in S_n} \mathrm{sign}(\sigma) a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}.\] Наприклад, якщо у\(n=2\) нас є тільки дві перестановки\(\iota\) і\((1 \ 2)\). Так як\(\mathrm{sign}(\iota) = 1\) і\(\mathrm{sign}((1 \ 2)) = -1\) отримуємо\[\det(A) = a_{1 1}a_{2 2} - a_{ 1 2}a_{2 1}.\]

Задача 3.12 Знайдіть знак кожного елемента\(S_3\) і використовуйте цю інформацію, щоб виписати формулу\(\det (A)\) коли\(n = 3\). (Зверніть увагу, що в даному випадку детермінантом є сума 6 термінів.)

Задача 3.13 Якщо\(n=10\) скільки членів у наведеній вище формулі для детермінанта?

Визначення 3.7

Якщо\((G,*)\) це група, то кількість елементів в\(G\) називається порядком\(G\). Використовуємо\(\vert G\vert\) для позначення порядку\(G\).

Зверніть увагу, що\(\vert G\vert\) може бути скінченним або нескінченним. Якщо він скінченний\(\vert G\vert=n\) для деякого натурального цілого числа\(n\). Цікавою, але складною проблемою є визначення всіх груп фіксованого порядку\(n\). За малим\(n\) це можна зробити, як ми побачимо, але надії відповісти на питання за всіма значеннями, незважаючи на зусилля багатьох математиків, які спеціалізуються на вивченні скінченних груп, немає надії.\(n\)

Завдання 3.14 Знайти\(\vert GL(2,\mathbb{Z}_2) \vert\) і\(\vert M_2(\mathbb{Z}_2) \vert\).

Теорема\(\PageIndex{6}\)

\(\vert S_n \vert = n!\)для всіх\(n \ge 1\).

Доказ\(n\) Дозволяти будь-яке додатне ціле число. Елементи\(S_n\) мають вигляд

\[\left ( \begin{array} {ccccc} 1&2&3&\dots&n \\ a_1&a_2&a_3&\dots &a_n \end{array} \right)\]де\(a_1, a_2, \dots , a_n\) будь-яка перестановка чисел\(1,2, \dots, n\). Отже, проблема полягає в тому, скільки способів ми можемо вибрати\(a_1, a_2, \dots , a_n\)? Зверніть увагу, що існують\(n\) способи вибору\(a_1\). Після того, як вибір зроблений для\(a_1\),\(n-1\) залишаються можливості для\(a_2\). Таким чином, існують і зовсім\(n(n-1)\) способи вибору\(a_1a_2\). Тоді, для кожного вибору\(a_1a_2\),\(n-2\) залишаються можливості для\(a_3\). Таким чином, існують\(n(n-1)(n-2)\) способи вибору\(a_1a_2a_3\). Продовжуючи таким чином, ми бачимо, що є\[n(n-1)(n-2)\cdots2\cdot 1 = n!\] способи вибору\(a_1, a_2, \dots , a_n\). \(\blacksquare\)

Задача 3.15 Показати, що зворотний\(k\) цикл - це також\(k\) -цикл. Підказка: Показати, що якщо\(a_1,a_2, \dots, a_k\) є окремими елементами\([n]\) then\[(a_1 \ a_2)^{-1} = (a_2 \ a_1)\]\[(a_1 \ a_2 \ a_3)^{-1} = (a_3 \ a_2\ a_1)\]\[(a_1 \ a_2 \ a_3 \ a_4)^{-1} =(a_4 \ a_3 \ a_2 \ a_1)\] і більш загалом\[(a_1 \ a_2 \ \cdots \ a_k)^{-1} =(a_k \ \cdots \ a_2 \ a_1)\] Підказка: Нехай\(\sigma = (a_1 \ a_2 \ \cdots \ a_k)\) і\(\tau = (a_k \ \cdots \ a_2 \ a_1)\). Покажіть, що\(\tau (\sigma(a_i)) = a_i\) для всіх,\(i\) розглянувши три випадки:\(i \notin \{1,2,\dots, k\}\),\(i \in \{1,2,\dots, k-1\}\) і\(i=k\).

Проблема 3.16 Показати,\(\sigma\) що якщо\(k\) - цикл, то\(\mathrm{sign}(\sigma) =1\) якщо\(k\) непарний, а\(\mathrm{sign}(\sigma) = -1\) якщо\(k\) парний.

Проблема 3.17 [Проблема виклику] Для\(\sigma \in S_n\) довести, що\[\begin{aligned} \sigma \mbox{ is even } &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = 1 \\ \qquad \sigma \mbox{ is odd } \; \; &\Longleftrightarrow& \prod_{i<k} \frac {\sigma(k) -\sigma (i)}{k-i} = - 1\end{aligned}\]