Группа подстановок

Группа подстановок

Симметрическая группа

Определение 1. Произвольное взаимно однозначное отображение множества первых $n$ натуральных чисел называется подстановкой¹⁾ $n$ -го порядка.

Замечание. Часто подстановки называют перестановками.

Обычно подстановку $\pi$ изображают следующим образом: $\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}$ , что задает образы всех элементов: $\pi(1)=i_1$ , $\pi(2)=i_2$ и так далее. Также используют запись $\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}$ .

Операция умножения на подстановках определяется как композиция отображений: $\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}\circ\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}=\begin{pmatrix}1 & 2 & \ldots & n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}$ .

Предложение 1. Множество всех подстановок порядка $n$ с операцией умножения $\circ$ образуют группу $S_n$ . Единичным элементом группы является подстановка $e=\begin{pmatrix}1 & 2 & \ldots & n\\ 1 & 2 & \ldots & n\end{pmatrix}$ , обратной подстановкой для $\pi=\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ j_1 & j_2 & \ldots & j_n\end{pmatrix}$ является $\pi^{-1}=\begin{pmatrix}j_1 & j_2 & \ldots & j_n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}$ . Порядок этой группы равен $n!$ .

Заметим, что при $n>2$ группа $S_n$ не коммутативна.

Пример 1. Группа $S_3$ состоит из шести элементов: $e=\begin{pmatrix}1 & 2 & 3\\ 1 & 2 & 3\end{pmatrix}$ , $\begin{pmatrix}1 & 2 & 3\\ 1 & 3 & 2\end{pmatrix}$ , $\begin{pmatrix}1 & 2 & 3\\ 2 & 1 & 3\end{pmatrix}$ , $\begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}$ , $\begin{pmatrix}1 & 2 & 3\\ 3 & 1 & 2\end{pmatrix}$ , $\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}$ . Эта группа не коммутативна: произведение $\begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}\circ\begin{pmatrix}1 & 2 & 3\\ 1 & 3 & 2\end{pmatrix}$ равно $\begin{pmatrix}1 & 2 & 3\\ 2 & 1 & 3\end{pmatrix}$ , что отлично от $\begin{pmatrix}1 & 2 & 3\\ 1 & 3 & 2\end{pmatrix}\circ\begin{pmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{pmatrix}=\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}$ .

Определение 2. Группа $S_n$ называется симметрической группой²⁾ порядка $n$ .

Транспозиции и циклы

Определение 3. Элемент $k\in\{1,\ldots,n\}$ подстановки $\pi$ называется действительно перемещаемым, если $k\neq\pi(k)$ .

Определение 4. Циклической подстановкой³⁾, или циклом⁴⁾ называется такая подстановка $\pi\in S_n$ , что при повторении ее достаточное число раз всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Для обозначения цикла используют запись $(i\quad\pi(i)\quad\ldots\quad\pi^{t-1}(i))$ , где $t$ — число действительно перемещаемых символов подстановки, которое называется длиной цикла⁵⁾.

Пример 2. В подстановке $\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 3 & 2 & 6 & 5 & 1 & 4 & 7 & 8\end{pmatrix}$ действительно перемещаемыми символами являются 1, 3, 4, 5, 6. Выберем любой из них, например, 3. $\pi(3)=6,\,\pi(6)=4,\,\pi(4)=5$ , $\pi(5)=1,\,\pi(1)=3$ . Поэтому цикл можно записать как $(3\quad 6\quad 4\quad 5\quad 1)$ .

Определение 5. Циклы называются независимыми⁶⁾, если они не имеют общих действительно перемещаемых символов.

Определение 6. Цикл длины 2 называется транспозицией⁷⁾.

Предложение 2. Любая подстановка $\pi\neq e$ из $S_n$ может быть разлжена в произведение попарно независимых циклов. Такое представление определено однозначно с точностью до порядка перемножения циклов.

Пример 3. $\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 2 & 4\end{pmatrix}=(1\quad 3)(2\quad 5\quad 4)$ — разложение подстановки в произведение попарно независимых циклов.

Предложение 3. Каждая подстановка может быть представлена в виде произведения транспозиций.

В отличие от представления в произведение попарно независимых циклов, представление в виде произведения транспозиций может не быть единственным.

Пример 4. Подстановка $\begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 1 & 4\end{pmatrix}$ может быть разложена в произведение транспозиций $(1\quad 3)(1\quad 2)$ или $(1\quad 3)(2\quad 4)(1\quad 2)(1\quad 4)$ .

Знакопеременная группа

Определение 7. Пусть $\pi=\tau_1\ldots\tau_k$ — разложение подстановки $\pi$ в произведение транспозиций. Тогда число $\varepsilon(\pi)=(-1)^k$ называется знаком⁸⁾(четностью) подстановки $\pi$ . Подстановка называется четной⁹⁾, если $\varepsilon(\pi)=1$ и нечетной¹⁰⁾ в противном случае.

Предложение 4. Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.

Предложение 5. Пусть $\pi$ — цикл длины $l$ . Тогда его четность равна $\varepsilon_{\pi}=(-1)^{l-1}$ .

Определение 8. Пусть $\pi=\pi_1\pi_2\ldots\pi_k$ — разложение подстановки в произведение независимых циклов длин $l_1,l_2,\ldots,l_k$ . Число $d_{\pi}=l_1+\ldots+l_k-k$ называется декрементом¹¹⁾ подстановки $\pi$ .

Предложение 6. Пусть $\pi=\pi_1\pi_2\ldots\pi_k$ — разложение подстановки в произведение независимых циклов длин $l_1,l_2,\ldots,l_k$ . Тогда четность подстановки $\pi$ вычисляется по формуле
$\varepsilon_{\pi}=(-1)^{d_{\pi}}$ .

Пример 5. Любая транспозиция — это нечетная подстановка. Подстановка из примера 4 четная.

Предложение 7. Множество всех четных подстановок образуют подгруппу $A_n$ группы $S_n$ . Порядок группы $A_n$ равен $\frac{1}{2}n!$ .

Определение 9. Группа $A_n$ всех четных подстановок называется знакопеременной группой¹²⁾ порядка $n$ .

Литература

¹⁾ permutation

²⁾ symmetric group

³⁾ cyclic permutation

⁴⁾ cycle

⁵⁾ cycle length

⁶⁾ independent

⁷⁾ transposition

⁸⁾ signature

⁹⁾ even

¹⁰⁾ odd

¹¹⁾ decrement

¹²⁾ alternating group

glossary/group/permutation.txt · Последние изменения: 05.09.2010 18:25:03 ladilova

Наверх