§ 7. ОБРАЗУЮЩИЕ СИММЕТРИЧЕСКОЙ ГРУППЫ

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

Рис. 18

Решение. Занумеруем картины в первоначальном порядке числами . Пусть на место первой картины нужно повесить картину с номером на место второй — картину с номером и т. д., наконец, на место картины — картину с номером — разные числа из множества Перемещаясь вдоль стены обозначенным способом в одном направлении картины последовательно занимает все места, на которых висят картина. Поэтому картину с номером можно повесить на место первой картины (рис. 18). Выбирая направление перемещения картины с номером так, чтобы не двигать картину с номером картину с номером можно повесить на место второй. Аналогично, выбирая такое направление перемещения, чтобы не двигать картины с номерами картину с номером можно повесить на место третьей. Продолжая этот процесс дальше, каждую картину можно повесить на нужное место. Следовательно, ответ на вопрос, поставленный в задаче, утвердительный.

Сформулируем теперь эту задачу на языке перестановок. Занумеруем места, на которых висят картины, так, чтобы нумерация мест совпадала с нумерацией картин в первоначальном положении. Размещение картин, при котором картина с номером висит на первом месте, картина с номером — на втором и т.д., картина с номером — на месте, однозначно описывается перестановкой

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

Если в положении, которое описывается перестановкой (1), поменять местами картины, которые стоят на местах то перестановка которая будет характеризовать это новое положение, будет результатом умножения перестановки а слева на транспозицию

Если переход от первоначального положения к желаемому, которому отвечает перестановка осуществляется за s шагов, то можно записать

где — некоторые транспозиции. Следовательно, вопрос задачи можно сформулировать так: можно ли разложить произвольную перестановку в произведение транспозиций?

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

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

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

(проверьте!). Пользуясь этим, каждую перестановку, разложив ее сначала в произведение циклов, можно представить в виде произведения транспозиций.

Пример 1. Разложить в произведение транспозиций перестановку

Раскладываем в произведение циклов:

Далее, имеем

Следовательно,

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

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

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

(Убедитесь, что перестановки, которые стоят справа и слева в этом равенстве, одинаково действуют на каждый элемент из М.) Поскольку любую перестановку можно разложить в произведение транспозиций вида , то, заменив в этом разложении все транспозиции в соответствии с равенством (2), получим разложение в произведение транспозиций системы II.

В свою очередь, произвольную транспозицию из последовательности II можно разложить в произведение перестановок системы I по равенству

Проверим, правильно ли равенство (3). Пусть Перестановка - действует на элементы 1 и k так:

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

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

Действительно, если , то , а поэтому

Таким образом, каждая перестановка системы I раскладывается в произведение перестановок , потому что элемент (У имеет конечный порядок, например так что

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

В § 5 было введено понятие графа как совокупности точек на плоскости, некоторые из которых соединены стрелками. Такие графы называют ориентированными, поскольку на стрелку, соединяющую две точки, можно смотреть как на путь с фиксированной ориентацией, которая указывается направлением стрелки. Вдоль такого отрезка разрешается проходить только в одном направлении — в том, которое указано стрелкой. Здесь нам понадобится понятие неориентированного графа, которое введем следующим образом.

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

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

Граф связан, если любые две вершины этого графа соединены по крайней мере одним путем. Мы рассматриваем графы без петель, т. е. без ребер, которые начинаются и заканчиваются в одной вершине. Такой граф называется деревом, если в нем нет замкнутых путей. Деревом является, например, граф, изображенный на рис. 196, а графы 19 а, в - - деревьями не являются.

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

Рис. 19

Пусть А — некоторое множество транспозиций из По множеству А строится неориентированный граф, вершины которого обозначены числами , причем вершины i, j соединены ребром тогда и только тогда, когда транспозиция принадлежит множеству А. Например, множеству транспозиций (1, 2), (2, 3), (2, 5), (3, 5), (4, 5) соответствует граф, изображенный на рис. 19 а, а множеству (1, 2), (1, 3), (2,3), (4, 5) — граф, изображенный на рис. 19 в. Граф, построенный по некоторому множеству А транспозиций, часто называют графом Пойа этого множества. Множества транспозиций, являющиеся системами образующих симметрической группы (приводимыми или нет), выделяются по свойствам своих графов Пойа.

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

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

Доказательство. Как и при проверке равенства (3), покажем, что перестановки из правой и левой частей равенства (4) действуют на любой элемент множества М одинаково. Пусть . Тогда и т. д. На шаге получим Действуя на элемент любой из транспозиций получим тот же элемент. Таким образом, перестановка, стоящая в правой части равенства (4), элемент i переводит в элемент . Для элемента получаем равенства , т. е. элемент этой подстановкой переводится в i. Пусть теперь Транспозиция оставляет элемент на месте. Если , то все транспозиции также оставляют на месте и, следовательно, этот элемент является неподвижной точкой для перестановки из правой части (4). Если совпадает с каким-то элементом , то имеем следующие - равенства: т. e. элемент является неподвижной точкой подстановки правой части из (4). Лемма доказана.

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

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

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

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

причем в множество А входят лишь такие транспозиции для которых при некотором k элементы одновременно содержатся в . Поэтому множество А можно разбить на подмножеств (некоторые из которых могут быть пустыми), включая в подмножество те и только те транспозиции для которых i, Произведение транспозиций из множества — это некоторая перестановка на множестве М, подвижные точки которой принадлежат Так как попарно не пересекаются, то при любых перестановки, порождаемые транспозициями из А и являются взаимно простыми. Итак, любую перестановку которая раскладывается в произведение транспозиций из множества А, можно разложить в произведение

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

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

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

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

Рис. 20

Неприводимые системы образующих, целиком состоящие из транспозиций, называют базисами симметрической группы . Поскольку графы Пойа систем I и II, приведенных на с. 52, являются деревьями, (рис. 20), то эти системы неприводимы. По виду графов Пойа базис I называется линейным базисом, а базис II — звездообразным. Оба эти базиса состоят из транспозиции. Это неслучайно. Покажем, что любое дерево с вершинами содержит ребро.

Воспользуемся методом математической индукции по числу . Случай — база индукции. В этом случае имеется лишь одно дерево, и оно имеет одно ребро. Предположим, что любое дерево с вершинами содержит ребро, и рассмотрим произвольное дерево с вершинами. В любом дереве имеется по крайней мере одна «висячая» вершина, т. е. такая, которая соединена ребром только с одной вершиной дерева. (Если в конечном графе нет «висячих» вершин, то в нем обязательно есть замкнутые пути.) Удалим из дерева эту вершину и ребро, из нее выходящее. Получим снова связный граф, являющийся деревом. Поскольку число вершин этого графа равно , к нему применимо предположение индукции, т. е. он содержит ребра. Следовательно, исходное дерево содержит ребро. Из этого простого утверждения получаем следующий важный вывод о базисах симметрической группы все базисы симметрической группы равномощны и состоят из транспозиции.

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