7.6. Симметрическая группа подстановок

Пусть конечное множество из элементов. Множество всех взаимно однозначных отображений множества на себя называется симметрической группой степени Без ограничения общности можно считать, что множество состоит из элементов Каждое такое отображение называется подстановкой или перестановкой и записывается где образ элемента Произведением подстановок является композиция отображений (операция группы)

Например, для подстановок имеем Данный пример показывает, что симметрическая группа не является абелевой (некоммутативная) при Порядок данной группы количество всех перестановок из элементов. Единичная (тождественная) подстановка обозначается которая удовлетворяет Обратной является подстановка для которой верно, что

Утверждение 7.6.1. Симметрическая группа степени 2 — абелева.

• Определение. Подстановка , перемещающая элементы так, что оставляющая на месте остальные элементы, называется циклом длины к и обозначается

Равносильное определение. Подстановка называется циклической, если каждый из ее действительно перемещаемых элементов можно перевести в любой другой (из действительно перемещаемых элементов), если подстановку применить достаточное число раз. Например, Теперь цикл можно записать:

Пример. — цикл длины семь.

• Определение. Два цикла называются независимыми, если они не содержат общих действительно перемещаемых элементов. Например, (1, 2, 3, 5, 9) и независимые циклы.

• Теорема 7.6.1. Каждую нетождественную подстановку можно разложить единственным образом в произведение независимых циклов.

Доказательство. Пусть Элементы назовем эквивалентными если для некоторого целого числа k. Введенное отношение есть отношение эквивалентности на множестве Оно разбивает множество непересекающиеся классы эквивалентности по этому отношению Каждый элемент принадлежит одному и только одному классу причем множество состоит из образов элемента при действии степеней подстановки где — количество элементов в Множества еще называют -орбитами. Выберем в каждом классе по одному представителю и поставим ему в соответствие цикл Так как любой элемент, не принадлежащий остается на месте при действии степеней то перестановка есть произведение независимых циклов

• Замечание 1. Если цикл имеет длину 1, то он действует как тождественная подстановка. Такие циклы в записи можно опускать.

• Замечание 2. Независимые циклы в записи можно произвольным образом переставлять между собой. Так, где

Пример.

• Определение. Декрементом подстановки называется разность между числом действительно перемещаемых элементов и числом независимых циклов, на которые она раскладывается. Подстановка называется четной, если четное число и подстановка нечетная, если нечетное. Введем функцию

где тогда

Например, для подстановки (45) декремент равен следовательно, подстановка нечетная.

• Определение. Цикл длины 2 называется транспозицией Для транспозиции декремент нечетное число.

• Теорема 7.6.2. При умножении подстановки на транспозицию она меняет свою четность.

Доказательство. Пусть разложение подстановки в произведение независимых циклов. Умножим ее на транспозицию Рассмотрим все возможные случаи:

4. принадлежат одному и тому же циклу.

5. принадлежат разным циклам.

Пусть к — число действительно перемещаемых элементов число независимых циклов в разложении . Декремент подстановки

1. Пусть тогда Декремент

2. Пусть а Будем считать, что В этом случае Декремент

3. Случай рассматривается подобно

4. Пусть а принадлежат одному и тому же циклу. Тогда Декремент

5. Пусть принадлежат разным циклам. Тогда Декремент

Таким образом, во всех случаях четность подстановки меняется.

• Теорема 7.6.3. Каждая подстановка разлагается в произведение транспозиций не единственным образом, однако четность числа транспозиций постоянна и совпадает с четностью самой подстановки.

Доказательство. разложение подстановки в произведение независимых циклов. Каждый цикл разлагается в произведение транспозиций Таким способом можно разложить в произведение транспозиций все циклы подстановки где транспозиции. Теорема 7.6.2 позволяет записать

Таким образом, четность подстановки совпадает с четностью числа транспозиций в разложении

• Следствие произвольные подстановки.

Доказательство. Пусть разложения в произведение транспозиций Тогда разложение в произведение транспозиций. Из теоремы

• Следствие обратная подстановка. Доказательство. Пусть тогда так как тождественная подстановка, где транспозиции. Первое следствие позволяет записать . С другой стороны, тождественная подстановка и Тогда следовательно,

• Теорема 7.6.4. Число четных подстановок равно числу нечетных.

Доказательство. Достаточно показать, что так как Для этого установим взаимно однозначное соответствие между четными и нечетными подстановками.

Пусть произвольная фиксированная транспозиция. Рассмотрим отображение где Пусть а произвольная четная подстановка, тогда нечетная подстановка.

Свойство 1. Для верно, что в противном случае Отсюда, умножая справа последнее равенство на получим , а так как , то , что противоречит выбору

Свойство 2. Для любой нечетной подстановки существует прообраз четной подстановки, так как

Свойства 1, 2 позволяют утверждать, что отображение является взаимно однозначным.

• Утверждение подгруппа симметрической группы

Теорема 7.6.5 Кэли. Всякая конечная группа порядка изоморфна некоторой подгруппе симметрической группы Доказательство. Для любого элемента рассмотрим отображение состоящее в умножении всех элементов слева на Свойство группы позволяет утверждать, что взаимно однозначное отображение (подстановка). Обратным к будет отображение единичным отображением является Вследствие ассоциативности умножения в группе имеем замкнутость: т.е. Отсюда следует, что множество образует подгруппу в множестве всех взаимно однозначных отображений в себя, т.е. в симметрической группе Тогда отображение . Sm такое, что есть изоморфизм, поскольку взаимно однозначное и выполняется свойство сохранения операций.