Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

2.2. Группы на матрицах и подстановках

Группа 12-го порядка и групповые закономерности

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

C₃C₄ ≈ C₁₂   и   C₂C₆ ≈ .

Изоморфизм существует и среди некоммутативных групп, а именно: C₂D₃ ≈ , образующими которых будут:

C₂D₃:     a = (012),     b = (02),     c = (34),

:     a = (012345),     b = (15)(24).

Чтобы лучше понять сущность изоморфизма, все группы 12-го порядка сведем в табл. 2.24. В графах d_i этой таблицы приведены результаты деления порядка группы на наименьшее общее кратное длин циклов, входящих в подстановки. Изоморфные группы имеют одинаковые наборы этих чисел: для C₃C₄ и C₁₂ справедлив перечень чисел d₁, для C₂C₆ и — d₂, а для C₂D₃ и — d₃.

Таблица 2.24

Числа d_i отражают одинаковое циклическое строение подстановок. Однако одинаковые ряды d_i служат необходимым и достаточным условием изоморфизма только для коммутативных групп. Для некоммутативных групп данное условие является лишь необходимым, но далеко не достаточным, в чем мы убедимся, рассматривая группы 16-го порядка.

В табл. 2.24 приведены элементы и ряды d_i еще для двух групп 12-го порядка. Одна из них, с рядом d₄, в чем-то напоминает группу кватерниона, так как для нее 2-циклы, полученные от образующих a и b, равны между собой: a³ = b². Таким образом, в подобных группах (а они встречаются для всех групп, порядок которых делится на 4) существует одна-единственная подстановка, которая состоит из совокупности транспозиций; все остальные подстановки имеют цикличность больше двух. Для сравнения с приведем полную систему равенств между элементами последней группы:

Оставшаяся некоммутативная группа 12-го порядка называется группой тетраэдра ( T ), поскольку она отвечает группе вращения этой геометрической фигуры. На примере группы T проиллюстрируем одно, довольно неприятное, свойство определяющих соотношений — их неоднозначность. Для получения конкретных элементов группы тетраэдра в качестве образующих можно взять два связанных 3-цикла с двумя общими индексами, тогда система определяющих соотношений будет выглядеть так:

Как видим, в этих равенствах фигурируют элементы, составленные из трех букв. Если в качестве образующих взять 2- и 3-циклы, то в определяющих соотношениях появятся элементы из четырех букв:

Чтобы исчерпать все двенадцать подстановок комбинациями из двух букв, нужно выбрать в качестве образующих три 3-цикла. Однако в этом случае возрастет и число возможных равенств — T :

Число 12 раскладывается на три простых множителя — 2 · 2 · 3. Зададимся вопросом, не будут ли группы 20-го (2 · 2 · 5), 28-го (2 · 2 · 7) и т.д. порядков иметь аналогичное строение? Имея перед собой упорядоченные таблицы умножения размером 12 · 12, можно попытаться составить аналогичные таблицы размером 20 · 20, 28 · 28 и т.д. Приведем таблицы 12 · 12 для группы диэдра (табл. 2.25), группы типа кватерниона (табл. 2.26) и группы тетраэдра T (табл. 2.27).

Таблица 2.25

Таблица 2.26

Составить по аналогии таблицы умножения для коммутативных групп порядков 20-го, 28-го и т.д. не представляет большой сложности. Повторить приведенные таблицы для групп , , , и т.д. тоже нетрудно. Однако придумать таблицы умножения размером 20 · 20 и 28 · 28, аналогичные табл. 2.27, не удается. Групп 20-го и 28-го порядков с тетраэдральной структурой просто не существует. В табл. 2.28 приведены возможные варианты групп интересующих нас порядков. Оказывается, групп 28-го порядка только четыре, а групп 20-го — пять, однако группа, которую мы обозначили как , далека от тетраэдрального строения. Возникает вопрос, как вообще осуществляется поиск новых групп?

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

Таблица 2.27

Таблица 2.28

Прежде всего, примем фундаментальное условие для образующих a и b, касающееся их цикличности: a¹⁰ = b⁴ = e. Затем, по аналогии с группой , предположим справедливость равенства ab = ba⁹. Ясно, что в группе должен существовать элемент aba⁹. Представим его двумя способами:

aba⁹ = a · ba⁹ = a · ab = a²b, 

aba⁹ = ab · a⁹ = ba⁹ · a⁹ = ba⁸.

Следовательно, в искомых соотношениях есть равенство a²b = ba⁸. Далее, возьмем элемент a²ba⁸ и снова распишем его двумя способами, получив новое соотношение a³b = ba⁷. Беря подходящие элементы, в том числе bab, b²a³b, и представляя их двумя указанными способами, находим все необходимые соотношения группы , которые мы сейчас выписывать не будем.

Если бы мы взяли за основу равенство ab = ba³, нам не удалось бы его совместить с кватернионным условием a⁵ = b², которое неизбежно возникает в группе . Выбранное равенство влечет за собой соотношение ab² = b²a⁹. Если принять условия: a¹⁰ = b⁴ = e, ab = ba³ и a⁵ ≠ b², число элементов в новой группе возросло бы до 40, что также для нас неприемлемо. Поиск неизвестной группы 20-го порядка тетраэдрального строения уместно начать с равенства a⁵ = b⁴ = e. Далее, наудачу, берем снова равенство ab = ba³ и смотрим, что получится из элемента aba³:

aba³ = a · ba³ = a · ab = a²b, 

aba³ = ab · a³ = ba³ · a³ = ba.

Получаем новое равенство a²b = ba. Затем ищем равенство, отвечающее элементу a²ba. Продолжая аналогичным образом, находим все элементы новой группы, которая, однако, совершенно не похожа на группу T. Обозначив ее как (общепринятой системы обозначений для всех групп пока не выработано), выпишем все ее элементы, вместе с определяющими соотношениями :

В данном случае нам повезло: выбор какого-то нового исходного равенства, например, ab = ba⁴, приведет к изоморфной группе. Других же групп 20-го порядка, кроме перечисленных в табл. 2.28, не существует.

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

{4 = 2 · 2, 9 = 3 · 3, 25 = 5 · 5, ...},

{6 = 2 · 3, 10 = 2 · 5, 14 = 2 · 7, ...}.

Только что рассмотренная группа попадает в ряд групп, порядок которых определяется формулой: n = (p – 1) · p, где p – простое число. Так получается последовательность:

{2 = 1 · 2, 6 = 2 · 3, 20 = 4 · 5, 42 = 6 · 7, ...}.

Одни последовательности возрастают медленно, как например, ряды групп диэдра и кватерниона:

{2, 4, 6, 8, 10, 12, ... , n = 2 · k},

{4, 8, 12, 16, 20, ... , n = 4 · k},

другие стремительно, как например, ряд из симметрических групп:

{2, 6, 24, 120, 720, ... , n = k!}.

Последовательности пересекаются друг с другом. В точках пересечения могут получаться изоморфные группы или совершенно отличные — предсказывать здесь что-либо трудно. Существуют такие порядки, где пересекается множество рядов с самыми различными организационными принципами. Этими точками пересечения являются группы порядков 16, 24, 32, 48, 64 и т.д. Так, для 64-го порядка имеется 267 структурных разновидностей. Дать определяющие соотношения всем группам, даже для такого достаточно скромного порядка, как 64-й, представляется весьма непростой задачей.