Симметрическая группа

Определение 3.5.1. Пусть W – конечное множество из n элементов для произвольного . Поскольку природа его элементов для нас не существенна, удобно считать, что W = {1, 2,…, n }. Всякая биекция, то есть взаимно однозначное преобразование W называется подстановкой на множестве W. В развернутой и наглядной форме подстановку , i = 1, 2,…, n, удобно изображать в виде двухстрочной таблицы: . В этой таблице каждый i -й столбец четко указывает, в какой элемент f (i) преобразуется элемент i, .

Композиция подстановок, как композиция биекций, является подстановкой. Подстановки перемножаются в соответствии с общим правилом композиции функций: gf (i) = g (f (i)), i = 1, 2,…, n.

Пример 3.5.1. Пусть , . Тогда

,

аналогично . Как видим, fg ¹ gf, то есть композиция подстановок не обладает свойством коммутативности. ·

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

Пример 3.5.2. Для подстановки найдем обратную подстановку f ^–1. Получаем, что . Чтобы убедиться в правильности вычислений, найдем композиции этих двух подстановок в том и другом порядке:

;

. ·

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

Определение 3.5.2. Группу всех подстановок на n -элементном множестве относительно операции композиции называют симметрической группой степени n и обозначают S_n.

Несложно видеть, что все вышесказанное справедливо не только для конечного, но и для произвольного непустого множества W. Таким образом, множество всех биективных преобразований W образует группу относительно операции композиции, обозначаемую S (W) и называемую симметрической группой множества W.

Теорема 3.5.1. Порядок группы S_n равен n!.

Исходя из определения подстановки как взаимно однозначного преобразования n -элементного множества, утверждение справедливо согласно теореме 2.2.2.

Таким образом, | S ₂ | = 2, | S ₃ | = 6, | S ₄ | = 24, | S ₅ | = 120 и т.д.

Разложим подстановки из S_n в произведение более простых подстановок. Суть разложения сначала поясним, рассмотрев подстановки f и g из примера 3.5.1.

Пример 3.5.3. Подстановка f кратко записывается в виде f = (1 3 4 2) или, что то же самое, в виде f = (3 4 2 1) = (4 2 1 3) = (2 1 3 4) и носит название цикла длиной 4. Подстановка g = (1 3)(2 4) – произведение двух независимых (не пересекающихся) циклов (1 3) и (2 4) длиной два. Разложение в произведение независимых циклов подстановок f и g изображено на рис. 3.5.1. ·

Рис. 3.5.1

Перейдем теперь к общему случаю. Пусть S_n – произвольная симметрическая группа степени n и f – произвольная подстановка из S_n. Пусть Г_f = < f > – циклическая подгруппа в S_n, порожденная подстановкой f. Элементы i и j множества W = {1, 2,…, n } назовем Г_f -эквивалентными, если найдется такая подстановка для подходящего целого k, что g (i) = j. Тогда g ^–1(j) = i. Очевидно, отношение Г_f -эквивалентности на множестве W рефлексивно (g = f ⁰ = e), симметрично (g (i) = j, g ^–1(j) = i) и транзитивно . Тогда W разбивается на попарно непересекающиеся классы Г_f -эквивалентных друг другу элементов, называемых f-орбитами или Г_f -орбитами: W = W ₁ È…È W_p. Каждый элемент i Î W принадлежит в точности одной f -орбите, и если i Î W_k, то W_k состоит из образов элемента i при действии степеней f: i, f (i), f ²(i),…, (i), где l_k = | W_k | – длина f -орбиты W_k. Очевидно, l_k £ | < f > | – порядка подгруппы < f >. Ясно, что (i) = i, причем – наименьшее натуральное число с таким свойством.

Определение 3.5.3. Положим

.

Тем самым получим подстановку, называемую циклом длиной l_k, действующую тождественно на остальных элементах из W.

Итак, f_k действует как f на W_k и тождественно на W \ W_k. Это дает основание считать циклы f_k и f_m при k ¹ m независимыми или непересекающимися (так как они действуют на непересекающихся множествах W_k и W_m). Таким образом, разбиению W = W ₁ È…È W_p соответствует разложение подстановки f в произведение: , при этом циклы-сомножители независимы и перестановочны. Естественно в произведении опускать сомножители, соответствующие орбитам W_i из одного элемента, так как – тождественная подстановка на W.

Пример 3.5.4. Подстановку можно разложить в произведение независимых циклов следующим образом: f = (1 3 4 5 6)(2 8)(7) = (1 3 4 5 6)(2 8). ·

Итак, выше была доказана следующая теорема.

Теорема 3.5.2. Каждая подстановка , f ¹ e, является произведением независимых циклов длинами l_k ³ 2. Это разложение в произведение определено однозначно с точностью до порядка следования циклов.

Следствие. Порядок подстановки (порядок циклической группы Г_f) равен наименьшему общему кратному длин независимых циклов, входящих в разложение f.

Пусть – цикл длиной . Найдем в группе .

и т.д.,

Отсюда видно, что l_k – наименьшее натуральное число, такое что . Значит, = l_k. Итак, порядок любого цикла равен длине этого цикла.

. Согласно теореме 3.5.2 каждая подстановка , f ¹ e, является произведением независимых циклов длинами l_k ³ 2, и это разложение определено однозначно с точностью до порядка следования циклов. Порядок подстановки делится на порядок каждого цикла, который входит в ее разложение, причем это наименьшее число с таким свойством по определению порядка элемента группы. Значит, порядок такой подстановки равен НОК порядков этих циклов, то есть длин этих циклов.

Определение 3.5.4. Цикл длиной 2 называется транспозицией.

Теорема 3.5.3. Каждая подстановка , f ¹ e, разлагается в произведение транспозиций.

Согласно теореме 3.5.2 каждая подстановка , f ¹ e, является произведением независимых циклов длинами l_k ³ 2. Для доказательства данной теоремы достаточно убедиться в том, что каждый цикл длиной l_k ³ 2 можно разложить в произведение транспозиций следующим образом:

.

Это проверяется непосредственным умножением транспозиций. Но данный способ разложения цикла длиной l_k ³ 2 в произведение транспозиций не является единственным. Итак, каждая подстановка , f ¹ e, разлагается в произведение транспозиций.

Пример 3.5.5. Разложим подстановку в произведение независимых циклов и транспозиций:

g = (1 4 6 8 3)(2 5 7 9) = (1 3)(1 8)(1 6)(1 4)(2 9)(2 7)(2 5) =

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

На данном примере убеждаемся в том, что разложение подстановки в произведение транспозиций неоднозначно. ·

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

Определение 3.5.5. Подстановка называется четной, если она разлагается в произведение четного числа транспозиций, в противном случае она называется нечетной. Тождественную подстановку также относят к четным, полагая, что в ее разложении нуль транспозиций.

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

Теорема 3.5.4. Все четные подстановки группы S_n образуют подгруппу A_n; при n = 1 A_n = S_n, при n ³ 2 | A_n | = n!/2.

Когда n = 1, A_n = S_n = { e }, поэтому, очевидно, A_n £ S_n.

При n ³ 2 покажем, что A_n £ S_n согласно критерию подгруппы (теорема 3.3.1). Рассмотрим " f, g Î A_n и разложим их в произведения транспозиций:

f = t ₁… t _{2 k} , g = t ₁… t _{2 l} , где k, l Î Z _³0.

Тогда , поскольку в разложении количество всех транспозиций-сомножителей равно 2 k + 2 l = 2(k + l) – четное число. Итак, A_n £ S_n.

Пусть n ³ 2. Рассмотрим смежный класс tA_n, где t – некоторая транспозиция. Получим класс нечетных подстановок: tA_n Í S_n \ A_n. Допустим, | A_n | = | tA_n | = a, а | S_n \ A_n | = n! – a = b, тогда a £ b. Теперь рассмотрим множество S_n \ A_n всех нечетных подстановок и применим к ним одну и ту же транспозицию t – получим столько же четных подстановок, то есть | S_n \ A_n | = | t (S_n \ A_n) | = b и t (S_n \ A_n) Í A_n, поэтому b £ a. Итак, a = b. Множества всех четных и нечетных подстановок не пересекаются и в объединении дают все множество S_n. Значит, | A_n | = | S_n \ A_n | = n!/2.

Следствие. A_n – нормальная подгруппа группы S_n; при n ³ 2 S_n: A_n = 2.

При n = 1 A_n = S_n = { e }, поэтому, очевидно, A_n S_n.

При n ³ 2 согласно теоремам 3.5.4 и 3.4.2 S_n: A_n = | S_n |/| A_n | = n!/(n!/2) = 2. И, как было показано в примере 3.4.3, любая подгруппа индекса 2 нормальна. Следовательно, A_n S_n и в этом случае.

Определение 3.5.6. Подгруппа A_n всех четных подстановок группы S_n называется знакопеременной группой степени n.

Дата добавления: 2014-01-04