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

Пусть

— произвольная подстановка степени п. Если для некоторого I число отлично от I, то говорят, что подстановка а действительно перемещает число в противном случае говорят, что подстановка а оставляет число I на месте.

Рассмотрим циклическую подгруппу группы состоящую из степеней подстановки а. Если — порядок этой подгруппы, то она состоит из подстановок

причем все эти подстановки различны. Пусть — произвольное действительно перемещаемое подстановкой а число. Обозначим через число, в которое переводит число подстановка . Очевидно, что подстановка а переводит число в число . Если бы оказалось, что , то, применяя к этому равенству подстановку мы получили бы, что т. е. что подстановка а оставляет, вопреки предположению, число на месте. Следовательно, все числа действительно перемещаются подстановкой а. Среди этих чисел имеется не более различных, ибо очевидно, равно Если числами

исчерпываются все числа, действительно перемещаемые подстановкой а, то подстановка а называется циклом и обо-Эначается символом ().

В этом случае все числа различны,

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

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

где — все числа из ряда отличные от чисел

Заметим еще, что запись цикла в виде неоднозначна. Именно

т. e. запись цикла можно начйнать с любого действительно перемещаемого им числа. С точностью до преобразований такого рода запись цикла, как легко видеть, однозначна.

Количество чисел, действительно перемещаемых циклом а, называется его длиной. Из сказанного выше ясно, что длина цикла равна его порядку.

Наименьшая возможная длина цикла равна двум. Циклы длины два называются транспозициями. Транспозиция переводит число I в число число j — в число t и оставляет все остальные числа на месте.

Задача. Доказать, что подстановка, действительно перемещающая только два числа, является транспозицией.

Любой цикл длины является произведением транспозиций.

Действительно,

Два цикла называются независимыми, если они не имеют общих действительно перемещаемых чисел. Очевидно, что при перемножении независимых циклов порядок множителей не играет никакой роли (т. е. независимые циклы, как говорят, перестановочны).

Оказывается, что любая не тождественная подстановка является произведением независимых циклов.

Мы докажем это утверждение индукцией по числу s действительно перемещаемых чисел. С этой целью заметим, во-первых, что число s не может быть равно единице. Действительно, если подстановка а переводит число I в число , то число Y она не может оставлять на месте, так как в противном случае два различных числа i к j переводились бы подстановкой а в одно и то же число j. Поэтому . Если , то подстановка является транспозицией, и следовательно, теорема для нее справедлива. Тем самым начальный этап индукции обоснован.

Предположим теперь, что теорема уже доказана для всех подстановок, действительно перемещающих менее s чисел, и рассмотрим произвольную подстановку а, действительно перемещающую s чисел. Пусть — одно из чисел, действительно перемещаемых подстановкой а. Применяя к этому числу изложенное выше построение (т. е. воздействуя на него степенями подстановки ), мы получим числа действительно перемещаемые подстановкой а (см. выше). Пусть первое из этих чисел с положительным номером, совпадающее с числом . Такое число существует, так как, например, число , где — порядок подстановки а, равно числу . Докажем, что числа все различны. Действительно, если, например, то, применяя к этому равенству подстановку мы получим что в силу минимальности числа q невозможно.

Поскольку числа все различны (и , ибо ; см. выше), то мы можем составить цикл

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

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

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