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

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

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

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

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

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

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

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

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

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

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