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

Пусть 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_jj_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_jj_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):

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

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

в) в частности, если g – подстановка,разлагающаяся в произведение циклов длины l₁,…,l_k, то ordg=НОК(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