Научная библиотека

§ 15. ЧЕТНЫЕ И НЕЧЕТНЫЕ ПЕРЕСТАНОВКИ. ЗНАКОПЕРЕМЕННАЯ ГРУППА

Разложение перестановок из в произведение транспозиций, вообще говоря, не однозначно, например:

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

Теорема. Если — разложения перестановки в произведение транспозиций, то числа s и t имеют одинаковую четность.

Доказательство. Пусть — некоторая перестановка на множестве — разложения в произведение транспозиций. Подействуем перестановкой на знакопеременный многочлен Как было установлено в предыдущем параграфе, А и могут отличаться лишь знаком, причем если а транспозиция, то . Рассмотрим две последовательности многочленов:

В каждой из них два соседних выражения отличаются лишь знаком. А поэтому

С другой стороны, Следовательно, т. е. s и t — числа одинаковой четности.

Теперь можно дать такое определение.

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

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

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

Для этого построим взаимно однозначное отображение V множества на множество

Зафиксируем некоторую транспозицию а; и поставим в соответствие каждому элементу перестановку

Перестановки — разной четности, т. е. и отображение V определено правильно.

Убедимся в том, что отображение биективно. Если и то и потому что равенство можно было сократить на а и получить, вопреки условию, что

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

Каждая транспозиция — нечетная перестановка. Равенство (2) § 7 показывает, что цикл нечетной длины — перестановка четная. Четной будет также тождественная перестановка е. Понятно, что произведение четных перестановок — перестановка четная, произведение двух нечетных перестановок — также четная, а произведение четной на нечетную (или наоборот) — нечетная.

Если перестановка разложена в произведение транспозиций

то обратной к будет перестановка

так как из равенства

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

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

Заметим, что четность перестановки можно определить, не раскладывая ее в произведение транспозиций. Достаточно лишь разложить перестановку в произведение циклов и подсчитать количество циклов четной длины. Если найденное число будет четным, то перестановка четная, в противном случае — нечетная (см. упражнение 11).

Упражнения

1. Какую характерную особенность имеет граф четной перестановки?

2. Какой наивысший порядок могут иметь элементы группы ?

3. Составить таблицу умножения группы А

4. Какая из описанных нами в § 8 подгрупп будет знакопеременной?

5. Найти центр группы упражнение 4 § 9).

6. Доказать что — максимальная подгруппа отличная от т. е. каждая подгруппа, которая содержит , совпадает или или с

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

8. Можно ли разложить каждую четную перестановку где нечетно, в произведение циклов

9. Говорят, что пара чисел и j образует инверсию, если . Доказать, что перестановка

будет четной тогда и только тогда, когда количество инверсий, обравованных элементами ее второго ряда, — число четное.

10. Сколько имеется перестановок из в которых элементы второго ряда образуют ровно 6 инверсий?

11. Пусть перестановки Разность называется декрементом этой перестановки. Доказать, что четность перестановки совпадает с четностью ее декремента.