Любой .цикл длани т является произведением т - 1 транспозиций. Действительно,

(о l 2 • • • im-d = (о l) Со ik m-l)-

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

Оказывается, что

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

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

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

. . ., .....действительно перемещаемые подстановкой а

(см. выше). Пусть первое из этих чисел с положительным номером, совпадающее с числом i. Такое число существует, так как, например, число 1, где т - порядок подстановки а, равно числу 1. Докажем, что числа 1, 1, ... .... все различны. Действительно, если, например, ti=bii p, то, применяя к этому равенству подстановку а", мы получим 1о = 1р, что в силу минимальности числа q невозможно.

Поскольку числа 1, .....все различны (и q>l,

ибо (qIi, см. выше), то мы можем составить цикл(/о/1...

... Ig-i)- Подстановка а (/о li . . . оставляет на месте

все числа, которые оставляются на месте подстановкой а,

а кроме того и все числа Iq.....Таким образом, она

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

(о • • •

Так как каждый цикл разлагается на транспозиции, то из доказанной теоремы следует, что

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

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

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

3. Четные подстановки. Знакопеременная группа

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

Uk)ilk) = ilJ)Uk), если iфJ, (1)

{tJ){tk) = {tk)Uk), если ]фк (2)

(формулы (1) и (2) выражают, как легко видеть, один и тот же факт, но в различных обозначениях).

Лемма. Если произведение нескольких транспозиций равно тождественной подстановке, то число этих транспозиций четно.

Мы докажем эту лемму индукцией по числу s различных чисел, входящих в записи данных транспозиций. Наименьшее

4 Зак. 160. М. М. Постников

возможное значение числа s равно, очевидно, двум. Если 5 = 2, то рассматриваемое произведение является степенью некоторой транспозиции и поэтому равно тождественной подстановке только тогда, когда показатель степени четен (ибо любая транспозиция имеет порядок 2). Таким образом, в случае s = 2 лемма доказана.

Предполагая теперь, что лемма уже доказана для любого произведения транспозиций, записи которых содержат менее S различных чисел, рассмотрим некоторое, равное тождественной подстановке произведение транспозиций

(;1/2)(/з4)---(ViV = « (3)

в записи которых входит ровно s различных чисел. Пусть I - одно из этих чисел. Пользуясь соотношением (1) и тем, что независимые транспозиции перестановочны, мы можем «переместить вперед» все транспозиции, в запись которых входит число /, т. е. перейти от произведения (3) к рав-рому произведению вида

(;Л)---(Ур)(*1*2)---(*2г-1%2г). (4)

в котором все числа k, .....2r отличны от числа I.

Если /7> 1, то, пользуясь соотношением (2) или соотношением

iiJ)iU)==e. (5)

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

(;Л)(1У ••(2/-lУ• Ho это произведение переводит, очевидно, число в число I и потому не может быть тождественной подстановкой. Следовательно, последний случай невозможен. Таким образом, в результате наших преобразований мы получим равное тождественной подстановке произведение транспозиций, записи которых не содержат числа I. Никаких новых чисел записи этих подстановок, очевидно, не содержат. Следовательно, согласно предположению индукции, в это произведение входит четное число транспозиций. Остается заметить.