Циклическая перестановка

Тип (математической) перестановки без фиксированного элемента

В математика, и, в частности, в теории групп, циклическая перестановка (или цикл ) - это перестановка элементы некоторого набора X, который отображает элементы некоторого подмножества S из X друг в друга циклическим образом, фиксируя (то есть, отображая на себя) все другие элементы X. Если S имеет k элементов, цикл называется k-циклом . Циклы часто обозначаются списком их элементов, заключенным в круглые скобки, в том порядке, в котором они переставлены.

Например, если X = {1, 2, 3, 4}, перестановка (1, 3, 2, 4), которая отправляет 1 в 3, 3 в 2, 2 в 4 и 4 в 1 (так что S = X) - это 4-цикл, и перестановка (1, 3, 2), которая отправляет 1 в 3, 3 в 2, 2 в 1 и 4 в 4 (поэтому S = {1, 2, 3} и 4 - фиксированный элемент) - это 3-цикл. С другой стороны, перестановка, которая отправляет 1 в 3, 3 в 1, 2 в 4 и 4 в 2, не является циклической перестановкой, потому что она отдельно переставляет пары {1, 3} и {2, 4}.

Набор S называется орбитой цикла. Любую перестановку на конечном числе элементов можно разложить на циклы на непересекающихся орбитах.

Циклическими частями перестановки являются циклы, таким образом, второй пример состоит из 3-цикла и 1-цикла (или фиксированной точки) и третий состоит из двух 2-циклов и обозначается (1, 3) (2, 4).

Содержание

• 1 Определение
• 2 Основные свойства
• 3 Транспонирование
  • 3.1 Свойства
• 4 См. Также
• 5 Примечания
• 6 Ссылки
  • 6.1 Источники
• 7 Внешние ссылки

Определение

Схема циклической перестановки с двумя неподвижными точками; 6-цикл и два 1-цикла.

A перестановка называется циклической перестановкой тогда и только тогда, когда имеет единственный нетривиальный цикл (цикл длины>1).

Например, перестановка, записанная в двухстрочный (двумя способами), а также циклические обозначения,

$(1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; 4\; 2\; 7\; 6\; 5\; 8\; 1\; 3)\; =\; (1\; 4\; 6\; 8\; 3\; 7\; 2\; 5\; 4\; 6\; 8\; 3\; 7\; 1\; 2\; 5)\; =\; (1\; 4\; 6\; 8\; 3\; 7)\; (2)\; (5),\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; \backslash \backslash \; 4\; 2\; 7\; 6\; 5\; 8\; 1\; 3\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 4\; 6\; 8\; 3\; 7\; 2\; 5\; \backslash \backslash \; 4\; 6\; 8\; 3\; 7\; 1\; 2\; 5\; \backslash \; end\; \{pmatrix\}\}\; =\; (1\; \backslash \; 4\; \backslash \; 6\; \backslash \; 8\; \backslash \; 3\; \backslash \; 7)\; (2)\; (5),\}$

- шестерка -цикл; диаграмма его цикла показана справа.

Некоторые авторы ограничивают определение только теми перестановками, которые состоят из одного нетривиального цикла (то есть не допускаются фиксированные точки).

Циклическая перестановка без тривиальных циклов; 8-цикл.

Например, перестановка

$(1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; 4\; 5\; 7\; 6\; 8\; 2\; 1\; 3)\; =\; (1\; 4\; 6\; 2\; 5\; 8\; 3\; 7\; 4\; 6\; 2\; 5\; 8\; 3\; 7\; 1)\; =\; (1\; 4\; 6\; 2\; 5\; 8\; 3\; 7)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; \backslash \backslash \; 4\; 5\; 7\; 6\; 8\; 2\; 1\; 3\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 4\; 6\; 2\; 5\; 8\; 3\; 7\; \backslash \; 7\backslash \; 4\; 6\}\; \backslash \; 7\backslash \; 4\; 6\}\; =\; (1\; \backslash \; 4\; \backslash \; 6\; \backslash \; 2\; \backslash \; 5\; \backslash \; 8\; \backslash \; 3\; \backslash \; 7)\}$

является циклической перестановкой согласно этому более ограниченному определению, в то время как предыдущий пример - нет.

Более формально, перестановка $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$множества X, рассматриваемая как биективная функция $\sigma :\; X\; \to \; X\; \{\backslash \; displaystyle\; \backslash \; sigma:\; X\; \backslash \; to\; X\}$, называется циклом, если действие на X подгруппы, сгенерированной $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$, имеет не более одной орбиты с более чем одним элементом. Это понятие чаще всего используется, когда X - конечное множество; тогда, конечно, самая большая орбита S также конечна. Пусть $s\; 0\; \{\backslash \; displaystyle\; s\_\; \{0\}\}$будет любым элементом S, и положим $si\; =\; \sigma \; i\; (s\; 0)\; \{\backslash \; displaystyle\; s\_\; \{i\}\; =\; \backslash \; sigma\; ^\; \{i\}\; (s\_\; \{0\})\}$для любого $i\; \in \; Z\; \{\backslash \; displaystyle\; i\; \backslash \; in\; \backslash \; mathbf\; \{Z\}\}$. Если S конечно, существует минимальное число $k\; \ge \; 1\; \{\backslash \; displaystyle\; k\; \backslash \; geq\; 1\}$, для которого $sk\; =\; s\; 0\; \{\backslash \; displaystyle\; s\_\; \{k\}\; =\; s\_\; \{0\; \}\}$. Тогда $S\; =\; \{s\; 0,\; s\; 1,\dots ,\; sk\; -\; 1\}\; \{\backslash \; displaystyle\; S\; =\; \backslash \; \{s\_\; \{0\},\; s\_\; \{1\},\; \backslash \; ldots,\; s\_\; \{k-1\}\; \backslash \}\}$и $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$- это перестановка, определяемая как

$\sigma \; (si)\; =\; si\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; sigma\; (s\_\; \{i\})\; =\; s\_\; \{i\; +\; 1\}\}$для 0 ≤ i < k

и $\sigma \; (x)\; =\; x\; \{\backslash \; displaystyle\; \backslash \; sigma\; (x)\; =\; x\}$для любого элемента из $Икс\; \setminus \; S\; \{\backslash \; Displaystyle\; X\; \backslash \; setminus\; S\}$. Элементы, не зафиксированные в $\sigma \; \{\backslash \; displaystyle\; \backslash \; sigma\}$, можно представить как

$s\; 0\; \mapsto \; s\; 1\; \mapsto \; s\; 2\; \mapsto \; \cdots \; \mapsto \; sk\; -\; 1\; \mapsto \; sk\; =\; s\; 0\; \{\backslash \; displaystyle\; s\_\; \{0\}\; \backslash \; mapsto\; s\_\; \{1\}\; \backslash \; mapsto\; s\_\; \{2\}\; \backslash \; mapsto\; \backslash \; cdots\; \backslash \; mapsto\; s\_\; \{k-1\}\; \backslash \; mapsto\; s\_\; \{k\}\; =\; s\_\; \{0\}\}$.

Цикл можно записать с помощью компактное обозначение цикла $\sigma \; =\; (s\; 0\; s\; 1\dots \; sk\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; sigma\; =\; (s\_\; \{0\}\; ~\; s\_\; \{1\}\; ~\; \backslash \; dots\; ~\; s\_\; \{k-1\}))\}$(в этой нотации между элементами нет запятых, чтобы избежать путаницы с кортежем k- ). Длина цикла - это количество элементов его наибольшей орбиты. Цикл длины k также называется k-циклом.

Орбита 1-цикла называется фиксированной точкой перестановки, но в качестве перестановки каждый 1-цикл является тождественной перестановкой. Когда используется обозначение цикла, 1-циклы часто подавляются, когда не возникает путаницы.

Основные свойства

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

Дано количество k-циклов в симметрической группе S n, для $1\; \le \; k\; \le \; n\; \{\backslash \; displaystyle\; 1\; \backslash \; leq\; k\; \backslash \; leq\; n\}$, по следующим эквивалентным формулам

$(nk)\; (k\; -\; 1)!\; знак\; равно\; N\; (N\; -\; 1)\; \cdots \; (N\; -\; К\; +\; 1)\; К\; знак\; равно\; N!\; (п\; -\; к)!\; к\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{k\}\}\; (k-1)!\; =\; \{\backslash \; frac\; \{n\; (n-1)\; \backslash \; cdots\; (n-k\; +\; 1)\}\; \{k\}\}\; =\; \{\backslash \; frac\; \{\; n!\}\; \{(nk)!\; k\}\}\}$

k-цикл имеет сигнатуру (−1).

инверсия цикла $\sigma \; =\; (s\; 0\; s\; 1\dots \; sk\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; sigma\; =\; (s\_\; \{0\}\; ~\; s\_\; \{1\}\; ~\; \backslash \; точки\; ~\; s\_\; \{k-1\})\}$задается изменением порядка записей: $\sigma \; -\; 1\; =\; (sk\; -\; 1\dots \; s\; 1\; s\; 0)\; \{\backslash \; displaystyle\; \backslash \; sigma\; ^\; \{\; -1\}\; =\; (s\_\; \{k-1\}\; ~\; \backslash \; dots\; ~\; s\_\; \{1\}\; ~\; s\_\; \{0\})\}$. В частности, поскольку $(a\; b)\; =\; (b\; a)\; \{\backslash \; displaystyle\; (a\; ~\; b)\; =\; (b\; ~\; a)\}$, каждый два цикла является своим собственным обратным. Поскольку непересекающиеся циклы коммутируют, обращение к произведению непересекающихся циклов является результатом обращения каждого из циклов отдельно.

Транспозиции

Матрица из $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$

Цикл только с двумя элементами называется транспонированием . Например, перестановка $\pi \; =\; (1\; 2\; 3\; 4\; 1\; 4\; 3\; 2)\; \{\backslash \; displaystyle\; \backslash \; pi\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 2\; 3\; 4\; \backslash \backslash \; 1\; 4\; 3\; 2\; \backslash \; end\; \{pmatrix\}\}\}$, что местами 2 и 4.

Свойства

Любая перестановка может быть выражена как композиция (продукт) транспозиций - формально они являются генераторами для группа . Фактически, когда переставляемый набор равен {1, 2,..., n} для некоторого целого числа n, тогда любая перестановка может быть выражена как произведение смежных транспозиций $(1\; 2),\; (2\; 3),\; (3\; 4),\; \{\backslash \; displaystyle\; (1\; ~\; 2),\; (2\; ~\; 3),\; (3\; ~\; 4),\}$и так далее. Это следует потому, что произвольное транспонирование может быть выражено как произведение смежных транспозиций. Конкретно, можно выразить транспозицию $(kl)\; \{\backslash \; displaystyle\; (k\; ~~\; l)\}$, где , перемещая k на l по одному шагу за раз, а затем перемещая l обратно туда, где k was, который меняет местами эти два и не вносит никаких других изменений:

$(kl)\; =\; (kk\; +\; 1)\; \cdot \; (k\; +\; 1\; k\; +\; 2)\; \cdots \; (l\; -\; 1\; l)\; \cdot \; (l\; -\; 2\; l\; -\; 1)\; \cdots \; (кк\; +\; 1).\; \{\backslash \; Displaystyle\; (к\; ~~\; l)\; =\; (к\; ~~\; k\; +\; 1)\; \backslash \; cdot\; (k\; +\; 1\; ~~\; k\; +\; 2)\; \backslash \; cdots\; (l-1\; ~~\; l)\; \backslash \; cdot\; (l-2\; ~~\; l-\; 1)\; \backslash \; cdots\; (k\; ~~\; k\; +\; 1).\}$

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

$(abcd\dots \; yz)\; =\; (ab)\; \cdot \; (bcd\dots \; yz).\; \{\backslash \; displaystyle\; (a\; ~\; b\; ~\; c\; ~\; d\; ~\; \backslash \; ldots\; ~\; y\; ~\; z)\; =\; (a\; ~\; b)\; \backslash \; cdot\; (b\; ~\; c\; ~\; d\; ~\; \backslash \; ldots\; ~\; y\; ~\; z).\}$

Это означает начальный запрос заключается в перемещении $a\; \{\backslash \; displaystyle\; a\}$в $b,\; \{\backslash \; displaystyle\; b,\}$$b\; \{\backslash \; displaystyle\; b\}$в $с,\; \{\backslash \; displaystyle\; c,\}$$y\; \{\backslash \; displaystyle\; y\}$до $z,\; \{\backslash \; displaystyle\; z,\}$и, наконец, $z\; \{\backslash \; displaystyle\; z\}$- $a.\; \{\backslash \; displaystyle\; a.\}$Вместо этого можно свернуть элементы, сохраняя $a\; \{\backslash \; displaystyle\; a\}$там, где он находится, выполнив сначала правильный коэффициент (как обычно в обозначении операторов, и следуя соглашению из статьи о перестановках ). Это переместило $z\; \{\backslash \; displaystyle\; z\}$в позицию $b,\; \{\backslash \; displaystyle\; b,\}$, поэтому после первой перестановки элементы $a\; \{\backslash \; displaystyle\; a\}$и $z\; \{\backslash \; displaystyle\; z\}$еще не на своих конечных позициях. После этого выполняется транспонирование $(ab),\; \{\backslash \; displaystyle\; (a\; ~\; b),\}$, затем адрес $z\; \{\backslash \; displaystyle\; z\}$по индексу $b\; \{\backslash \; displaystyle\; b\}$, чтобы поменять местами то, что изначально было $a\; \{\backslash \; displaystyle\; a\}$и $z.\; \{\backslash \; displaystyle\; z.\}$

Фактически, симметрическая группа является группой Кокстера, что означает, что она генерируется элементами порядка 2 (смежные транспозиции), и все отношения имеют определенную форму.

Один из основных результатов о симметричных группах утверждает, что либо все разложения данной перестановки на транспозиции имеют четное количество транспозиций, либо все они имеют нечетное количество транспозиций. Это позволяет четности перестановки быть четко определенной концепцией.

См. Также

• Циклическая сортировка - алгоритм сортировки, основанный на идее, что сортируемая перестановка может быть разложена на циклы, которые можно по отдельности чередовать для получения отсортированного результата
• Циклы и фиксированные точки
• Циклическая перестановка целого числа
• Обозначение цикла
• Циклическая перестановка в белках

Примечания

Ссылки

Источники

• Андерсон, Марлоу и Фейл, Тодд (2005), Первый курс абстрактной алгебры, Chapman Hall / CRC; 2-е издание. ISBN 1-58488-515-7.
• Фрали, Джон (1993), Первый курс абстрактной алгебры (5-е изд.), Эддисон Уэсли, ISBN 978-0-201-53467-2
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Прентис-Холл, ISBN 978-0-13-186267-8
• Саган, Брюс Э. (1991), Симметричная группа / представления, комбинаторные алгоритмы и симметричные функции, Wadsworth Brooks / Cole, ISBN 978-0-534-15540-7

Внешние ссылки

Эта статья включает материал из цикла по PlanetMath, который находится под лицензией Creative Commons Attribution / Совместная лицензия.