Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 9
Текст из файла (страница 9)
В частности, если H < G, тосуществует такое действие G (действие сдвигами на смежныхклассах), для которого H — стабилизатор некоторой точки.Лемма 1.54 (лемма Бернсайда). Пусть конечная группаG действует на конечном множестве X. Количество орбитдействия дается формулой:1 X|Xg |,(1.10)|G|g∈Gгде Xg = {x ∈ X | gx = x} — множество неподвижныхточек g.Доказательство. Обозначим через N количество таких пар(g, x), что g(x) = x.
Подсчитаем число N двумя способами.Вначале просуммируем мощности стабилизаторов всех элементов x ∈ X. Стабилизаторы точек из орбиты точки x, состоящей из s точек, дадут вклад s|Gx | = (G : Gx )|Gx | = |G| (последствию 1.53 мощность орбиты равна индексу стабилизатора). Т. е. каждая орбита дает вклад |G| в число N . Поэтому Nравно числу орбит, умноженному на |G|.50Глава 1.ГруппыПо-другому число N можно посчитать, суммируя количество неподвижных точек |Xg | по всем g. Приравняв дваполученных выражения и разделив на |G|, получаем искомуюформулу (1.10).Лемма Бернсайда часто применяется в перечислительнойкомбинаторике. Приведем один простой пример.Пример 1.55 (подсчет ожерелий). Ожерелье состоит из12 бусин черного или белого цвета, которые жестко закреплены на круглом кольце через равные расстояния.
Ожерельяразные, если их нельзя совместить движением. Сколько естьразных ожерелий?Занумеруем места́ бусин в порядке их следования вдолькольца и для каждого места укажем цвет бусины. Получилимножество N из 212 «помеченных» ожерелий. На этом множестве действует диэдральная группа D12 и те «помеченные»ожерелья, которые попадают в одну орбиту, задают одинаковое в смысле нашей задачи ожерелье. Так что задача свеласьк подсчету числа орбит.Подсчитаем число орбит, пользуясь леммой Бернсайда.Прежде всего заметим, что сопряженные элементы группыдают одинаковый вклад в формулу (1.10): если h = ugu−1и g(x) = x, то h(u(x)) = u(g(x)) = u(x), поэтому u(Xg ) = Xh .С другой стороны, если g(x) = x, то и g k (x) = x. Поэтомунеподвижные точки при действии g остаются неподвижнымии при действии группы hgi.Теперь разберем все возможные случаи.g = e.
Для тождественного отображения неподвижнымиточками будут все 212 = 4096 «помеченных» ожерелий.g — поворот на ±2π/12, ±5 · 2π/12. Группа hgi действует транзитивно на множестве {1, . . . , 12} (1 и 5 взаимно просты с 12). Поэтому неподвижными точками будут только 21«помеченных» ожерелий, в которых все бусины одинаковогоцвета.
Этот случай дает вклад в формулу (1.10) в размере4 · 21 = 8.g — поворот на ±2 · 2π/12. На четных и нечетных местахдолжны стоять бусины одинакового цвета, поэтому общийвклад этого случая 2 · 22 = 8.1.10.Факторгруппы51Рассуждая аналогично, находим, что вклад случая, когдаg — повороты на ±3 · 2π/12 равен 2 · 23 = 16, вклад случая,когда g — повороты на ±4 · 2π/12 равен 2 · 24 = 32, а вкладслучая, когда g — поворот на 6 · 2π/12 равен 26 = 64.Осталось рассмотреть два случая: когда g — поворот наугол π вокруг диагонали 12-угольника, в этом случае общийвклад равен 6 · 27 = 768; а также когда g — поворот на уголπ вокруг середины противоположных сторон 12-угольника, вэтом случае общий вклад равен 6 · 26 = 384.Собирая эти вычисления вместе, получаем ответ:153764096 + 8 + 8 + 16 + 32 + 64 + 768 + 384 == 224.24241.10.
ФакторгруппыПрежде чем давать формальное определение факторгруппы, объясним, что хотелось бы получить. Переход от множества к классам эквивалентности этого множества по некоторому отношению эквивалентности называется факторизацией.Мы хотим факторизовать группу по подгруппе, т. е. перейтик множеству классов смежности по этой подгруппе. В случаепроизвольной подгруппы факторизация по классам смежности переводит группу в более общий объект — действие группы на множестве.
Но иногда это действие можно представитькак действие некоторой новой факторгруппы на себе самойсдвигами. Другими словами, в этом случае можно рассматривать классы смежности по подгруппе как элементы некоторойгруппы. Конечно, мы теряем при факторизации какую-то информацию о группе, но зато полученная факторгруппа будетпроще, изучать ее легче и т. д.Оказывается, что факторизация дает группу только в случае нормальных подгрупп. Рассмотрим вначале пример, когдафакторизация не дает группу.Пример 1.56 (продолжение примера 1.22).
Составим таблицу действия группы S3 на смежных классах по подгруппеH = h(12)i (смежные классы разделены линиями):52Глава 1.ГруппыH (23)H (13)H()H (23)H (13)H(12)H (13)H (12)H(23) (23)HH (13)H(132) (23)H (13)HH(13) (13)H (23)HH(123) (13)HH (23)HКак видим, разные элементы одного смежного класса действуют на смежные классы по-разному. Поэтому из такогодействия нельзя получить бинарную операцию на множествесмежных классов.Теперь рассмотрим случай нормальной подгруппы H ⊳ G.Пусть G/H — совокупность смежных классов G по H. Обозначение подсказывает, что мы «делим» G на H.
Отсюда ещеодно название нормальной подгруппы — нормальный делитель. Чтобы получить группу, на множестве G/H необходимоввести операцию. Сделаем это таким образом: (xH) · (yH) == (xyH).Прежде всего нужно проверить, что данное выше определение корректно. Другими словами, произведение двух классовсмежности должно не зависеть от выбора представляющихклассы элементов x, y. (В противном случае никакой операциина G/H мы бы не получили.)Пусть x′ = xh1 , y ′ = yh2 .
Тогда (x′ H)·(y ′ H) = (xh1 yh2 )H == (xyh3 )H = (xyH) (в среднем равенстве мы использовалинормальность подгруппы H).Теперь докажем, что множество G/H относительно введенной операции является группой.1) Ассоциативность очевидна, так как выполняется в группе G.2) Поскольку (xH) · (eH) = (eH) · (xH) = (xH), подгруппаH (точнее, смежный класс eH, но это и есть сама подгруппа)является единичным элементом.3) Класс x−1 H — обратный к xH относительно введеннойоперации: (x−1 H) · (xH) = (x−1 xH) = (eH).Итак, G/H относительно операции умножения смежныхклассов является группой. Она называется факторгруппой G1.10.53Факторгруппыпо подгруппе H.
Заметим, что если G конечна, то и все ееподгруппы конечны, поэтому|G/H| =|G|= (G : H).|H|Элемент факторгруппы G/H обычно задается указаниемпредставителя x ∈ G класса смежности xH. Чтобы не путатьэлементы группы и элементы факторгруппы, используютсяразличные обозначения: (xH) = x̄ = [x] = {x}.Рассмотрим примеры факторгрупп.Пример 1.57.
G/G ∼= {e}. Мы забываем про группу всё, кроме того, что в ней есть единица.Пример 1.58. G/{e} = G. Здесь мы всё запомнили о группе.Естественно, у нас возникают и промежуточные случаи.Пример 1.59. Возьмем в аддитивной группе целых чисел Zподгруппу 3Z ⊳ Z. Построим факторгруппу Z/3Z. Во-первых,в этой группе есть нулевой элемент 0̄ (здесь естественно использовать аддитивную запись):0̄ = 0 + 3Z,далее берем смежный класс, порожденный элементом 1,1̄ = 1 + 3Z,то же самое для элемента 2 ∈ Z2̄ = 2 + 3Z.Получаем факторгруппу Z/3Z = {0̄, 1̄, 2̄} с операцией сложения, определенной следующей таблицей (в сокращеннойформе):0̄ 1̄1̄ 2̄2̄ 0̄2̄0̄1̄Теперь мы можем забыть, что классы смежности — это множества чисел, и работать с группой из трех элементов.
(Этагруппа называется группой вычетов по модулю 3, и мы ее ужеодин раз построили на с. 15.)54Глава 1.ГруппыВ продолжение этого примера заметим, что если G = hai —циклическая группа, то факторгруппа G/H по любой подгруппе H < G будет также циклической: ясно, что an = (ā)n .Пример 1.60 (продолжение примера 1.41). Имеют местоизоморфизмы (G × H)/(G × {e}) ∼= H, (G × H)/({e} × H) ∼= G.Читателю предлагается построить эти изоморфизмы самостоятельно.1.11. Ядро гомоморфизмаНапомним, что гомоморфизм — это отображение однойгруппы в другую, сохраняющее произведение.
Пусть hG, ·i иhG′ , ◦i — группы, а ϕ — гомоморфизм группы G в группу G′ .Ядром гомоморфизма называется множество Ker ϕ = {g ∈ G |ϕ(g) = e′ }. Т. е. ядро гомоморфизма — это множество элементов группы G, отображающихся в единицу группы G′ . Пустьa ∈ Ker ϕ, b ∈ Ker ϕ, тогда и ab ∈ Ker ϕ (если два элементапринадлежат ядру гомоморфизма, то и их произведение принадлежит гомоморфизму), так какϕ(ab) = ϕ(a) ◦ ϕ(b) = e′ ◦ e′ = e′ .Обратный к элементу, принадлежащему ядру, также принадлежит ядру:ϕ(a−1 ) ◦ ϕ(a) = ϕ(a−1 · a) = ϕ(e) = e′ .Значит ядро является подгруппой G.Пример 1.61. Рассмотрим отображение ϕ : Z → hai аддитивной группы целых чисел Z в конечную циклическую группуhai, порожденную элементом a, которое задается формулой:ϕ : n 7→ an .Очевидно, что это гомоморфизм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
