55. Перестановки.

До сих пор мы рассматривали примеры групп, элементами которых являлись линейные преобразования. Понятие группы не связано обязательно операциями линейного преобразования и может быть построено и для операций другого рода. Мы переходим сейчас к рассмотрению операций, с которыми уже встречались раньше [2], а именно переходим к рассмотрению перестановок. Выясним сначала некоторые основные факты и понятия, относящиеся к перестановкам.

Пусть имеется некоторых объектов, которые мы, как и в [2], пронумеруем, т. е. будем просто считать, что эти объекты суть целые числа . Из этих чисел мы, как известно, можем составить перестановок. Возьмем одну из этих перестановок

Числа в своей совокупности дают все целые числа от 1 до , причем в перестановке (26) они расставлены в определенном порядке. Сравним перестановку (26) с основной перестановкой :

Переход от основной перестановки к перестановке (26) совершается путем замены 1 на на и так далее. Обозначим эту операцию одной буквой Р и будем в дальнейшем называть ее перестановкой. Определим теперь понятие об обратной перестановке

Это будет такая операция, которая переводит (26) в основную последовательность, т. е. заменяет на 1, на 2 и так далее. Разъясним это на частном примере: возьмем и рассмотрим перестановку

Обратная перестановка будет иметь вид:

Нетрудно видеть, что

Введем теперь понятие о произведении перестановок. Пусть и — какие-нибудь две перестановки. Назовем произведением перестановок такую перестановку, которая получается в результате применения сначала перестановки а затем перестановки Например, если мы имеем две перестановки

то их произведение будет давать перестановку вида:

Непосредственно очевидно, что обратная перестановка вполне определяется из условия

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

Последовательно применяя несколько перестановок, мы можем составить произведение нескольких перестановок Нетрудно видеть, что такое произведение удовлетворяет сочетательному закону, т. е.

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

где — любая перестановка.

Произведение перестановок не будет, вообще говоря, удовлетворять переместительному закону, т. е. произведения и будут, вообще говоря, различными перестановками. Предлагаем проверить это на предыдущем примере.

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

Совокупность всех перестановок образует, очевидно, группу. Перейдем теперь к установлению еще другой группы, которая составляет лишь часть предыдущей. Заметим для этого, что всякая перестановка может быть выполнена при помощи нескольких транспозиций [2], причем для заданной перестановки число транспозиций может быть различным, но, как мы доказали выше, оно будет всегда для заданной перестановки или четным, или нечетным. Перестановки, состоящие из четного числа транспозиций, образуют сами по себе группу. Группа, образованная всеми перестановками, называется обычно симметрической группой, а группа, состоящая из четных перестановок, т. е. из перестановок, сводящихся к четному числу транспозиций, называется знакопеременной.

Рассмотрим теперь перестановки особого типа. Пусть какие-нибудь различных чисел из первых чисел. Положим, что наша перестановка состоит в замене на на и так далее, на и, наконец, на . Перестановку такого типа назовем циклом и обозначим ее символом . Совершая круговую перестановку чисел внутри скобки, мы будем получать циклы:

которые, очевидно, дают ту же перестановку, что и Если , т. е. если мы имеем цикл (4), то такой цикл равносилен, очевидно, единичной перестановке, и его не имеет смысла рассматривать. Цикл из двух чисел равносилен, очевидно, транспозиции элементов

Если имеются два цикла без общих элементов, то их произведение не зависит от порядка сомножителей.

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

Оба эти произведения дают, очевидно, одну и ту же перестановку

Мы можем всякую перестановку Р представить в виде произведения циклов, не имеющих общих элементов. Чтобы сделать это, возьмем элемент 1 и примем его за первый элемент в цикле. За второй элемент цикла возьмем тот элемент, который получается из 1 при помощи Р. Пусть это будет За третий элемент возьмем тот, который получается из при помощи Р и так далее, пока, наконец, не дойдем до такого элемента, который переходит в 1 при помощи Р. Это и будет последний элемент составленного цикла. Нетрудно видеть, что этот цикл не может содержать одинаковых элементов. Составленный таким образом цикл не исчерпает, вообще говоря, все элементов. Из оставшихся элементов возьмем какой-нибудь за первый элемент нового цикла и, как и выше, составим второй цикл и т. д.

В качестве примера возьмем перестановку при :

Применяя предыдущий прием, можем представить ее в виде произведения циклов

причем порядок сомножителей справа не играет роли.

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

а при наличии общих элементов:

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

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

Пусть имеется некоторая перестановка

Обратную перестановку мы можем, очевидно, записать в виде:

Пусть имеются две перестановки, причем вторую мы запишем двояко:

Мы имеем:

и, следовательно,

Из написанного вытекает следующее правило: чтобы получить перестановку надо в обеих строчках перестановки

совершить перестановку Q.