§ 19 ПЕРЕСТАНОВОЧНЫЕ КОНСТРУКЦИИ

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

Понятно, что для конечных множеств имеет место равенство

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

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

т. е. упорядочим по возрастанию вначале первые компоненты, а при равных первых компонентах — вторые, и тоже по возрастанию. (Такой порядок называется лексикографическим.)

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

Рис. 39

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

Примеры. 1. Пусть и на множествах заданы соответственно перестановки

Тогда

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

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

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

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

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

Примеры. 3. Пусть

Тогда — перестановка на множестве . Согласно определению, имеем

Таким образом, перестановка имеет следующую таблицу значений:

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

Получим следующую перестановку:

Эту перестановку можно сконструировать в два этапа.

А именно: разбиваем множество на две одинаковые части {1, 2, 3} {4, 5, 6} и на каждой из этих частей производим такую же перестановку, как . Получим перестановку

Затем переставляем эти части во второй строке таблицы, не изменяя порядок элементов в них.

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

естественно сопоставлять произведению перестановок

В самом деле, перестановка задается таблицей

которой при задании нумерации элементов прямого произведения {1, 2, 3}х{1, 2, 3} соответственно упорядочению (1) отвечает как раз таблица 7.

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

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

Будем называть так построенную перестановку сплетением перестановок с помощью перестановки а и обозначать символом

Итак, согласно определению, действие сплетения перестановок с помощью перестановки а на произвольный элемент определяется равенством

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

Поскольку — конечные множества, то достаточно проверить, что преобразование инъективно. Пусть — различные пары из прямого произведения . Это означает, что выполнено по крайней мере одно из неравенств или . Если , то и, независимо от того равны между собой числа или нет, пары между собой различны. Пусть теперь Тогда и пары между собой различны, поскольку . Итак, для произвольных различных пар из имеем

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

Примеры. 5. Пусть

— перестановка на множестве

— перестановки на множестве

Сплетение перестановок с помощью а действует на множестве так:

Таким образом, перестановка имеет таблицу значений

При принятой нами нумерации множества ей сопоставляется следующая таблица:

6. Пусть . Сплетение перестановок с помощью перестановки а действует на произвольный элемент согласно равенству

Это действие совпадает с действием прямого произведения перестановок , т. е. имеет место равенство

Пусть теперь G и Н — произвольные множества перестановок на множествах соответственно.

Определения. 1. Суммой множеств перестановок G и (в предположении, что ) называется множество всевозможных перестановок вида где а

2. Прямым произведением множеств перестановок G и называется множество всевозможных перестановок вида где

3. Сплетением множеств перестановок G и Н называется множество всевозможных перестановок вида , где .

Прямую сумму множеств перестановок G и М обозначим символом их прямое произведение — символом а сплетение — . Понятно, что имеют место следующие равенства:

а)

б)

в)

Теорема. Если — группы перестановок, то также являются группами перестановок на соответствующих множествах.

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

Пусть — две перестановки из Произведение этих перестановок действует на произвольный элемент

Но совпадает либо с (при ), либо с (при ). Если то тоже содержится в Поэтому Аналогично, если то тоже содержится в этом множестве и Итак, произведение перестановок множества действует на произвольный элемент таким же образом, как и перестановка Следовательно, имеет место равенство Поскольку G и Н — группы, то замкнуто относительно умножения перестановок.

Пусть теперь — две перестановки из Произведение действует на произвольную пару согласно равенствам

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

Снова замкнуто относительно умножения перестановок.

И наконец, пусть — две перестановки из причем

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

Имеем равенства

Таким образом, произведение АВ на первую компоненту пары действует, как перестановка а на вторую компоненту — как перестановка т. е. АВ является сплетением перестановок с помощью перестановки а следовательно, содержится в . Итак, замкнуто относительно умножения перестановок. Теорема доказана.

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

Упражнения

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

2. Пусть - тип перестановки а на множестве - тип перестановки на множестве Каков тип перестановки на множестве

3. Установите, что для порядков перестановок выполняется соотношение

4. Постройте таблицу перестановки , где

и таблицу, соответствующую при принятой нумерации множества {1, 2, 3}х{1, 2, 3}.

5. Как, зная порядок - перестановок , определить порядок перестановки

6. Проверить, что группа перестановок

есть прямая сумма циклических групп второго порядка на множествах {1, 2} и {3, 4}, а группа перестановок

является прямым произведением циклической группы второго порядка над множеством М = {1, 2} на себя, причем подстановки из этого прямого произведения записаны с учетом принятой нами нумерации элементов множества

7. Указать обратные к перестановкам , где перестановки на некоторых множествах,

8. Пусть

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

Как определить обратную к перестановке вида

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

11. Пусть Укажите конструкцию, с помощью которой группа симметрий этого многочлена строится из симметрических групп действующих на подходящих множествах,

12. Перестановка а над множеством М имеет следующее разложение в произведение взаимно простых циклов;

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

соответственно,