7.6. Симметрическая группа подстановок
Пусть
конечное множество из
элементов. Множество всех взаимно однозначных отображений множества
на себя называется симметрической группой
степени
Без ограничения общности можно считать, что множество
состоит из элементов
Каждое такое отображение
называется подстановкой или перестановкой и записывается
где
образ элемента
Произведением подстановок является композиция отображений (операция группы)
Например, для подстановок
имеем
Данный пример показывает, что симметрическая группа
не является абелевой (некоммутативная) при
Порядок данной группы
количество всех перестановок из
элементов. Единичная (тождественная) подстановка обозначается
которая удовлетворяет
Обратной
является подстановка
для которой верно, что
Утверждение 7.6.1. Симметрическая группа
степени 2 — абелева.
• Определение. Подстановка
, перемещающая элементы
так, что
оставляющая на месте остальные элементы, называется циклом длины к и обозначается
Равносильное определение. Подстановка называется циклической, если каждый из ее действительно перемещаемых элементов
можно перевести в любой другой (из действительно перемещаемых элементов), если подстановку применить достаточное число раз. Например,
Теперь цикл можно записать:
Пример.
— цикл длины семь.
• Определение. Два цикла называются независимыми, если они не содержат общих действительно перемещаемых элементов. Например, (1, 2, 3, 5, 9) и
независимые циклы.
• Теорема 7.6.1. Каждую нетождественную подстановку
можно разложить единственным образом в произведение независимых циклов.
Доказательство. Пусть
Элементы
назовем эквивалентными
если
для некоторого целого числа k. Введенное отношение есть отношение эквивалентности на множестве
Оно разбивает множество
непересекающиеся классы эквивалентности по этому отношению
Каждый элемент
принадлежит одному и только одному классу
причем множество
состоит из образов элемента
при действии степеней подстановки
где
— количество элементов в
Множества
еще называют
-орбитами. Выберем в каждом классе
по одному представителю
и поставим ему в соответствие цикл
Так как любой элемент, не принадлежащий
остается на месте при действии степеней
то перестановка
есть произведение независимых циклов
• Замечание 1. Если цикл
имеет длину 1, то он действует как тождественная подстановка. Такие циклы в записи
можно опускать.
• Замечание 2. Независимые циклы в записи
можно произвольным образом переставлять между собой. Так,
где
Пример.
• Определение. Декрементом
подстановки называется разность между числом действительно перемещаемых элементов и числом независимых циклов, на которые она раскладывается. Подстановка называется четной, если
четное число и подстановка нечетная, если
нечетное. Введем функцию
Свойство 1. Для
верно, что
в противном случае
Отсюда, умножая справа последнее равенство на
получим
, а так как
, то
, что противоречит выбору
Свойство 2. Для любой нечетной подстановки
существует прообраз
четной подстановки, так как
Свойства 1, 2 позволяют утверждать, что отображение
является взаимно однозначным.
• Утверждение
подгруппа симметрической группы
Теорема 7.6.5 Кэли. Всякая конечная группа
порядка
изоморфна некоторой подгруппе симметрической группы
Доказательство. Для любого элемента
рассмотрим отображение
состоящее в умножении всех элементов
слева на
Свойство группы
позволяет утверждать, что
взаимно однозначное отображение (подстановка). Обратным к
будет отображение
единичным отображением является
Вследствие ассоциативности умножения в группе
имеем замкнутость:
т.е.
Отсюда следует, что множество
образует подгруппу в множестве всех взаимно однозначных отображений
в себя, т.е. в симметрической группе Тогда отображение
. Sm такое, что
есть изоморфизм, поскольку
взаимно однозначное и выполняется свойство
сохранения операций.