Полугруппы преобразований и группы подстановок

Пусть X есть n -множество, P(X) - моноид всех преобразований множества X и S (X) - группа всех обратимых элементов моноида P(X), то есть группа всех подстановок множества X. Если X ¢ - также n -множество, то P(X)@P(X ¢) и S (X)@ S (X ¢). Это позволяет для любого n -множества рассматривать моноид - симметрическую полугруппу преобразований степени n, обозначаемую P _n, и симметрическую группу S_n всех подстановокстепени n. Подгруппы группы S_n называют группами подстановок.

Теорема 4.6. Всякая полугруппа G порядка n изоморфна некоторой полугруппе преобразований (n +1)-множества.

t Пусть G ={ g ₁,…, g_n }. Положим X = G È{ g ₀} и элементу g_i полугруппы G поставим в соответствие преобразование j _i множества X, i =1,…, n, называемое левым g_i -сдвигом:

j _i (g ₀)= g_i, j _i (g_j)= g_{i *} g_j, j =1,…, n.

Рассмотрим функцию f: G ®{j₁,…,j _n }, реализующую указанное соответствие. Функция f есть биекция, так как преобразования j₁,…,j _n попарно различны, это следует из того, что j _i (g ₀)¹j _j (g ₀) при i ¹ j. Пусть g_jg_i = g_r для i, j Î{1,…, n }, тогда

f (g_jg_i)(g ₀)= f (g_r)(g ₀)=j _r (g ₀)= g_r = g_jg_i =j _j (g_i)=j _j (j _i (g ₀))=(j _j j _i)(g ₀)= f (g_j) f (g_i)(g ₀),

f (g_jg_i)(g_k)= f (g_r)(g_k)=j _r (g_k)= g_rg_k = g_jg_ig_k =j _j (g_ig_k)=j _j (j _i (g_k))=(j _j j _i)(g_k)= f (g_j) f (g_i)(g_k).

Значит, {j₁,…,j _n } - полугруппа преобразований и f (g_jg_i)= f (g_j) f (g_i). Следовательно, f – изоморфизм. u

Заметим, моноид G порядка n изоморфен некоторой полугруппе преобразований n -множества.

Теорема 4.7 (Кэли). Всякая конечная группа G порядка п изоморфна некоторой подгруппе группы S_n.

t Пусть е, g ₁, g ₂, …, g_{n -1} – все элементы группы G. Для фиксированного элемента а группы G рассмотрим отображение j _а (g) =а _* g. Имеем подстановку

j _а = .

Вместе с тем, получаем отображение G ® S_n, при котором а ®j _а. Убедимся, что это и есть искомый изоморфизм.

Во-первых, это отображение инъективно, так как различным элементам а и b группы G отвечают различные подстановки j _а и j _b (в первом случае е ® а, а во втором - е ® b).

Во-вторых, это отображение согласовано с операциями, то есть, j _{а * b} (х) = j _а ×j _b (х)при любых а, b, х Î G. Действительно,

j _{а * b} (х)= а _* b _* х,(j _а ×j _b)(х)=j _а (j _b (х))= а _* b _* х. u

Циклическая глубина и период преобразования g связаны с характеристиками графа Г(g).

Утверждение 4.2. Для g ÎP(X):

а) dep g есть наибольшая из длин всех подходов к циклам графа Г(g);

б) per g = НОК (l ₁,..., l_m), где l ₁,..., l_m - все различные длины циклов графа Г(g);

в) в частности, если g – подстановка,разлагающаяся в произведение циклов длины l ₁,…, l_k, то ord g = НОК (l ₁,…, l_k). w

Пусть G -полугруппа (группа) преобразований множества X и S ={ g ₁,…, g_p } - система образующих элементов полугруппы (группы) G, то есть G =á S ñ.

Пусть H – группа подстановок множества X. Преобразования g и h из P(X) называются сопряженными или подобными в группе H (при H = S (X) просто сопряженными или подобными), если в H найдётся подстановка d, при которой g =d^-1× h ×d. По утверждению 4.3а отношение подобия относительно группы H, заданное на моноиде P(X), есть отношение эквивалентности.

Теорема 4.12. Преобразования g и h множества X подобны Û изоморфны графы Г(g) и Г(h) этих преобразований.

t а) Если преобразования g и h множества X подобны, то у = g (х) Û d(у)= h (d(х)) при некоторой подстановке dÎ S (X). Следовательно, графы Г(g) и Г(h)изоморфны, так как отличаются лишь переобозначением вершин с помощью подстановки d. Обратное утверждение доказывается рассуждениями в обратном порядке. u

Следствие. Подстановки g, h Î S_n сопряжены Û g и h имеют одинаковую цикловую структуру. w

Сопряженные подстановки имеют одинаковые порядки.

Пусть G £P(X). Элементы x, y Î X называются G – эквивалентными (обозначается x @ ^Gy), если g (x)= y и g ¢(y)= x для некоторых преобразований g, g ¢Î G.

Отношение @ ^G является отношением эквивалентности на X ¢.

Подмножества множества X ¢, образующие классы G –эквивалентности, называются областями транзитивности полугруппы G. Если G =á S ñ, где S ={ g ₁,…, g_p }, то области транзитивности полугруппы G суть компоненты сильной связности графа Г _S (X).

Полугруппа преобразований G называется транзитивной, если X - ее единственная область транзитивности, и интранзитивной в противном случае. Орбитой элемента x Î X ¢ относительно полугруппы G (обозначается G (x)) называется область транзитивности полугруппы G, содержащая элемент x.

Циклическая полугруппа преобразований á g ñ типа (d, n) не транзитивна при d >1. Действительно, разбиение множества Х на непустые подмножества циклических и ациклических вершин графа Г(g ¢) одинаково для всех преобразований g ¢ полугруппы á g ñ, отсюда в á g ñ не найдется преобразования, отображающего любую циклическую вершину графа Г(g) в любую ациклическую вершину.

Стабилизатором элемента x в полугруппе (группе) преобразований G называется подмножество всех преобразований полугруппы (группы) G, для которых элемент x является неподвижным (обозначается St _x (G)).

Отметим некоторые свойства стабилизатора элемента x в полугруппе преобразований G множества X.

1) Если St _x (G)¹Æ при x Î X, то St _x (G)£ G.

2) Если x @ ^Gy для x, y Î X, то g ¢ g ÎSt _x (G) и gg ¢ÎSt _y (G), т.е. St _x (G)¹Æ Û x Î X ¢.

Пусть G – группа подстановок множества X. Элементы x, y Î X называются G – эквивалентными, если g (x)= y для некоторой подстановки g Î G. Данное отношение является отношением эквивалентности на X, так как каждый элемент X является циклическим в графе Г _S (X). Классы G –эквивалентности называются областями транзитивности группы G. Если G =á S ñ, где S ={ g ₁,…, g_p }, то области транзитивности группы G суть компоненты связности в Г _S (X). Группа подстановок G называется транзитивной (интранзитивной), если X – ее область транзитивности (X разбивается на две или более областей транзитивности). Орбитой элемента x Î X относительно группы G (обозначается G (x)) называется область транзитивности группы G, содержащая элемент x.

Обозначим через X ^{[ k ]} множество всех неупорядоченных бесповторных выборок размера k из алфавита X. Свойство транзитивности групп подстановок, определяющее переходы символов x, обобщается на свойство k -транзитивности (k - натуральное), определяющее возможность перехода любой выборки x ¢ в любую выборку y ¢, где x ¢, y ¢Î X ^{[ k ]}.

Неупорядоченные бесповторные выборки (x ₁,…, x_k) и (y ₁,…, y_k) из X ^{[ k ]} называют G – эквивалентными (обозначается (x ₁,…, x_k)@ ^G (y ₁,…, y_k)), если g (x_i)= y_i для некоторой подстановки g Î G, i =1,…, k. Определенное отношение @ ^G является отношением эквивалентности на X ^{[ k ]}.

Подмножества множества X ^{[ k ]}, образующие классы G –эквивалентности, называются областями k - транзитивности группы G. Группа G называется k - транзитивной, еслиее единственная область k -транзитивности есть X ^{[ k ]}, и k - интранзитивной в противном случае. Орбитой выборки (x ₁,…, x_k) относительно группы G (обозначается G (x ₁,…, x_k)) называют область k -транзитивности полугруппы G, содержащую эту выборку.

Свойство k -транзитивностигрупп допускает также вероятностную интерпретацию. Вероятностная мера задается на элементах группы, и возможность преобразования выборок характеризуется соответствующими вероятностями.

Теорема 4.13 (лемма Бернсайда). Для любого x Î X и любой подгруппы G группы S (X)

ô G ô=ôSt _x (G)ô×ô G (x)ô.

Следствие. Для транзитивной группы G и любого x Î X:

ô G ô=ôSt _x (G)ô×ô X ô. w

Теорема 4.14 [17, т.2, стр.282].Группа подстановок G является k -транзитивной Û G транзитивна и для некоторого x Î X является (k -1)-транзитивной подгруппа St _x (G), рассматриваемая как группа подстановок множества X \{ x }. w