Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 15
Текст из файла (страница 15)
Теорема Лагранжа. Если Н вЂ” подгруппа группы6, то се порядок является делителем порядка 6. Доказательство. Пусть е, а,, а,, ..., а„,— все перестановки, содержащиеся в группе 6, ()о=в, (3ь ... ..., ()„,— все перестановки из Н (т. е. гп~п). Если Н=6, то утверждение теоремы справедливо, поэтому предположим, что НчьС (Н вЂ” собственная подгруппа 6). В силу этого предположения существует перестановка у, ~ 6, такая, что у, ф Н. Рассмотрим ряд перестановок ()О'у1=у1 ()1'Уг р -г'71 (1) Все перестановки этого ряда различны: если бы для каких-то 1, 1 имело место равенство р; ° у1 =(3~ ° у„то, умножив его правую и левую части на у,', мы получили бы равенство р;=~л Кроме того, ни одна из них не содер. жится в подгруппе Н: если бы для какого.то номера 1 имело место включение р; ° у, ен Н, то это означало бы, что р; ° уг=~~ для какого-то /.
Из этого равенства имеем у,=()~' ° ~~, а так как Н вЂ” группа перестановок, то у, ен Н, что противоречит выбору этой перестановки. Если перестановками группы Н и ряда (1) исчерпаны все перестановки из 6, то ~6~=2(Н(, и все доказано. В противном случае найдется такая перестановка у, ен6, что у,~Н и у, не содержится в ряде (1). Определим для нее ряд перестановок Аналогично проверяется, что а) все перестановки ряда (2) различны; б) они не содержатся в Н; в) ни одна из них не встречается среди перестановок ряда (1).
Если перестановками из подгруппы Н и рядов (1) и (2) исчерпываются все элементы группы 6, то (6(=3(Н~ н все доказано. В противном случае продолжаем процесс выбора перестановок у; и пострс(ения рядов вида (1) и (2) дальше. Так как группа 6 конечная, то на каком-то, например на Й-м, шаге все перестановки из 6 будут исчерпаны. Иными словами, все их можно расположить таким 79 образом: рз рз ° ° () -х б»71 1з71 " 1- 71, () уз ~з 7» " ~ — 7, () '7»- анз'7»- " () -з уа-ы ре (зе * 7» ()е'7» (эе 7»-з при этом все перестановки в каждой из строк различны и любые 2 строки не имеют общих элементов. Поскольку общее число элементов в (3) равно и (порядок группы 6), а число элементов в каждой строке равно т (порядок группы Н), то имеем равенство п =ту, т.
е. т является делителем и, и теорема доказана. Число й называют индексом подгруппы Н в группе 6 и обозначают [6: Н "1 Из доказательства теоремы Лагранжа мы получаем, что имеет место равенство Упражнения 1. Множества перестановок, сто«шве в рядах таблнцы (3), называютсн пРаемми (так как тз Уинонснетсн спРава) классами смежности, а таблицу (3) естественно назвать таблицей разлажениа груаам 0 на араеьм класси смежности ло паоерулае и.
Вполне аналогично можно построить таблнцу разложенан группы 6 аа »сема классы смежности по подгруппе Н. Построить таблицы рвэложенна группы $з на классы смежности как правые, так н левые по подгруппе Л = (е, (1, 2)); по подгруппе В (е, (1, 2, 3), (1; 3, 2))ь" ' но Так как порядок циклической подгруппы, порожденной перестановкой а ев 6, совпадает с порядком перестановки а, то из теоремы Лагранжа получаем, что порядок тобой перестановки из 6 — делитель 16(. Теорема Лагранжа позволяет также существенно упростить решение задачи описания всех подрупп данной . группы.
Например, если порядок группы 6 есть простое число, то в 6 нет нетривиальных собственных подгрупп (согласно теореме Лагранжа). Собственные подгруппы из Яа могут состоять из двух и трех перестановок (делители числа 3! =6), поэтому непосредственную проверку, о которой идет речь в задаче из 3 8, можно опустить. А ведь эта проверка длинная, так как есть Сз'+Сз'=21 подмножество из 5», состоящее нз 4 или 5 элементов. Даже на этих двух примерах видно, .
насколько существенным может быть применение теоремы Лагранжа. 2. Доказать, что вращения правильного шестиугольника 'вокруг центра на углы, кратные и/3, образуют подгруппу в группе всех его снмметрнй. Составить таблицы разложения на вравые н левые классы смежности группы снммегрнй шестнугольннка по подгруппе всех вра. щеннй. Обобщить это на случай произвольного п-угольннка, 3. Если Н вЂ подгруп индекса 2 в группе О, то правые н левые классы смежности по этой подгруппе совпадают. Докажите. 4.
Пусть йь йа, ..., Ач †решен (й! †натуральн) уравнения х»+х»+...+ха т (ш †произвольн натуральное). Тогда д,!. 2»!.... Аа! является дели- телем ш! Докажите, 5. Выпишите все числа, которые, согласно теореме Лагранжа, могут быть порядкамн элементов в группе Ры. Существуют лн в группе Р»» перестановки таких порядков? В. Тот же вопрос для группы 5ю ф 12. ОРБИТЫ ГРУППЫ ПЕРЕСТАНОВОК. ЛЕММА БЕРНСАЙДА Рассматривая группы перестановок, мы ограничивались изучением их действия на элементы некоторого множества. Но ведь если такое действие определено, то перестановки поэлементно чпередвигают» и подмножества данного множества. При изучении свойств действий на подмножествах первым шагом является, естественно, описание тех подмножеств, которые данная группа перестановок в целом не передвигает.
В связи с этим возникает понятие орбиты группы перестановок на данном множестве. Пусть 6 — группа перестановок на множестве М= =(1, 2; ..., и). Подмножество 0 с: М называется орбитой группы 6, если а) (а)ага О для любого ия6 и любого а я 0; т. е. действие перестановок из О на элементы О не выводит за пределы 0; б) любые два элемента из 0 можно перевести друг в друга некоторой перестановкой из 6. Всякая группа перестановок 6 = (е =ао, ао ...,аа-х) имеет орбиты. Для доказательства выберем произвольный элемент а ен М и рассмотрим множество 0(а) = (а=(а)а„(а)аь ... ..., (а)а» х).
Оно будет орбитой группы 6, так как а) если а! ен О и Ь = (а)осу ее О (а), то (Ь)а! = (а) (сху.а!) ен ни 0(а), так как ау са! енб (ведь 6 — группа); б) если Ь=(а)сг! и с=(а)ау — произвольные элементы из О (а), то Ь = (а)се! = (а) (е а) = (а) (а! * !2, '. а!) = (с)а~ '. а;; и при этом сс!' осу е26; так как 6.— группа. а! Оказывается, что орбитами подобного вида иечерпываютея все типы орбит. Более точно, если 0 — орбита группы 6 и аен0, то 0=0(а). Справедливость этого утверждения вытекает непосредственно из определения орбиты группы. Ясно, что любые две орбиты 0(а) и 0(Ь) либо совпадают (если Ь ен 0 (а)), либо ие пересекаются (если Ь ~ 0 (а)). Отсюда (почти так же как и при доказательстве теоремы Лагранжа) следует, что мноаеество М распадаепия вебьединение неперееекаюи(ахея псдмножеапв — орбит группы 6.
В частности, может случиться, что единственной орбитой группы 6 будет само множество М, как это имеет место для групп Р„(проверьте!). Группы с таким свойством называются транзитивными. Таким образом, группа перестановок 6 на множестве М транзитивна, если любой элемент а АМ может быть получен из любого другого элемента Ь ~М под действием подходящим спбсобом выбранной перестановки а~6: а=(Ь)а. Все другие группы перестановок называются интранзитивными. В связи с разбиением множества М на орбиты группы перестановок 6 возникают следующие два вопроса: 1) Сколько орбит имеет группа 6 на множестве М? 2) Какова длина каждой из этих орбит, т.
е. из скольких элементов они состоят? Сформулируем вначале утверждение, позволяющее выяснить ответ на второй вопрос. Оно формулируется с использованием понятия стабилизатора элемента из М. А именно: для любого элемента а~М можно рассмотреть множество 6, всех перестановок из 6, для которых точка а является неподвижной. Это множество, очевидно, является группой (еще один способ образования групп перестановок!), которая и называется стабилизатором точки а. Теорема.
Длина орбиты 0(а) равна индексу стабилизатора 6, в группе 6, т. е. )0(а) ! = (6): (6,). Доказательство. Пусть 6=(а,=е, аь ", ае-~) а=Во=е, ~ь, () 1). Для подсчета различных элементов в последовательности а, (а)а„..., (а)сс~ 1 удобно особым образом расположить в ряд элементы группы 6. Для этого вспомним примененное при доказательстве теоремы Лагранжа разложение группы 6 в правые классы смежности по подгруппе 6,. Существуют перестановки уе= е у1 ", ь г из группы 6, такие, что все переста- 82 вовки ряда.
ао=ро уо=е, ад=()д уо, "., а, д=р.-д уо* а,=()о уь а,+д=рд уд, ..., аь-д=(1 д уь (1) й<д-дм=ро уьь аа-Ио+д=рд'уд-ь ° ° °, аь-д=~~д'уьд попарно различны и исчерпывают всю группу О. Для любого д =О, ..., 1 — 1 применение з перестановок адь аь~„..., а~;+,~ „образующих д-ю строку таблицы (1), к элементу а дает один и тот же элемент (а)уь Все 1 элементов (а) уд попарно различны. Действительно, еслибы (а)Уд = (а)Уу дла иекотоРых д, 1, то а = (а)У~.У,.', т. е. пеРестановка уу уд' ен О,. Но это возможно только тогда, когда у; и уд содержатся в одном правом классе смежности группы О по подгруппе О„чего быть не может.
Таким образом, длина орбиты 0(а) равна 1, т. е, числу строк в таблице (1). А это число в $ 10 и было названо индексом подгруппы в группе. Проиллюстрируем понятие орбиты группы и доказанную теорему на примере 4 из 9 9, где рассматривалась группа перестановок О = (е, а, (1 у), действующая на множестве М=(1, 2, 3, 4, 5, 6). Имеем (1)е=1, (1)а=5, (1)(1 =2, (1)у=4, т. е. 0(1) = (1, 2, 4, 5). Выбирая какой- нибудь элемент из М, не принадлежащий 0(Ц, скажем 6, получим (6)е=-б, (6)а=б, (6)(А=3, (6)у=3, т. е, 0(6)=(3, 6). Таким образом, группа перестановок О на множестве М имеет две орбиты: 0(1) = (1, 2„4, 5), 0(6) = (3, 6), и поэтому является ннтранзнтивной.
Стабилизатор О, точки 1 из 0(1) состоит из одной перестановки е. Поэтому [О: Од1=4= ~ 0(1) ~. Стабилизатор О, точки 6 из 0(6) состоит из перестановок е и а. Разложение группы О на правые классы смежности по подгруппе Оо — — (е, а) имеет вид е, а, е ° ()=(), а ()=у. Поэтому ~О: Оо] = 2 = ( 0(6) ). Докажем теперь утверждение, чисто исторически называемое леммой Берисайда по имени английского математика-алгебраиста В. Бернсайда (1852 — 1927), который, по-вндимому, первым опубликовал его доказательство в своей книге по теории конечных групп (1911 г.). Это простое утверждение является основой теории перечисления, разработанной Д, Пойа и рядом других математи- аз ков,— теории, находящей широкие применения в кибернетике, технике, органической химии, биологии и т.
д. Пусть у (а) — число неподвижных точек перестановки а, Г (6) — число орбит группы перестановок 6 = (<х, = и, а„..., а,-,), действующей на множестве М = (1, 2,..., п). Лемма Берн сайда. Для любой еруппы перестановок имеет место равенство ((6)= —,' ~' у(а). аао До к аз а тел ь ство. Рассмотрим отношение «перестановка а сохраняет неподвии ным элемент т» между перестановками группы 6 и элементами множества М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
