7. Действие группы на множестве. Орбита и стабилизатор элемента, теорема о порядке стабилизатора элемента. Лемма Бернсайда (1124131), страница 2
Текст из файла (страница 2)
Пусть конечная группа Gдействует на множестве N = {1, 2, . . . , n}. Тогда число N(G )орбит элементов множества N по группе G равноN(G ) =1 Xλ1 (πg ),|G |g ∈Gгде λ1 (πg ) — число неподвижных элементов перестановки πg .Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЛемма БернсайдаДоказательство. Пусть G = {g1 = e, g2 , . . . , gm }.Построим таблицу T = (tij ), в которойtij = 1, если πgj (i) = i;tij = 0, иначе.N \G12T :...nπg1 = e11πg2...πgm...|G1 |...|G2 |......1...|Gn |λ1 (πg1 ) λ1 (πg2 ) . . .
λ1 (πgm )В таблице T число единиц в каждой строке равно порядкустабилизатора элемента — номера этой строки; число единиц вкаждом столбце равно числу неподвижных элементовперестановки с номером этого столбца.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаДоказательство.Число единиц в таблице T можно подсчитатьnPпо строкам как|Gi |i=1и по столбцам какmPλ1 (πgj ).j=1ТогдаnXi=1|Gi | =mXj=1λ1 (πgj ).Лемма БернсайдаДействие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЛемма БернсайдаДоказательство.По предыдущей теореме |Gi | =nX|G ||Oi | .|Gi | = |G |i=1ПоэтомуnX1.|Oi |i=1Если для элементов i, k ∈ N верно i ∼G k, то Oi = Ok , откуда|Oi | = |Ok |.
ПустьOa1 , . . . , OaN(G )все различные орбиты по группе G .ТогдаN(G )N(G )nX 1 XX 1X1=1=· |Oal | = N(G ).|Oi ||Oal ||Oal |i=1l=1i∼G all=1Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЛемма БернсайдаДоказательство.Следовательно,|G | · N(G ) =mXλ1 (πgj ).j=1Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаПример: число орбит при вращении треугольникаПример. Найдем число орбит элементов множестваN = {1, 2, 3} по тождественному действию группы H вращенийправильного треугольника в плоскости.
Сколько их?Напомним, чтоH = {π1 = e = (1)(2)(3), π2 = (123), π3 = (132)}.Тогдаλ1 (π1 ) = 3, λ1 (π2 ) = λ1 (π3 ) = 0.Значит,31 X1N(H) =λ1 (πj ) = (3 + 0 + 0) = 1.|H|3j=1Все элементы множества N из одной орбиты, т.е.перестановками группы H каждый элемент множества Nможно перевести в любой другой элемент этого множества.Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЗадачи для самостоятельного решения1. Найти группу перестановок вершин правильногошестиугольника при его вращениях в плоскости.
Найти всеподгруппы этой группы. Найти орбиту вершины 1 притождественном действии в группе и в каждой из подгрупп. Полемме Бернсайда подсчитать число орбит вершин по каждойиз подгрупп.2. По лемме Бернсайда подсчитать число орбит вершинправильного восьмиугольника при его вращениях в плоскостина угол, кратный π2 .Действие группыОрбита элементаСтабилизатор элементаЛемма БернсайдаЛитература к лекции1. Чашкин А.В. Лекции по дискретной математике. М.: Изд-вомеханико-математического факультета МГУ, 2007. С.
53–57.Действие группыОрбита элементаСтабилизатор элементаКонец лекцииЛемма Бернсайда.