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

Обозначим через Х конечное множество, а его элементы – через 1,2,...,п. Рассмотрим все биекции (подстановки) s: Х ® X. Легко видеть, что они образуют группу относительно операции композиции отображений. Эта группа называется симметрической группой п-й степени и обозначается через S_n или через S(X). Нетрудно показать, что |S_n |= п!. Так, например, группа S₃ состоит из шести подстановок:

В нижней строке указаны образы элементов 1, 2, 3, расположенных в верхней строке. Условимся при вычислении произведения подстановок s₁s₂ выполнять отображения справа налево, т.е. сначала отображение s₂, а затем s₁. Например:

Подгруппы симметрической группы называются группами подстановок.

Подстановку вида 1®2®3®…®k®1 назовем циклом длиной k и обозначим (1,2,…,k). Два цикла называются независимыми, если перемещаемые ими элементы попарно различны. Независимые циклы коммутируют, т. e. для них выполнено условие s₁s₂ =s₂s₁. Цикл длиной 2 называется транспозицией.

Теорема 1. Каждая подстановка единственным образом разложима в произведе­ние независимых циклов.

Теорема 2. Каждая подстановка tÎ S_n является произведением транспозиций.

Ни о какой единственности не может быть и речи хотя бы потому, что для любой транспозиции t и подстановки s имеем st²=s. Тем не менее, характер четности числа k в разложении подстановки в произведение транспозиций p=t₁t₂…t_k определяется подстановкой p однозначно. В самом деле, умножение подстановки на транспозицию меняет характер четности перестановки p=a₁a₂…a_n на противоположный. Поэтому, если транспозиции t₁t₂…t_k приводят перестановку a₁a₂…a_n к виду 1,…,n, то p=t_k…t₁, и наоборот, поэтому характер четности подстановки p совпадает с характером четности перестановки a₁a₂…a_n. Подстановка называется четной или нечетной в зависимости от четности числа k.

Теорема 3. При п > 1 количество четных подстановок равно количест­ву нечетных подстановок и равно п!/2.

Нетрудно показать, что все четные перестановки образуют подгруппу группы S_n. Эта подгруппа называется знакопеременной группой и обозначается через А_n. При n>1 имеем разложение S_n = А_n È(1,2)А_n. Поэтому [S_n: А_n]=2. Для любой подстановки pÎS_n смежные классы pА_n и А_np состоят из всех четных или всех нечетных подстановок в зависимости от четности подстановки p. Поэтому S_n <S_n.

Теорема 4 (Кэли). Всякая конечная группа G изоморфна подгруппе симметрической группы S_n, где п =|G |.