Разложение подстановок на циклы.

При изучении групп подстановок большое значение имеет представление подстановок в виде произведений так называемых циклов. По определению символом обозначается подстановка, переводящая в снова в а все остальные элементы рассматриваемого множества оставляющая на месте. Так, например, если рассматриваются подстановки чисел 1, 2, 3, 4, 5, то

Подстановка вида называется циклической или цйклом длины называются элементами цикла. Единичная подстановка условно записывается в виде циклов длины 1. Циклы длины 2 называются транспозициями. Переставляя элементы цикла в циклическом порядке, мы получаем ту же самую подстановку, например

Легко проверяется, что циклы без общих элементов, например (2, 3) и (1, 4, 5), являются коммутирующими подстановками, и поэтому при перемножении таких циклов можно не обращать внимания на порядок сомножителей в произведении.

Значение циклов в общей теории основывается на следующей теореме: всякая подстановка может быть представлена в виде произведения циклов без общих элементов, причем это представление однозначно с точностью до порядка сомножителей.

Доказательство теоремы непосредственно видно из способа такого представления. Допустим, что мы желаем разложить подстановку Мы видим, что А переводит 1 в 4, 4 в 3, 3 в 6, 6 в 1.

В результате имеем первый множитель (1, 4, 3, 6). Берем оставшееся число 2 и видим, что А переводит 2 в 5, 5 в 2. Поэтому второй множитель будет (2, 5). Поскольку все числа рассмотрены, то

Разложение подстановок на циклы, имеющие общие элементы, также возможно, но уже неоднозначно. Например,

Докажем, что каждый двойной цикл есть нечетная подстановка. Мы уже убедились в этом для цикла (1, 2). Но любой цикл есть где — любая подстановка переводящая 1 в Подстановка есть нечетная подстановка, ибо (1, 2) нечетная, одновременно или четные или нечетные.

Согласно формуле (3), цикл длины может быть представлен в виде произведения нечетных подстановок. Поэтому цикл длины есть подстановка нечетная, если четно, и четная, если нечетно. Это дает возможность быстро подсчитать четность подстановок, разложение которых на циклы известно. В частности, подстановка четна так как она согласно формуле (2), есть произведение двух нечетных подстановок.