Лемма Бернсайда о числе орбит группы подстановок

Определение: Подстановка р:Х→Х={1,2,…,n} сохраняет элемент а (а есть неподвижная точка подстановки р), если р(а)=а.

Стабилизатор элемента а из Х группы G есть множество Ga = {p∈G: p(a) = a} всех подстановок, сохраняющих элемент а.

Замечание: Стабилизатор Ga есть группа.

Утверждение: Длина орбиты А(а) равна индексу стабилизатора G(a) в группе G, то есть мощность |A(a)|=|G|/|Ga|.
Без доказательства.

Лемма (Бернсайда): Если 1) X={1,2,…,n}; 2) G= {p0 =e, p1, …, pr-1} есть группа подстановок на множестве Х; 3) χ(p) есть число фиксированных точек подстановки р, тогда число орбит группы подстановок G равно f(G) = |G|-1p∈G χ(p).

Доказательство: Изобразим отношение «m есть фиксированный элемент подстановки р».

На каждой вертикали pi звездочкой отмечены неподвижные точки подстановки pi. Их число равно χ(pi). При вычислении по вертикалям число звезд (неподвижных точек) равно: χ(p0) + χ(p1) + … + χ(pr-1) = ∑χp∈G(pi) . На каждой горизонтали m отмечены все подстановки, сохраняющие элемент m. Эти подстановки образуют стабилизатор Gm, который есть группа, и по предыдущему утверждению |A(m)| = |G|/|Gm|, откуда |Gm|=|G|/|A(m)|. При вычислении по горизонтали число звезд на диаграмме равно |G1| + |G2| + … + |Gn| = ∑m ∈X|Gm|. Множество Х разбивается в объединение попарно непересекающихся орбит. X = O1 ∪ O2 ∪ … ∪ Ot, где t=f(G) есть число орбит. Перегруппируем слагаемые предыдущей суммы относительно элементов орбит и получим:

m∈O|Gm| = ∑m∈O1|Gm| + … + ∑m∈Ot|Gm|.

Если m∈O включение верно для орбиты O, то O=А(m), тогда каждое слагаемое предыдущей суммы:

m∈O|Gm| = ∑m∈O|G|/|A(m)| = ∑m∈X|G|/|O| = |G|/|O|∑m∈X1 = |G|/|O| |O| = |G|

Тогда вся сумма: ∑m∈O|Gm| = |G| + … + |G| = t|G| = f(G)|G|.

Число звездочек, вычисленных по горизонтали и вертикали, совпадает. Следовательно, сумма ∑χp∈G = f(G)|G|, откуда число орбит группы G: f(G) = |G|-1 ∑χp∈G. Лемма доказана.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru