Группа перестановок

Материал из synset
Версия от 15:58, 7 октября 2012; WikiSysop (обсуждение | вклад) (Защищена страница «Группа перестановок» ([edit=sysop] (бессрочно) [move=sysop] (бессрочно)))
Перейти к: навигация, поиск
Примеры и определения << Оглавление (Последняя версия в: Глава 5) >> Еще немного определений

Рассмотрим ещё один важный класс групп. Пусть имеется упорядоченных объектов, пронумерованных цифрами от 1 до \textstyle . Эти объекты можно переставить местами способами (на первое место поставим один их предметов; для каждой из этих возможностей, на второе место поставим один из оставшихся предметов, и т.д.). Например, для трёх объектов возможно 6 перестановок:

Sym tbl06.png

Каждой перестановке мы присвоили имя "-", и будем её считать операцией, переводящей первоначальный порядок в некоторый другой. Перестановки задействуют только пары элементов, оставляя третий неизменным. Оставшиеся две являются циклическим сдвигом вправо и влево .

Композиция двух последовательных перестановок, снова является перестановкой. Представим все возможные композиции перестановок трёх объектов при помощи таблицы умножения. Ясно, что если мы переставим первый и второй объект, а затем повторим эту операцию, то получится исходный порядок. Поэтому . Сдвинув исходный порядок вправо (), а затем повторив этот сдвиг мы получим . Аналогично рассуждая дальше, сформируем таблицу умножения:

Sym tbl07.png

Эта группа называется группой перестановок или симметрической группой и обозначается как . Очевидно, что она не абелева. Например: . Аналогично строится группа перестановок объектов . Она имеет порядок и при также является не абелевой.

Обратим внимание на блок 2x2 в правом нижнем углу состоящий из элементов и . Это подгруппа . Понятно, что циклические сдвиги вправо или влево вместе с единичным порядком являются замкнутыми операциями и образуют группу . Она является инвариантной (проверьте).

Группа изоморфна . Действительно, номера вершин треугольника на рисунке (стр.\,\pageref{group_D3_pic}), перечисляемые по часовой стрелки, начиная с верхней, являются перестановками трёх чисел (так, только при ).

Перестановки можно считать всюду определёнными обратимыми целочисленными функциями , где — позиция элемента, а — его номер. Результат композиции двух последовательных перестановок равен:

Обратная к перестановка удовлетворяет уравнению:

Соответственно, единичная перестановка — это "'линейная функция" .

При вычислении результата композиции двух перестановок можно поступать следующим образом. Рассмотрим, например . Запишем первую перестановку, поставив у номера объекта индекс равный его текущему положению в списке:

На первом месте в стоит 2. Это означает, что применённая к уже сделанной , должна на первое место поставить второй элемент , т.е. "1". Аналогично третий элемент ("3") идёт на второе место, и первый ("2") на третье. Таким образом для записи композиции необходимо взять второй список, и вместо его цифр записать элементы первого списка с индексами :

Например, выполним более длинное умножения двух перестановок девяти объектов:

Чтобы для данной перестановки записать обратную к ней, необходимо значение номера позиции элемента поставить на место номера этого элемента:

Для этого достаточно переставить местами число и его индекс, и после этого отсортировать по возрастанию индекса. Например

В результате: .

Любую перестановку можно характеризовать по числу одновременно задействованных в ней объектов. Так, в элемент "" переставляет местами первые два объекта, а положение третьего оставляет неизменным. Замкнутые группы переставляемых объектов называются циклами. В перестановке может быть несколько циклов:

Чтобы их найти, берём первый элемент, номер которого не совпадает с номером позиции (8) и идём на 8-е место. Там стоит 3. Поэтому идём на 3-е место. Там 1, и так как на первом месте стоит 8-ка с которой мы начали, цикл замыкается.

Цикл записывают опуская индексы, так как их всегда можно восстановить. Для этого необходимо в качестве индекса ставить номер предыдущего объекта в списке цикла, считая предыдущим для первого элемента — последний:

Cicles.png
Cicles2.png

При таком алгоритме записи циклов любые циклические перестановки , , являются одной и той же перестановкой. Смысл цикла состоит в круговой перестановке объектов — 8 идёт на третье место, 3 идёт на первое, а 1 на восьмое. Заметим, что мы различаем обозначения для цикла (квадратные скобки) и для перестановки (круглые).

Если два цикла, например и не имеют пересекающихся элементов, то произведение содержащих им перестановок можно выполнять в любом порядке:

Таким образом, выявление циклов позволяет разбить перестановку на композицию более простых перестановок.

Циклы состоящие из двух объектов называются транспозициями. Двойное применение транспозиции даёт единичную перестановку. Аналогично, тройное применение цикла длинной 3 даёт исходный порядок:

Понятно, что если цикл имеет длину , то его -я степень даст единичную перестановку (мы раз по кругу переставим объекты, вернувшись к исходному порядку).

Изоморфизм групп иногда приобретает очень любопытные формы. Пронумеруем элементы группы цифрами от 1 до 4. Представим каждую строку таблицы умножения в виде списка номеров элементов, поставив первым номер элемента в заголовке строки:

Sym tbl08.png

В каждой строке, включая её заголовок, элемент встречается один и только один раз. Поэтому строки таблицы умножения (вместе с единичной ) являются перестановками четырех элементов. Так как в этом случае возможно перестановки, то — лишь некоторое подмножество из группы . Однако это подмножество перестановок замечательным образом оказывается группой с той же таблицей, что и у ! Например,

Этот эффект возникает благодаря теореме Кэли:

\it Любая конечная группа G изоморфна некоторой подгруппе группы перестановок .

Действительно, рассмотрим группу с элементами . Каждому элементу поставим в соответствие перестановку исходного порядка (строка с заголовком ):

Единичной (исходной) перестановкой будем считать упорядоченные по индексу элементы . Рассмотрим композицию двух перестановок и , созданных при помощи и :

Действительно, пусть . При умножении перестановок, мы должны на первое место результата поставить элемент из списка под номером . В силу упорядоченности в по второму индексу — это или . Аналогично для остальных элементов списка. Следовательно, перестановка получается при помощи и таблица умножения перестановок изоморфна группе .



Примеры и определения << Оглавление (Последняя версия в: Глава 5) >> Еще немного определений

Релятивистский мир - лекции по теории относительности, гравитации и космологии