1611141236-738b6049e710338c8c4dd43e7bd2b717 (824981), страница 11
Текст из файла (страница 11)
Поскольку природа его элементов для нас несущественна, удобно считать, что й = = (1,2,..., и). Элементы множества 5„= о(й) всех взаимно однозначных преобразований й — > й, обычно обозначаемые строчными З 8. Перестпаноеки буквами греческого алфавита, называются переев»яновнами.
Лишь за единичным преобразованием е = еп сохранилась буква латинского алфавита. В развернутой и наглядной форме произвольную перестановку я: 2 + я(1), 1 = 1, 2,..., и, изображают в виде полностью указывая все образы: 1 2 ... и 1 Г Г, 11 12 »я где 1» = х(й), й = 1,..., и — переставленные символы 1, 2,..., и. Перестановки сг, т Е Я„перемножаются в соответствии с общим правилом композиции отображений: (ат) = а(т(1)). Например, для перестановок 2341 ' 4321 имеем 1 2 3 4 1 4 3 2 В то же время 4321 2341 3214 так что о г ф тп. Согласно результатам 2 5 умножение перестановок подчиняется следующим правилам. 1) Умножение ассоциативно, т.е. (а)1).~ = а(бч) для всех а, )3, у е Е ~и. й) Я„обладает единичным элементом е: яе = и = еи для всех и Е Я„.
ш) Для каждой перестановки я Е Я„существует обратная перестановкахя 1: из 1 = и 'х = е. Эти три свойства, дополненные общими принципами, на которых мы не хотим сейчас останавливаться (см. гл. 4), дают основанне говорить о группе Я„. Точнее, множество Я„, рассматриваемое вместе с естественной операцией умножения его элементов (композицией перестановок), называется снммешрнческой группой сн2ененн п Гл.
1. Исптока алгебры (иначе, симметпрической группой на и символы или па и тпочках). Для нас пока это всего лишь удобное терминологическое соглашение, смещающее акценты с множества Я„как такового на мультипликативные свойства перестановок, т.е. на то, что может быть выявлено при композиции элементов из Я„. Симметрическая группа Я„лежала у истоков общей теории групп и теории Галуа более 170 лет тому назад, и можно только поражаться связанному с ней обилию математических идей. Замечание.
Иногда элементы группы Я„называют подстпановкамв, используя термин перестановка в качестве синонима расположения чисел 1, 2,..., п в каком-то фиксированном порядке. Так как между такими упрядочениями чисел и элементами группы Я„ имеется взаимно однозначное соответствие, а слово "перестановка" ассоциируется в сознании скорее с действием, чем с застывшим упорядочением, то подстановки у нас из употребления исключены. Впрочем, ниже мы будем говорить, например, о подстановке числа в многочлен, но это служит лишь дополнительным аргументом в пользу указанного терминологического соглашения.
Ксли нужны еще какие-то доводы, то их можно найти по меньшей мере: а) в научной литературе; б) в учебнике П.С. Александрова "Лекции по аналитической геометрии" (Наука, 1968, с. 767). Найдем порядок ~Я„~ группы Я„. Символ 1 можно подходящей перестановкой о перевести в любой другой символ а(1), для чего существует в точности и различных возможностей. Но, зафиксировав о(1), мы имеем право брать в качестве о(2) лишь один из оставшихся и — 1 символов (всего различных пар о(1), о(2) имеется (и — 1) + (и — 1) + ...
+ (п — 1) = и(п — 1)), в качестве о(3)— соответственно и — 2 символов и т.д. Всего возможностей выбора о(1), о(2),..., о(и), а стало быть, н всех различных перестановок будет и(п — 1)... 2. 1 = и!. Таким образом, Сап1 Я„= )Я„! = и!. 2. Цикловая структура перестановки. Разложим теперь перестановки из Я„в произведения более простых перестановок.
Идею разложения поясним схематически (рис. 13) на примере указанных выше перестановок о, т Е Ял. т= 4 1 3 2 — з 4 Рвс. 13 Перестановка о, кратко записываемая в виде а = (1 2 3 4), или, З 8. Перестановки 53 что то же самое, в виде о = (2 3 4 1) ее (3 4 1 2) = (4 1 2 3), называется наивом длины 4, а перестановка т = (1 4)(2 3) — произведением двух неэавнснммя (непересекагоганэсл) циклов (1 4) и (2 3) длины 2. Заметим, что оэ = (1 3)(2 4), о» = (оэ)э = е, тэ = е. Пусть теперь к — произвольная перестановка из Я„. Ее степень к' определяется по индукции (см.
доказательство теоремы 3 3 5): з'= е, я(т' г), если з>0, если в=О, — ((.— )(- — >), .<о. При таком определении, очевидно, те я» — яе гг — я» те \ Ф (последовательное приписывание я или я г при з и г одинакового знака и замена ггл ',я гя на е при з и г разных знаков). Так как ~Й~ < со, то на самом деле для каждой перестановки я 6 Я„найдется однозначно определенное натуральное число д = д(я) такое, что все различные степени содержатся во множестве (я) = (е,я,...,яе ') и яе = е. Это число о называется еще порядком нересшановкн я. Так, рассмотренные выше перестановки и и т имеют соответственно порядки 4 и 2.
Две точки г,у Е Й назовем гг-эквиваленгнныма, если у = гг'(1) для некоторого з 6 Е. Так как о( ) „в( ) . „-в(у) ° е( ) й л(.) =ь /с = х"г г(1), то, очевидно, мы имеем дело с рефлексивным, симметричным и транзитивным отношением на Й (см.
п. 2 э 6). В соответствии с общим свойством отношений эквивалентности получаем разбиение Й=Й,и...байр (1) множества Й на попарно непересекающиеся классы Йг,..., Йр, которые принято называть еще я-орбнтламн. Название это вполне обосновано. Каждая точка 1 Е Й принадлежит в точности одной орбите, и если 1 Е Й», то Й» состоит из образов точки 1 при действии степеней элемента гг: г,я(г),ял(г),...,яг' '(1). Здесь 1» = )Й»| — дланя я-орбипгм Й». Очевидно, что 1» < о = Сзп1(я), Гл. 1. Иегпоки елеебрм причем 1« — наименьшее число, обладающее этим свойством. Поло- жив Я« = (ггг(1) ...
гг' (1)) = (.) «(.) мы придем как раз к перестановке, называемой ииклом длины 1«. Вопрос вкуса и удобства — писать (1 2 3 ... 1) или (1, 2, 3,...,1). Цикл я«оставляет на месте все точки из множества й 1 й«, а я()) = я«(г) для любой точки у 6 Йю Это свойство дает нам основание называть гг„яг, л ~ Ф, независимыми или иепересекаюигимисл циклами. Так как я'"(1) = 1 для 1 6 Й«, то гг«" = е. Итак, с разбиением (1) ассоциируется разложение перестановки и в произведение Я1Я2 Яр~ (2) где все циклы перестановочны: я = ягир...
1Гр — — Яг, Ггг,... 1Г1,. Можно считать, например, что 11 ) ))з »... 1рг > )р,+1 =... = (р = 1. Если цикл я« = (1) имеет длину 1, то он действует кзк единичная перестановка. Естественно такие циклы в произведении (2) опускать: я =лги«...я, («>1, 1<й<пг. (3) Например, перестановку (12345678( 1,23451768/ мы запишем в виде гг = (1 2 3 4 5)(6 7)(8) = (1 2 3 4 5)(6 7). (4) Некоторую неловкость вызывает то обстоятельство, что (1 2 3 4 5)(6 7) можно интепретировать как перестановку из Я„при любом п > 7, однако при фиксированном п никакой неоднозначности нет.
Более точно, пусть наряду с разложением (3) мы имеем еще одно разложение я = ага«... а„в произведение независимых циклов, и пусты — символ, не остающийся на месте при действии я. Тогда и,(1) ~ 1, аг(1) ф 1 для одного (и только одного) из циклов хг,..., х и одного из аг,...,а„. Имеем яе(1) = гг(1) = аг(1). Если мы уже знаем, что и, (1) = л (1) = а, (1), (5) то, применяя к этим равенствам перестановку гг и используя перестановочность гг си~ и с аг«, получаем ««+1(,) «(,) откуда гг«гг(1) = гг«+' (1) = а,"и(1) и, наконец, , «+1( ) «+1(;) „«-1-1(.) 8 8. перестановки 55 Значит, равенства (5) справедливы при любом й = О, 1, 2,...
Но цикл однозначно определяется действием его степеней на любой символ, который не остается на месте. Следовательно, к, = оь Далее применяется индукция по т или г. Итак, нами доказана Теорема 1. Каждая перестановка к ~ е в Я„лвляетсл произведением независимых ииклов длины > 2. Это разложение в произведение определено однозначно с точностью до порядка следования циклов.
Обратим внимание на циклы длины 2. Определение. Цикл длины 2 называется транспозиииеб. Любая транспозипня имеет вид т = (гу) и оставляет на месте все символы, отличные от г, 1. Из теоремы 1 вытекает Следствие. Каждая перестановка к Е Я„является произведением транспозииии. Доказательство. В самом деле, в силу теоремы 1 достаточно записать в виде произведения транспозиций каждый из циклов.
Но зто можно сделать, например, так: (1 2 ... 1 — 1 1) = (1 1)(1 1 — 1) ...(1 3)(1 2). П Формулировки теоремы 1 и ее следствия нуждаются в пояснении. Как следует из определения цикла о = (гг 1г гг ... й г ц), г1 ' ~ гг~ гг ~ ~ гг ° ° ° гг-1 '+ й г! ' г ц и У' Е й'1(гыгг,...,ц мй), и потому ничто не изменится, если мы запишем о = (гг гг ... ц гг), т.е.
произведем циклический сдвиг номеров, входящих в о. Таким образом, утверждение единственности в теореме 1 носит по существу абсолютный характер. С другой стороны, в следствии ни о какой единственности записи перестановки через транспозиции не может быть и речи. Скажем, о = (гггггз ° ц-г ц) = (гг й)(ггц' г)... (гг ге)(гг гг), о = (ггге ц-г ц гг) = (1г гг)(гг ц)(гг и-г) ((г(з) Эти две записи одной и той же перестановки о содержат по одинаковому числу 1 — 1 совершенно разных транспознций (лишь (1г И) = = (гг 1г)). Более того, транспозиции, вообще говоря, не перестановочны, а их число не является инвариантом перестановки. Например, в Ял имеем (1 2 3) = (1 3)(1 2) = (2 3)(1 3) = (1 3)(2 4)(1 2)(1 4).
56 Гл. 1. Ионтеки алгебры 3. Знак перестановки. Справедлива следующая важная Теорема 2. Пустпь тт — перестпановка иэ Я„, (6) х = тттг... т» — произвольное разложение х в произведение тпранспозииий. Тогда число е, = (-1)», (7) называемое знаком х (иначе: сигнатурой или четносптью), полностаью определяетасл пересптановкой х и не заеиситп отп способа разложения (6), тае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
