Полная версия

Главная arrow Математика, химия, физика arrow ДИСКРЕТНЫЙ АНАЛИЗ. ОСНОВЫ ВЫСШЕЙ АЛГЕБРЫ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Действия групп. Лемма Бернсайда

Действием группы G на множестве X называется гомоморфизм ip: G S(X) группы G в группу S(X) биекций множества X (взаимно однозначных отображений множества X на себя). Говорят также, что группа G действует на множестве X. Если ясно, о каком действии идет речь, то ip(g)(x) записывают как д(х). Элементы множества X будем называть точками, чтобы отличать их от элементов группы G.

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

Пример 1.47 (действие левыми сдвигами). Как уже говорилось при доказательстве теоремы Кэли, левый сдвиг на g это преобразование Lg(h) = gh. При доказательстве теоремы Кэли мы проверили по сути, что L: GS(G) — гомоморфизм и, более того, L(G) = G. Поэтому любая группа действует на себе самой умножением слева.

Конечно, можно определить аналогичное действие правыми сдвигами.

Пример 1.48 (действие сопряжениями). Группа действует на себе самой сопряжениями. По определению,

Рис. 1.4.

Фактически уже было доказано, что это гомоморфизм (формула (1.9) на с. 42).

Пример 1.49 (действие на классах смежности). Посмотрим более внимательно на действие группы левыми сдвигами. Пусть есть подгруппа Я группы G. По теореме 1.20 группа G разбивается на классы смежности по подгруппе Я, как показано на рис. 1.4. Там же можно увидеть, что происходит при умножении на некоторый элемент g группы G. Из ассоциативности умножения следует, что умножение на g сохраняет классы смежности но Я: образ g(gH) класса смежности дН является классом смежности с представителем дд. Более того, образы различных смежных классов различны. Действительно, если д(дН) = ggh = дд2^2, h,h2 € Я, т.е. 9 = #2^5 h = }г2^1 € Я, а значит дН = д2Н.

Таким образом мы получаем действие группы па множестве классов смежности (см. рис. 1.5).

Действия из примера 1.49 в некотором смысле исчерпывают все возможные действия групп.

Зафиксируем некоторое действие и будем писать д(х) для обозначения образа точки х при действии элемента д. Дяя любого х ? X определим множество элементов группы G, оставляющих точку х неподвижной: Gx = {д ? G д{х) = т}. Множество Gx называется стабилизатором точки х.

Утверждение 1.50. Стабилизатор Gx — подгруппа G.

Рис. 1.5.

Доказательство. 11роверим свойства подгруппы. Во-первых, е ? Gx, так как е(.т) = х (при гомоморфизме единичный элемент переходит в единичный, а единичный элемент в группе S(X) — тождественное отображение). Во-вторых, так как д(д~1(х)) = X, то из д ? Gx следует д~1 ? Gx. В-третьих, если h ? Gx, то и gh ? Gx, поскольку д(к(х)) = д(х) = х. ?

Орбитой действия называется множество образов некоторой точки х: Ох = {х' е X х' = g(x), д ? G}.

Утверждение 1.51. Орбиты действия разбивают точки множества X на классы эквивалентности.

Доказательство. Проверим свойства отношения эквивалентности.

Рефлексивность: е(х) = х, так как при гомоморфизме единичный элемент переходит в единичный.

Симметричность: если у ? Ох, то х ? Оу, так как из у = = д(х) следует х = д~1 (у).

Транзитивность: если у ? Ox, 2 ? Оу, то .г ? Ох, так как из У = Oi(x), z = д2(у) следует г = {gig2)(x). ?

Между смежными классами но стабилизатору Gx и точками орбиты х существует естественное взаимно однозначное соответствие (мы уже его фактически использовали при подсчете порядка группы многогранника в примере 1.28, с. 30).

Утверждение 1.52. Отображение у —> {д ? G д(х) = = у} сопоставляет каждой точке орбиты Ох класс смежности по стабилизатору Gx. Это соответствие взаимно однозначно.

Доказательство. Вначале докажем, что образом любой точки при отображении является класс смежности. Условие д(х) = h(x) равносильно условию h~1(g(x)) = х, которое означает, что h~1g € Gx и потому д Е hGx.

Из определения р ясно, что прообраз класса gGx при отображении р определен однозначно: это у = д(х).

Осталось доказать, что образ орбиты при отображении р всё множество смежных классов по Gx. Это очевидно: класс смежности gGx является образом точки д(х) при отображении р. ?

Следствие 1.53. Число элементов в орбите равно индексу стабилизатора.: Ох = (G : Gx).

Действие называется транзитивным, если у него ровно одна орбита (любую точку можно перевести в любую действием элемента группы). Доказанные выше утверждения означают, что все транзитивные действия являются, в сущности, действиями группы на смежных классах но некоторой ее подгруппе (стабилизатору точки). В частности, если Н < G, то существует такое действие G (действие сдвигами на смежных классах), для которого II — стабилизатор некоторой точки.

Лемма 1.54 (лемма Бернсайда). Пусть конечная группа G действует на конечном множестве X. Количество орбит действия дается формулой:

где X(J = X gx = х} — множество неподвижных точек д.

Доказательство. Обозначим через N количество таких пар (д, &*), что д(х) = х. Подсчитаем число N двумя способами.

Вначале просуммируем мощности стабилизаторов всех элементов х ? X. Стабилизаторы точек из орбиты точки а;, состоящей из s точек, дадут вклад sGx = (G : GX)GX = |G| (по следствию 1.53 мощность орбиты равна индексу стабилизатора). Т. е. каждая орбита дает вклад |G| в число N. Поэтому N равно числу орбит, умноженному на |С|.

По-другому число N можно посчитать, суммируя количество неподвижных точек Хд но всем д. Приравняв два полученных выражения и разделив на G, получаем искомую формулу (1.10). ?

Лемма Бернсайда часто применяется в перечислительной комбинаторике. Приведем один простой пример.

Пример 1.55 (подсчет ожерелий). Ожерелье состоит из 12 бусин черного или белого цвета, которые жестко закреплены на круглом кольце через равные расстояния. Ожерелья разные, если их нельзя совместить движением. Сколько есть разных ожерелий?

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

Подсчитаем число орбит, пользуясь леммой Бернсайда. Прежде всего заметим, что сопряженные элементы группы дают одинаковый вклад в формулу (1.10): если h = иди-1 и д(х) = сг, то h(u(x)) = и(д(х)) = и(х), поэтому и(Хд) = Xh-

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

Теперь разберем все возможные случаи.

д = е. Для тождественного отображения неподвижными точками будут все 212 = 4096 «помеченных» ожерелий.

д — поворот на ±27г/12, ±5 • 2п/12. Группа (д) действует транзитивно на множестве {1,..., 12} (1 и 5 взаимно просты с 12). Поэтому неподвижными точками будут только 21 «помеченных» ожерелий, в которых все бусины одинакового цвета. Этот случай дает вклад в формулу (1.10) в размере 4 • 21 = 8.

д — поворот на ±2 • 2тг/12. На четных и нечетных местах должны стоять бусины одинакового цвета, поэтому общий вклад этого случая 2 • 22 = 8.

Рассуждая аналогично, находим, что вклад случая, когда д — повороты на ±3 • 27г/12 равен 2 • 23 = 16, вклад случая, когда д — повороты на ±4 • 27г/12 равен 2 • 24 = 32, а вклад случая, когда д — поворот на 6 • 27г/12 равен 26 = 64.

Осталось рассмотреть два случая: когда д — поворот на угол 7г вокруг диагонали 12-угольника, в этом случае общий вклад равен 6 • 27 = 768; а также когда д — поворот на угол 7г вокруг середины противоположных сторон 12-угольника, в этом случае общий вклад равен 6 • 26 = 384.

Собирая эти вычисления вместе, получаем ответ:

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>