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

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

---

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

Каждой перестановке мы присвоили имя "$\textstyle a$-$\textstyle f$", и будем её считать операцией, переводящей первоначальный порядок $\textstyle e=(1\;2\;3)$ в некоторый другой. Перестановки $\textstyle \{a,\;b,\;c\}$ задействуют только пары элементов, оставляя третий неизменным. Оставшиеся две являются циклическим сдвигом вправо $\textstyle \{d\}$ и влево $\textstyle \{f\}$.

Композиция двух последовательных перестановок, снова является перестановкой. Представим все возможные композиции перестановок трёх объектов при помощи таблицы умножения. Ясно, что если мы переставим первый и второй объект, а затем повторим эту операцию, то получится исходный порядок. Поэтому $\textstyle a^{2}=b^{2}=c^{2}=e$. Сдвинув исходный порядок вправо ($\textstyle d$), а затем повторив этот сдвиг мы получим $\textstyle f=d^{2}$. Аналогично рассуждая дальше, сформируем таблицу умножения:

Эта группа называется группой перестановок или симметрической группой и обозначается как $\textstyle \mathbf {S_{3}}$. Очевидно, что она не абелева. Например: $\textstyle (a\,b=f)\neq (b\,a=d)$. Аналогично строится группа перестановок $\textstyle n$ объектов $\textstyle \mathbf {S_{n}}$. Она имеет порядок $\textstyle n!$ и при $\textstyle n>2$ также является не абелевой.

Обратим внимание на блок 2x2 в правом нижнем углу состоящий из элементов $\textstyle f$ и $\textstyle d$. Это подгруппа $\textstyle \mathbf {C_{3}} \subset \mathbf {S_{3}}$. Понятно, что циклические сдвиги вправо или влево вместе с единичным порядком являются замкнутыми операциями и образуют группу $\textstyle \mathbf {C_{3}} =\{e,d,f\}$. Она является инвариантной (проверьте).

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

$\textstyle \bullet$ Перестановки можно считать всюду определёнными обратимыми целочисленными функциями $\textstyle x(i)$, где $\textstyle i$ — позиция элемента, а $\textstyle x(i)$ — его номер. Результат композиции двух последовательных перестановок $\textstyle z=x\cdot y$ равен:

$z(i)=x{\bigl (}y(i){\bigr )}.$

Обратная $\textstyle {\bar {x}}$ к $\textstyle x$ перестановка удовлетворяет уравнению:

${\bar {x}}{\bigl (}x(i){\bigr )}={x}{\bigl (}{\bar {x}}(i){\bigr )}=i.$

Соответственно, единичная перестановка — это "'линейная функция" $\textstyle e(i)=i$.

$\textstyle \bullet$ При вычислении результата композиции двух перестановок можно поступать следующим образом. Рассмотрим, например $\textstyle a\cdot f=b$. Запишем первую перестановку, поставив у номера объекта индекс равный его текущему положению в списке:

$\overbrace {(2_{1}\;1_{2}\;3_{3})} ^{a}\cdot \overbrace {(2\;3\;1)} ^{f}=\overbrace {(1\;3\;2)} ^{b},$

На первом месте в $\textstyle f$ стоит 2. Это означает, что $\textstyle f$ применённая к уже сделанной $\textstyle a$, должна на первое место поставить второй элемент $\textstyle a$, т.е. "1". Аналогично третий элемент ("3") идёт на второе место, и первый ("2") на третье. Таким образом для записи композиции $\textstyle x\cdot y$ необходимо взять второй список, и вместо его цифр $\textstyle y=(i,j,k,...)$ записать элементы первого списка с индексами $\textstyle i,j,k,...$:

$(...\,x_{i}\,...y_{j}...z_{k}...)\cdot (i\,\,j\,k\,...)=(x\,y\,z\,....).$

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

$(8_{1}\;2_{2}\;1_{3}\;4_{4}\;5_{5}\;6_{6}\;7_{7}\;3_{8}\;9_{9})\cdot (1\;7\;3\;4\;5\;2\;9\;8\;6)=(8\;7\;1\;4\;5\;2\;9\;3\;6).$

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

$(...\,x_{i}\,...y_{j}...z_{k}...)^{-1}=(...\,i_{x}\,...j_{y}...k_{z}...).$

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

$d^{-1}=(3_{1}\;1_{2}\;2_{3})^{-1}=(1_{3}\;2_{1}\;3_{2})=(2\;3\;1)=f.$

В результате: $\textstyle d\cdot d^{-1}=(3_{1}\;1_{2}\;2_{3})\;(2\;3\;1)=(1\;2\;3)=e$.

$\textstyle \bullet$ Любую перестановку можно характеризовать по числу одновременно задействованных в ней объектов. Так, в $\textstyle \mathbf {S_{3}}$ элемент "$\textstyle a=(2\;1\;3)$" переставляет местами первые два объекта, а положение третьего оставляет неизменным. Замкнутые группы переставляемых объектов называются циклами. В перестановке может быть несколько циклов:

$p=(8_{1}\;7_{2}\;1_{3}\;4_{4}\;5_{5}\;2_{6}\;9_{7}\;3_{8}\;6_{9})=[8\;3\;1]\cdot [7\;9\;6\;2]$

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

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

$[8\;3\;1]=(8_{1}\;3_{8}\;1_{3})$

} \parbox{4cm}{

} \parbox{5cm}{

$\;\;\;\;[7\;9\;6\;2]=(7_{2}\;9_{7}\;6_{9}\;2_{6})$

} \parbox{3cm}{

}

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

Если два цикла, например $\textstyle [8\;3\;1]$ и $\textstyle [7\;9\;6\;2]$ не имеют пересекающихся элементов, то произведение содержащих им перестановок можно выполнять в любом порядке:

${\begin{array}{l}(\mathbf {8} _{1}\;2_{2}\;\mathbf {1} _{3}\;4_{4}\;5_{5}\;6_{6}\;7_{7}\;\mathbf {3} _{8}\;9_{9})\cdot (1\;\mathbf {7} \;3\;4\;5\;\mathbf {2} \;\mathbf {9} \;8\;\mathbf {6} )=(8\;7\;1\;4\;5\;2\;9\;3\;6),\\(1_{1}\;\mathbf {7} _{2}\;3_{3}\;4_{4}\;5_{5}\;\mathbf {2} _{6}\;\mathbf {9} _{7}\;8_{8}\;\mathbf {6} _{9})\cdot (\mathbf {8} \;2\;\mathbf {1} \;4\;5\;6\;7\;\mathbf {3} \;9)=(8\;7\;1\;4\;5\;2\;9\;3\;6).\\\end{array}}$

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

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

${\begin{array}{l}\;[8\;3\;1]^{2}\;=\;(8_{1}\;3_{8}\;1_{3})\,(8_{1}\;3_{8}\;1_{3})=(3_{1}\;1_{8}\;8_{3})\\\;[8\;3\;1]^{3}\;=\;(3_{1}\;1_{8}\;8_{3})\,(8_{1}\;3_{8}\;1_{3})=(1_{1}\;8_{8}\;3_{3})=e\end{array}}$

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

$\textstyle \bullet$ Изоморфизм групп иногда приобретает очень любопытные формы. Пронумеруем элементы $\textstyle \{e,a,b,c\}$ группы $\textstyle \mathbf {D_{2}}$ цифрами от 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}}

В каждой строке, включая её заголовок, элемент встречается один и только один раз. Поэтому строки таблицы умножения (вместе с единичной $\textstyle p_{e}$) являются перестановками четырех элементов. Так как в этом случае возможно $\textstyle 24$ перестановки, то $\textstyle p_{e},p_{a},p_{b},p_{c}$ — лишь некоторое подмножество из группы $\textstyle \mathbf {S_{4}}$. Однако это подмножество перестановок замечательным образом оказывается группой с той же таблицей, что и у $\textstyle \mathbf {D_{2}}$! Например,

${\begin{array}{l}p_{a}\,p_{b}=(2_{1}\;1_{2}\;4_{3}\;3_{4})\,(3\;4\;1\;2)=(4\;3\;2\;1)=p_{c},\\p_{a}\,p_{a}=(2_{1}\;1_{2}\;4_{3}\;3_{4})\,(2\;1\;4\;3)=(1\;2\;3\;4)=p_{e}.\end{array}}$

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

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

Действительно, рассмотрим группу с $\textstyle n$ элементами $\textstyle \mathbf {G} =\{g_{1},...,g_{n}\}$. Каждому элементу $\textstyle g_{i}$ поставим в соответствие перестановку исходного порядка (строка с заголовком $\textstyle g_{i}$):

$p_{i}=(g_{i}\,g_{1},\;g_{i}\,g_{2},\;...,g_{i}\,g_{n}).$

Единичной (исходной) перестановкой будем считать упорядоченные по индексу элементы $\textstyle p_{e}=(g_{1},\;g_{2},\;,...,\;g_{n})$. Рассмотрим композицию двух перестановок $\textstyle p_{i}$ и $\textstyle p_{j}$, созданных при помощи $\textstyle g_{i}$ и $\textstyle g_{j}$:

$p_{i}\,p_{j}=(g_{i}\,g_{1},\;...,g_{i}\,g_{n})\,(g_{j}\,g_{1},\;...,g_{j}\,g_{n})=(g_{i}\,g_{j}\,g_{1},\;...,g_{i}\,g_{j}\,g_{n})=p_{k}.$

Действительно, пусть $\textstyle g_{j}\,g_{1}=g_{s}$. При умножении перестановок, мы должны на первое место результата поставить элемент из списка $\textstyle p_{i}$ под номером $\textstyle s$. В силу упорядоченности в $\textstyle p_{i}$ по второму индексу — это $\textstyle g_{i}\,g_{s}$ или $\textstyle g_{i}\,g_{j}\,g_{1}$. Аналогично для остальных элементов списка. Следовательно, перестановка $\textstyle p_{k}=p_{i}\,p_{j}$ получается при помощи $\textstyle g_{k}=g_{i}\,g_{j}$ и таблица умножения перестановок $\textstyle p_{i}$ изоморфна группе $\textstyle \mathbf {G}$. $\textstyle \square$

---

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

---

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