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

Материал из synset
Перейти к: навигация, поиск
Примеры и определения << Оглавление (Последняя версия в: Глава 5) >> Еще немного определений

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle } } \bulletНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle Рассмотрим ещё один важный класс групп. Пусть имеется } nНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle упорядоченных объектов, пронумерованных цифрами от 1 до } nНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle . Эти объекты можно переставить местами } n!=2\cdot 3\cdot...\cdot nНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle способами (на первое место поставим один их } nНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle предметов; для ''каждой'' из этих } nНевозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle возможностей, на второе место поставим один из } (n-1)Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle оставшихся предметов, и т.д.). Например, для трёх объектов возможно } 6$ перестановок:

Невозможно разобрать выражение (неизвестная функция «\underrightarrow»): {\displaystyle e=(1\,2\,3),\;\;\;a=(\underline{2}\,\underline{1}\,3),\;\;\;b=(1\,\underline{3}\,\underline{2}),\;\;\;c=(\underline{3}\,2\,\underline{1}),\;\;\;d=(\underrightarrow{3\,1\,2}),\;\;\;f=(\underleftarrow{2\,3\,1}).}

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

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

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{r|ccc|cc|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{c}& \multicolumn{1}{c}{d}& \multicolumn{1}{c}{f}\\ \cline{2-6} a & \bullet & f & d & c & b \\ b & d & \bullet & f & a & c \\ \mathbf{S_3}:\;\;\; c & f & d & \bullet & b & a \\ \cline{2-6} d & b & c & a & f & \bullet \\ f & c & a & b & \bullet & d \\ \cline{2-6} \end{array} \;\;\;\;\;\;\;}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

} \parbox{4cm}{

Cicles.png

} \parbox{5cm}{

} \parbox{3cm}{

Cicles2.png
}

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

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

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

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

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

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

Невозможно разобрать выражение (неизвестная функция «\multicolumn»): {\displaystyle \begin{array}{rrr|c|cc|} \multicolumn{2}{r}{1} & \multicolumn{1}{r}{e} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{c}\\ \cline{4-6} &2 &a & \bullet & c &b\\ \cline{4-6} \mathbf{D_2}:\;&3 &b & c & \bullet &a\\ &4 &c & b & a & \bullet \\ \cline{4-6} \end{array} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{l} p_e=(1\;2\;3\;4)\\ p_a=(2\;1\;4\;3)\\ p_b=(3\;4\;1\;2)\\ p_c=(4\;3\;2\;1)\\ \end{array}}

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

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

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

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

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

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



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

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