§ 12. ОРБИТЫ ГРУППЫ ПЕРЕСТАНОВОК. ЛЕММА БЕРНСАЙДА

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

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

б) любые два элемента из О можно перевести друг в друга некоторой перестановкой из

Всякая группа перестановок имеет орбиты.

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

а) если , то , так как (ведь G — группа);

б) если — произвольные элементы из , то ; и при этом так как G — группа.

Оказывается, что орбитами подобного вида исчерпываются все типы орбит. Более точно, если О — орбита группы G и то . Справедливость этого утверждения вытекает непосредственно из определения орбиты группы.

Ясно, что любые две орбиты либо совпадают (если ), либо не пересекаются (если ). Отсюда (почти так же как и при доказательстве теоремы Лагранжа) следует, что множество М распадается в объединение непересекающихся псдмножеств — орбит группы G. В частности, может случиться, что единственной орбитой группы G будет само множество как это имеет место для групп (проверьте!). Группы с таким свойством называются транзитивными. Таким образом, группа перестановок G на множестве М транзитивна, если любой элемент может быть получен из любого другого элемента ЬМ под действием подходящим спбсобом выбранной перестановки Все другие группы перестановок называются интранзитивными.

В связи с разбиением множества М на орбиты группы перестановок G возникают следующие два вопроса:

1) Сколько орбит имеет группа G на множестве М?

2) Какова длина каждой из этих орбит, т. е. из скольких элементов они состоят?

Сформулируем вначале утверждение, позволяющее выяснить ответ на второй вопрос. Оно формулируется с использованием понятия стабилизатора элемента из М. А именно: для любого элемента можно рассмотреть множество всех перестановок из G, для которых точка а является неподвижной. Это множество, очевидно, является группой (еще один способ образования групп перестановок!), которая и называется стабилизатором точки

Теорема. Длина орбиты равна индексу стабилизатора в группе G, т. е.

Доказательство. Пусть

Для подсчета различных элементов в последовательности удобно особым образом расположить в ряд элементы группы G. Для этого вспомним примененное при доказательстве теоремы Лагранжа разложение группы G в правые классы смежности по подгруппе

Существуют перестановки из группы G, такие, что все перестановки ряда.

попарно различны и исчерпывают всю группу G. Для любого применение s перестановок образующих строку таблицы (1), к элементу а дает один и тот же элемент Все I элементов попарно различны. Действительно, если бы Для некоторых , то т. е. перестановка Но это возможно только тогда, когда содержатся в одном правом классе смежности группы G по подгруппе чего быть не может.

Таким образом, длина орбиты равна , т. е. числу строк в таблице (1). А это число в § 10 и было названо индексом подгруппы в группе.

Проиллюстрируем понятие орбиты группы и доказанную теорему на примере 4 из § 9, где рассматривалась группа перестановок действующая на множестве . Имеем Выбирая какой-нибудь элемент из М, не принадлежащий скажем 6, получим Таким образом, группа перестановок G на множестве М имеет две орбиты:

и поэтому является интранзитивной.

Стабилизатор точки 1 из состоит из одной перестановки е. Поэтому . Стабилизатор точки 6 из состоит из перестановок . Разложение группы G на правые классы смежности по подгруппе имеет вид

Поэтому

Докажем теперь утверждение, чисто исторически называемое леммой Бернсайда по имени английского математика-алгебраиста В. Бернсайда (1852—1927), который, по-видимому, первым опубликовал его доказательство в своей книге по теории конечных групп (1911 г.). Это простое утверждение является основой теории перечисления, разработанной Д. Пойа и рядом других математиков, — теории, находящей широкие применения в кибернетике, технике, органической химии, биологии и т. д.

Пусть — число неподвижных точек перестановки — число орбит группы перестановок действующей на множестве

Рис. 32

Лемма Бернсайда. Для любой группы перестановок имеет место равенство

Доказательство. Рассмотрим отношение «перестановка а сохраняет неподвижным элемент между перестановками группы G и элементами множества М. Сопоставим парам , вершины прямоугольной сети и отметим те из них, для которых соответствующая пара находится в указанном отношении, т. е. (рис. 32). Иными словами, построим график указанного отношения. Число отмеченных точек (точек, принадлежащих графику) можно подсчитать двумя способами: определить число отмеченных точек на каждой вертикали и просуммировать полученные величины или же определить число таких точек по каждой горизонтали и затем вычислить их сумму.

Согласно определению отношения на каждой вертикали отмечаются все точки, сохраняемые перестановкой а, соответствующей этой вертикали. Их число равно . Поэтому число всех точек графика равно

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

Поэтому при втором способе подсчета числа отмеченных точек графика рассматриваемого отношения получаем выражение

Однако если элементы содержатся в одной орбите, то и поэтому . Пусть — все орбиты группы G, такие, что и слагаемые в этом объединении не пересекаются. Разобьем сумму (2) на части так, чтобы внутри каждой из частей суммирование шло по элементам некоторой орбиты:

Каждое из t слагаемых в правой части этого равенства можно преобразовать следующим образом

Поэтому

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

т. е. . Лемма доказана.

В частности, если группа G транзитивная, т. е. , то по лемме Бернсайда

Упражнения

1. Пусть G — группа симметрий куба. Найдите порядок стабилизатора некоторой вершины в этой группе. Какие перестановки в нем содержатся?

2. Проверьте правильность утверждения леммы Бернсайда на примере группы G (пример 4 § 9).

3. Перестановки из группы G сопряжены в ней» если в G найдется такая перестановка у, что . Доказать, что а) каждая перестановка сопряжена сама с собой; б) если перестановка а сопряжена с перестановкой , то и, наоборот, перестановка Р сопряжена с перестановкой а; в) если а сопряжена с , то а сопряжена с у.

4. Из свойств а), б), в) упражнения 3 следует, что множество G разбивается в объединение непересекающихся подмножеств перестановок, попарно сопряженных между собой, которые называются классами сопряженных перестановок группы G. Докажите это.

5. Если перестановки сопряжены, то т. е. функция постоянна на классах сопряженных элементов

6. Используя предыдущую задачу, показать, что формулу для определения числа орбит группы G можно переписать в виде

где — общее значение для перестановок класса сопряженных перестановок, — число перестановок в классе сопряженных перестановок, s — число классов сопряженных перестановок.

7. Доказать, что сопряженные перестановки имеют одинаковый тип.

8. Если перестановки сопряжены, то при любом перестановки и РЛ тоже будут сопряженными. Доказать это.

Следует ли из сопряженности пар перестановок сопряженность их произведений?

9. Группа вращений куба естественным образом определяет группу перестановок на множестве его ребер. Определить типы всех перестановок из этой группы.

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