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}$$