Группа подстановок
Зачем изучать группы подстановок?
Группы подстановок (симметрические группы) являются фундаментальным объектом математики и находят применение в различных областях:
- Теория Галуа — изучение разрешимости уравнений в радикалах
- Комбинаторика — подсчёт числа перестановок и сочетаний
- Кристаллография — описание симметрии кристаллических решёток
- Квантовая механика — принцип тождественности частиц и статистика Ферми-Дирака/Бозе-Эйнштейна
- Теория кодирования — построение кодов, исправляющих ошибки
- Химия — описание симметрии молекул и молекулярных орбиталей
Определение подстановки
Определение 1. Подстановкой степени \( n \) называется биективное отображение множества \( \{1, 2, \ldots, n\} \) на себя.
Подстановку \( \sigma \) можно записать в виде:
\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & \ldots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \ldots & \sigma(n) \end{pmatrix} \]
Пример 1:
Подстановка степени 4:
\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix} \]
Здесь \( \sigma(1) = 3 \), \( \sigma(2) = 1 \), \( \sigma(3) = 4 \), \( \sigma(4) = 2 \).
1. Композиция подстановок
Композиция подстановок
Определение 2. Композицией (произведением) подстановок \( \sigma \) и \( \tau \) называется подстановка \( \sigma \circ \tau \), действующая по правилу:
\[ (\sigma \circ \tau)(i) = \sigma(\tau(i)) \quad \text{для всех } i = 1, 2, \ldots, n \]
Пример 2:
Рассмотрим подстановки:
\[ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \tau = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \]
Найдём композицию \( \sigma \circ \tau \):
\[ (\sigma \circ \tau)(1) = \sigma(\tau(1)) = \sigma(3) = 1 \\ (\sigma \circ \tau)(2) = \sigma(\tau(2)) = \sigma(1) = 2 \\ (\sigma \circ \tau)(3) = \sigma(\tau(3)) = \sigma(2) = 3 \]
Таким образом, \( \sigma \circ \tau = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = \varepsilon \) — тождественная подстановка.
Важное замечание:
Композиция подстановок некоммутативна! В общем случае \( \sigma \circ \tau \neq \tau \circ \sigma \).
2. Симметрическая группа
Симметрическая группа
Определение 3. Множество всех подстановок степени \( n \) образует симметрическую группу \( S_n \) относительно операции композиции.
Свойства симметрической группы
Теорема 1. Симметрическая группа \( S_n \) обладает следующими свойствами:
- Порядок группы \( S_n \) равен \( n! \)
- Композиция подстановок ассоциативна
- Существует тождественная подстановка \( \varepsilon \), где \( \varepsilon(i) = i \) для всех \( i \)
- Для каждой подстановки \( \sigma \) существует обратная подстановка \( \sigma^{-1} \)
Пример 3:
Для \( n = 3 \) группа \( S_3 \) содержит \( 3! = 6 \) элементов:
\[ \begin{aligned} &\varepsilon = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \quad \sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \quad \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}, \\ &\sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, \quad \sigma_4 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \sigma_5 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \end{aligned} \]
3. Чётные и нечётные подстановки
Инверсия в подстановке
Определение 4. Инверсией в подстановке \( \sigma \) называется пара \( (i, j) \) такая, что \( i < j \), но \( \sigma(i) > \sigma(j) \).
Чётность подстановки
Определение 5. Подстановка называется чётной, если она содержит чётное число инверсий, и нечётной, если она содержит нечётное число инверсий.
Знаком (чётностью) подстановки \( \sigma \) называется число:
\[ \varepsilon(\sigma) = (-1)^m \]
где \( m \) — количество инверсий в подстановке \( \sigma \).
Пример 4:
Рассмотрим подстановку \( \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \).
Найдём все инверсии:
- Пара (1,2): \( \sigma(1)=2 < \sigma(2)=3 \) — не инверсия
- Пара (1,3): \( \sigma(1)=2 > \sigma(3)=1 \) — инверсия
- Пара (2,3): \( \sigma(2)=3 > \sigma(3)=1 \) — инверсия
Всего 2 инверсии, значит подстановка чётная и \( \varepsilon(\sigma) = (-1)^2 = 1 \).
Свойства знака подстановки
Теорема 2. Для знака подстановки выполняются следующие свойства:
- \( \varepsilon(\sigma \circ \tau) = \varepsilon(\sigma) \cdot \varepsilon(\tau) \)
- \( \varepsilon(\sigma^{-1}) = \varepsilon(\sigma) \)
- Знак цикла длины \( k \) равен \( (-1)^{k-1} \)
- Знак транспозиции равен \( -1 \)
Пример 5:
Рассмотрим подстановку \( \sigma = (1\ 2\ 3) = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \).
Это цикл длины 3, поэтому его знак: \( (-1)^{3-1} = (-1)^2 = 1 \) (чётная подстановка).
Транспозиция \( (1\ 2) = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \) имеет знак \( -1 \) (нечётная подстановка).
4. Циклы и цикловая структура
Циклы
Определение 6. Циклом длины \( k \) называется подстановка \( (a_1 a_2 \ldots a_k) \), которая действует по правилу:
\[ a_1 \mapsto a_2, \quad a_2 \mapsto a_3, \quad \ldots, \quad a_{k-1} \mapsto a_k, \quad a_k \mapsto a_1 \]
а остальные элементы остаются на месте.
Теорема о разложении на циклы
Теорема 3. Любая подстановка может быть представлена в виде произведения независимых циклов. Это представление единственно с точностью до порядка циклов.
Пример 6:
Рассмотрим подстановку:
\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \]
Её цикловая структура: \( 1 \to 3 \to 1 \), \( 2 \to 5 \to 2 \), \( 4 \to 4 \).
Таким образом, \( \sigma = (1\ 3)(2\ 5)(4) = (1\ 3)(2\ 5) \).
Транспозиции
Транспозиция — это цикл длины 2. Любая подстановка может быть представлена в виде произведения транспозиций (хотя и не единственным образом).
Чётность подстановки определяется чётностью числа транспозиций в её разложении.
5. Знакопеременная группа
Знакопеременная группа
Определение 7. Знакопеременной группой \( A_n \) называется подгруппа симметрической группы \( S_n \), состоящая из всех чётных подстановок.
Свойства знакопеременной группы
Теорема 4. Знакопеременная группа \( A_n \) обладает следующими свойствами:
- Порядок группы \( A_n \) равен \( \frac{n!}{2} \)
- \( A_n \) является нормальной подгруппой в \( S_n \)
- При \( n \geq 5 \) группа \( A_n \) проста (не имеет нетривиальных нормальных подгрупп)
Пример 7:
Для \( n = 3 \) знакопеременная группа \( A_3 \) содержит \( \frac{3!}{2} = 3 \) элемента:
\[ A_3 = \left\{ \varepsilon, (1\ 2\ 3), (1\ 3\ 2) \right\} \]
Все эти подстановки чётные.
6. Классы сопряжённости в \( S_n \)
Теорема о классах сопряжённости
Теорема 5. Две подстановки \( \sigma \) и \( \tau \) в \( S_n \) сопряжены тогда и только тогда, когда они имеют одинаковую цикловую структуру.
Пример 8:
В группе \( S_4 \) подстановки \( (1\ 2)(3\ 4) \) и \( (1\ 3)(2\ 4) \) сопряжены, так как имеют одинаковую цикловую структуру (произведение двух независимых транспозиций).
Подстановка \( (1\ 2\ 3) \) не сопряжена с \( (1\ 2)(3\ 4) \), так как их цикловые структуры различны.
| Цикловой тип | Число элементов | Пример | Размер класса сопряжённости |
|---|---|---|---|
| (1,1,1,1) | 1 | \( \varepsilon \) | 1 |
| (2,1,1) | 6 | \( (1\ 2) \) | 6 |
| (2,2) | 3 | \( (1\ 2)(3\ 4) \) | 3 |
| (3,1) | 8 | \( (1\ 2\ 3) \) | 8 |
| (4) | 6 | \( (1\ 2\ 3\ 4) \) | 6 |
7. Применение групп подстановок
Теория Галуа
Группы подстановок играют ключевую роль в теории Галуа, которая связывает теорию полей с теорией групп. Группа Галуа многочлена является подгруппой симметрической группы и определяет, разрешимо ли уравнение в радикалах.
Кристаллография и теория симметрии
Группы подстановок используются для описания симметрии кристаллов и молекул. Точечные группы симметрии являются подгруппами симметрической группы.
Комбинаторика
В комбинаторике группы подстановок используются для подсчёта числа орбит при действии группы на множестве (лемма Бернсайда).
Квантовая механика
В квантовой механике принцип тождественности частиц требует, чтобы волновая функция системы identical частиц была либо симметричной (бозоны), либо антисимметричной (фермионы) относительно перестановки частиц.
Историческая справка
Изучение групп подстановок началось в XVIII-XIX веках в работах Лагранжа, Руффини, Абеля и Галуа. Эварист Галуа ввёл понятие группы подстановок и использовал его для исследования разрешимости алгебраических уравнений в радикалах.
В дальнейшем теория групп подстановок развивалась в работах Кэли, Силова, Жордана и других математиков. Кэли доказал, что любая конечная группа изоморфна некоторой группе подстановок (теорема Кэли).
В XX веке теория групп подстановок нашла applications в различных областях математики и физики, включая теорию представлений, комбинаторику и квантовую механику.