Groups-2

2 Группа перестановок Sn (симметрическая группа)

где перестановка A является взаимно-однозначным отображением следующего вида

A : {1, 2, 3, · · · , n − 1, n} ! {a1, a2, a3, · · · , an−1, an}

Все перестановки(3)образуют группу перестановок n объектов в которой под произведе-

(очевидно,что столбцы в такой записи перестановки можно переставлять,так как при этом отображение не меняется)будем понимать перестановку,которая получается последовательным применением перестановок A и B:

Циклическими перестановками или циклами (a1, a2, . . . , ak) (8k n) будем называть перестановки при которых объекты {a1, a2, . . . , ak} переставляют циклически a1 ! a2,

11

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

01

где использовано краткое обозначение для циклов

01

Отметим,что циклы,состоящие из разных объектов,не влияют друг на друга и,соответственно,коммутируют друг с другом,например:

(1, 3, 4) · (2, 6, 5) = (2, 6, 5) · (1, 3, 4)

Цикл (a, b) переставляющий лишь два различных символа,называется транспозицией

01

Утверждение5 Любой цикл распадается в произведение транспозиций:

(a1, a2, . . . , an) = (a1, a2)(a1, a3) · · · (a1, an−1)(a1, an)

Док-во. Достаточно доказать следующее утверждение (8k > 2)

(a1, a2, . . . , ak) = (a1, a2, . . . , ak−1)(a1, ak)

12

Применяя последовательно доказанное утверждение для k = n, n − 1, . . . , 3 утверждение доказано. Так как любая перестановка представима в виде произведения циклов,то из Утверждения5следует,что любая перестановка представима в виде произведения транспозиций.Более того,любая перестановка представима в виде произведения транспозиций.Это утверждение легко может быть понято,так как любые два объекта ai, aj из k объектов {a1, . . . , ak} могут быть переставлены(при этом все другие объекты останутся на месте)

путем последовательных транспозиций.

2.1Образующие группы перестановок Sn

Для группы Sn обычно выбирают один из2-х наборов образующих:

•набор из (n −1) образующих σi = (i, i + 1) (i = 1, . . . , n −1) (соседних транспозиций), которые удовлетворяют соотношениям группы кос

b σi2 = e, (i = 1, . . . , n − 1).

• набор из двух образующих-первой транспозиции σ1 = (1, 2) и самого длинного цикла (1, 2, . . . , n).

Перестановки,которые представляются в виде произведения четного(нечетного)числа транспозиций,называются четными(нечетными).Перестановки представляются в виде произведений неоднозначно,так как транспозиции удовлетворяют соотношениям

(i, j)(j, k) = (j, k)(i, k) = (i, k)(i, j), (i, j)2 = e (8i, j, k),

(5)

[(i, i + 1), (j, j + 1)] = 0 (8|i − j| > 1).

13

Справедливость формул(5)следует из следующей цепочки равенств(для простоты элементы i, j, k мы обозначили как 1, 2, 3):

Так как в правых частях этих равенст стоит одна и та же перестановка,левые части совпадают.

Используя равенства(5)можно легко доказать соотношения группы кос.Действительно выбирая в них j = i + 1, k = i + 2 получим

(i, i+2) = (i, i+1)(i+1, i+2)(i, i+1) = (i+1, i+2)(i, i+1)(i+1, i+2) ) σiσi+1σi = σi+1σiσi+1

Преобразования,использующие соотношения(5),схраняют четность перестановки. Четные перестановки образуют инвариантную подгруппу в группе перестановок Sn, так как очевидно,что присоединенное преобразование h ! ghg−1 (8g 2 Sn) сохраняет четность элементов h.

Например,для группы S3 с образующими e,σ 1, σ2 инвариантной подгруппой будут элементы H = {e,σ 1σ2, σ2σ1},а фактор-подгруппа состоит из двух элементов(смежных классов): E = {e,σ 1σ2, σ2σ1} и K = {σ1, σ2, σ2σ1σ2}. Отметим , что порядок подгруппыH равен3,а индекс(количество смежных классов в S3 по H) - 2.В силу теоремы Лагранжа произведение порядка и индекса подгруппы H равен 6 = 3! и совпадает с порядком группы

S3.

В группе Sn две перестановки,имеющие одинаковое разложение в произведение циклов(то есть одинаковое количество циклов и одинаковые длины соответствующих циклов),содержатся в одном и том же классе сопряженности.Действительно,перестановка, состоящая из m k1, k2 − k1, . . .,

A = (a1, a2, . . . , ak1 )(ak1+1, ak1+2, . . . , ak2 ) · · · (akm−1+1, akm−1+2, . . . , akm )

14

Рис. 1:Диаграма ЮнгаI. λ = (5, 3, 1)

(km = n) преобразованием сопряжение T · A · T −1, где T - произвольная перестановка

состоящую из циклов той же длины.То есть если мы хотим решить вопрос,входят ли две перестановки в один и тот же класс,можно расположить циклы слева направо в порядке убывания их длин,пока самый короткий цикл не окажется на последнем месте справа.Если в двух рассматриваемых перестановках длины всех циклов λ1 = k1, λ2 = k2 − k1, . . ., λm = km − km−1 одинаковы,то эти перестановки принадлежат одному и тому же классу сопряженности,в противном случае это не так.Поэтому число классов равно числу последовательностей целых чисел λ1, λ2, . . . , λm, удовлетворяющих условиям λ1 ≥ λ2 ≥ . . . ≥ λm и λ1 + λ2 + · · · + λm = km = n.Это число называется числом разбиений числа n:

λ = (λm(1)1 , λm(2)2 , . . . , λm(kk) ).

Например,рисунок1изображает диаграмму Юнга (5, 3, 1).Этой диаграмме соответствует

15

несколько перестановок(элементов группы S9).Например,перестановка

(1, 3, 4, 6, 7)(2, 5, 9)(8).

Рассмотрим группу S3.Перестановки из которых состоит эта группа можно разбить на три класса сопряженности

Утверждение6 Рассмотрим класс сопряженности Kλ перестановки 2 Sn, имеющий

разложение в циклы λ = (λm(1)1 , λm(2)2 , . . . , λm(kk) ). Тогда число |Zλ| перестановок g 2 Zλ таких, что g g−1 = , то есть 2 Kλ - стабилен , равно

|Zλ| = m1!λm(1)1 m2!λm(2)2 · · · mk!λm(kk) .

Док-во. Данная перестановка g 2 Zλ либо переставляет циклы одинаковой длинны,либо делает циклическую перестановку внутри цикла.То есть имеется mi! способов для первого действия и λm(i)i для второго действия(число циклов длины λ(i) равно mi).

16

Zλ есть подгруппа в Sn. Вся группа Sn действует на преобразованием сопряжения! g g−1 так,что g g−1 пересчитывает классы сопряженности.То есть из утверждения 6 следует , что размерность класса сопряженностиKλ, содержащий перестановку , отвеча - ющей диаграмме λ равна

Важность группы перестановок определяется тем,что в некотором смысле изучение конечных групп сводится к изучению различных подгрупп группы перестановок.Это формулируется как

Теорема2 (Кэли.) Любая конечная группа порядка n изоморфна некоторой подгруппе группы перестановок Sn.

Док-во. Для конечной группы G порядка n с элементами {g1 = e, g2, . . . , gn} множество элементов {gig1, gig2, . . . , gign} для любого фиксированного элемента gi 2 G совпадает с множеством {g1, g2, . . . , gn},но записанном в другом порядке.Действительно,из gk 6= gm следует,что gigk 6= gigm, то есть все элементы {gig1, gig2, . . . , gign} разные,а следовательно перечисляют изначальный набор {g1, g2, . . . , gn}. То же самое справедливо и для набора {g1gi, g2gi, . . . , gngi}. Таким образом , каждому элементуgi можно поставить в соответствие перестановку

Отсюда следует,что отображение gi ! pi является гомоморфизмом группы G на некоторую подгруппу группы Sn. Так как тождественная перестановка pe является образом

17

всего лишь одного единичного элемента e 2 G, то данное отображение gi ! pi является изоморфизмом. Из этой теоремы следует,что у любой конечной группы G порядка n существует пред-

представление,а следовательно и элементы gi реализуются теми же матрицами.Данное представление называется правым регулярным представлением группы G. Аналогично , рассматривая умножение элементов группы слева на фиксированный элемент gi 2 G, можно определить левое регулярное представление.

Матричные представления,соответствующие регулярному представлению,строятся следующим образом.Рассмотрим конечную группу G с n элементами,которые расставим в некотором порядке в виде вектора (g1, g2, . . . , gn).Действие слева фиксированного элемента gk на этот вектор определяет n-мерное матричное представление T (R)(gk) груп-

gmgkgi = gmgjTji(gk) = glTlj(gm)Tji(gk) = glTli(gmgk),

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

18