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

Пусть множество X состоит из n элементов , расположенных в произвольном, но фиксированном порядке.

Биекция называетсяподстановкой.

В случаях, когда природа элементов не имеет значения, удобно обращать внимание только на индексы и считать, что мы имеем дело с множеством . Следовательно,

.

Обозначим - множество всех подстановок наA. Очевидно, что .

На множестве будем рассматривать операцию перемножения (композиции) подстановоки:

для любого .

Эта операция обладает свойствами:

1) - выполняется свойство ассоциативности;

2) существует подстановка , для которойдля каждого- выполняется аксиома существования единичного элемента;

3) для любого существуеттакое, что- выполняется аксиома существования обратного элемента.

Следовательно, множество образует группу относительно операции перемножения перестановок. Отметим, что эта операция не является коммутативной, то есть, например,

,

.

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

Пример 1. Пусть .

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

Пример 2. Пусть .

Подстановка p не является циклом, но может быть представлена в виде композиции двух циклов:

причем эти циклы являются непересекающимися, т.е. не имеют общих нестационарных элементов.

Теорема 1. Любая подстановка может быть представлена в виде композиции непересекающихся циклов длины:

.

Доказательство теоремы дает процедуру построения циклов.

Найдем в A наименьший нестационарный относительно элемент, т.е.и для каждоговыполняется условие: если, то. (Если такого элемента не существует, тоявляется тождественной подстановкой () и ее можно рассматривать как пустое произведение циклов).

Будем строить образы элемента ,до тех пор, пока не получимпри наименьшем из возможныхk (). Тогда подстановка

определяет цикл длины k внутри подстановки . Если все нестационарные элементы подстановкисодержатся в, то. В противном случае найдем- наименьший из нестационарных элементов подстановки, не входящий в цикл. Строим цикл

.

Очевидно, что и- непересекающиеся. Если все нестационарные элементы исчерпаны, то, в противном случае повторяем процесс, пока каждый нестационарный элемент не войдет в какой-либо цикл. В конечном итоге получим.

Пример. Представить в виде композиции циклов подстановку

.

, значит ;

,значит;

- стационарный элемент.

Следовательно, .

Определение. Порядком подстановки называется наименьшее натуральное числоp такое, что .

Теорема 2. Порядок подстановки равен наименьшему общему кратному порядков циклов в ее разложении на непересекающиеся циклы.

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

2.2.3. Изоморфизм групп

Определение. Группы иназываютсяизоморфными, если существует биекция , сохраняющая групповую операцию, т.е.

для всех .

Пример. Пусть - группа преобразований правильного треугольника в себя, где- тождественное преобразо-вание,- поворот вокруг точкиO на 120, - поворот вокруг точкиO на 240, - отражение относительно осей симметрииI, II, III соответственно (рис. 2.3).

2

IIII

1 3

II

Рис. 2.3. Преобразование правильного треугольника

В качестве группы рассмотрим группу подстановок на множествевершин треугольника , где

, ,,

, ,.

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

Будем называть порядком конечной группы количество ее элементов.

Теорема (Кэли). Всякая конечная группа порядка n изоморфна некоторой подгруппе группы подстановок .

Доказательство. Пусть произвольная подгруппа порядкаn. Обозначим группу подстановок на множестве. Зафиксируем произвольный элементи рассмотрим отображениетакое, чтодля любого. Очевидно, образы различных элементовx и y, принадлежащих , различны и, следовательно, множество значений. Действительно, предположим, чтопри. Тогда.

Значит, отображение является подстановкой на множестве, причем,,, т.е. множествообразует подгруппу группы. При этом

.

Следовательно, отображение такое, чтоявляется изоморфизмом, т.к..

Задача. Найти группу подстановок, изоморфную группе поворотов правильного восьмиугольника на плоскости.

Решение задачи провести самостоятельно.