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

В математике , и в частности в теории групп , циклическая перестановка — это перестановка, состоящая из одного цикла. ^[1]^[2] В некоторых случаях циклические перестановки называются циклами ; ^[3] если циклическая перестановка имеет k элементов, ее можно назвать k -циклом . Некоторые авторы расширяют это определение, включив в него перестановки с неподвижными точками в дополнение не более чем к одному нетривиальному циклу. ^[3]^[4] В обозначениях циклов циклические перестановки обозначаются списком их элементов, заключенным в круглые скобки, в том порядке, в котором они переставляются.

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

Для более широкого определения циклической перестановки, допускающей фиксированные точки, каждая из этих неподвижных точек представляет собой тривиальные орбиты перестановки, и существует единственная нетривиальная орбита, содержащая все оставшиеся точки. Это можно использовать в качестве определения: циклическая перестановка (допускающая фиксированные точки) — это перестановка, имеющая единственную нетривиальную орбиту. Любую перестановку на конечном числе элементов можно разложить на циклические перестановки, нетривиальные орбиты которых не пересекаются. ^[5]

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

Определение

Циклическая перестановка, состоящая из одного 8-цикла.

Не существует единого мнения относительно точного определения циклической перестановки. Некоторые авторы определяют перестановку $σ$ набора $X$ как циклическую, если «последовательное применение будет проводить каждый объект перестановочного набора последовательно через позиции всех других объектов». ^[1] или, что то же самое, если его представление в обозначениях циклов состоит из одного цикла. ^[2] Другие предлагают более либеральное определение, допускающее фиксированные точки. ^[3]^[4]

Непустое $S$ множества $X$ является циклом подмножество $\sigma$ если ограничение $\sigma$ to $S$ является циклической перестановкой S . Если $X$ конечно , его циклы не пересекаются их объединение есть $X.$ , а То есть они образуют раздел , называемый циклическим разложением $\sigma .$ Итак, согласно более либеральному определению, перестановка $X$ является циклической тогда и только тогда, когда $X$ — ее уникальный цикл.

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

{\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}

имеет один 6-цикл и два 1-цикла, диаграмма его цикла показана справа. Некоторые авторы считают эту перестановку циклической, другие - нет.

Перестановка, которая является циклической для расширенного определения, но не для ограниченного, с двумя фиксированными точками (1-циклами) и 6-циклом.

В расширенном определении существуют циклические перестановки, не состоящие из одного цикла.

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

\sigma (s_{i})=s_{i+1}

для 0 ≤ я < к

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

s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}

.

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

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

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

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

Число k симметрической группе Sn _{-циклов в} задано для $1\leq k\leq n$ , по следующим эквивалентным формулам: ${\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.$

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

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

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

Цикл, состоящий только из двух элементов, называется транспозицией . Например, перестановка $\pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}$ который меняет местами 2 и 4. Поскольку это 2-цикл, его можно записать как $\pi =(2,4)$ .

Характеристики

Любую перестановку можно выразить как композицию произведение) транспозиций — формально они являются генераторами группы ( . ^[10] Фактически, когда переставляемый набор равен ${1, 2, ..., n}$ для некоторого целого числа $n$ , тогда любая перестановка может быть выражена как произведение соседние транспозиции $(1~2),(2~3),(3~4),$ и так далее. Это следует из того, что произвольную транспозицию можно выразить как произведение соседних транспозиций. Конкретно можно выразить транспозицию $(k~~l)$ где $k<l$ перемещая $k$ к $l$ шаг за шагом, а затем $возвращая l$ туда, где $был k$ , что меняет эти два места и не вносит никаких других изменений:

(k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).

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

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).

Это означает, что первоначальный запрос — переместить $a$ к $b,$ $b$ к $c,$ $y$ к $z,$ и наконец $z$ к $a.$ Вместо этого можно перекатывать элементы, сохраняя $a$ где это происходит путем выполнения сначала правильного фактора (как обычно в операторной записи и следуя соглашению в статье « Перестановка »). Это переместилось $z$ на позицию $b,$ поэтому после первой перестановки элементы $a$ и $z$ еще не достигли своих окончательных позиций. Транспонирование $(a~b),$ выполняется после этого, затем обращается $z$ по индексу $b$ поменять местами то, что было изначально $a$ и $z.$

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

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

См. также

Циклическая сортировка - алгоритм сортировки, основанный на идее о том, что сортируемая перестановка может быть разбита на циклы, которые можно индивидуально вращать для получения отсортированного результата.
Циклы и фиксированные точки
Циклическая перестановка целого числа
Обозначение цикла
Круговая перестановка в белках
Перетасовка Фишера-Йейтса

Примечания

^ Обратите внимание, что обозначение цикла не уникально: каждый k -цикл сам по себе может быть записан k разными способами, в зависимости от выбора $s_{0}$ на своей орбите.

Ссылки

^ Jump up to: Перейти обратно: ^а ^б Гросс, Джонатан Л. (2008). Комбинаторные методы с компьютерными приложениями . Дискретная математика и ее приложения. Бока-Ратон, Флорида: Chapman & Hall/CRC. п. 29. ISBN 978-1-58488-743-0 .
^ Jump up to: Перейти обратно: ^а ^б Кнут, Дональд Э. (2002). Искусство компьютерного программирования . Аддисон-Уэсли. п. 35.
^ Jump up to: Перейти обратно: ^а ^б ^с Богарт, Кеннет П. (2000). Вводная комбинаторика (3-е изд.). Лондон: Harcourt Academic Press. п. 554. ИСБН 978-0-12-110830-4 .
^ Jump up to: Перейти обратно: ^а ^б Розен, Кеннет Х. (2000). Справочник по дискретной и комбинаторной математике . Бока-Ратон Лондон Нью-Йорк: CRC press. ISBN 978-0-8493-0149-0 .
^ Эрлих, Гертруда (2013). Основные понятия абстрактной алгебры . Дуврские книги по математике. Курьерская корпорация. п. 69. ИСБН 9780486291864 .
^ Фрэли 1993 , с. 103
^ Ротман 2006 , с. 108
^ Саган 1991 , с. 2
^ Ротман 2006 , с. 117, 121
^ Ротман 2006 , с. 118, п. 2.35.
^ Ротман 2006 , с. 122

Источники

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

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

Циклическое обозначение перестановок , видео объясняет циклическое разложение.

В эту статью включены материалы из цикла PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .

[9] Обратите внимание, что обозначение цикла не уникально: каждый k -цикл сам по себе может быть записан k разными способами, в зависимости от выбора $s_{0}$ на своей орбите.

[:0-1] Jump up to: Перейти обратно: ^а ^б Гросс, Джонатан Л. (2008). Комбинаторные методы с компьютерными приложениями . Дискретная математика и ее приложения. Бока-Ратон, Флорида: Chapman & Hall/CRC. п. 29. ISBN 978-1-58488-743-0 .

[:1-2] Jump up to: Перейти обратно: ^а ^б Кнут, Дональд Э. (2002). Искусство компьютерного программирования . Аддисон-Уэсли. п. 35.

[:2-3] Jump up to: Перейти обратно: ^а ^б ^с Богарт, Кеннет П. (2000). Вводная комбинаторика (3-е изд.). Лондон: Harcourt Academic Press. п. 554. ИСБН 978-0-12-110830-4 .

[:3-4] Jump up to: Перейти обратно: ^а ^б Розен, Кеннет Х. (2000). Справочник по дискретной и комбинаторной математике . Бока-Ратон Лондон Нью-Йорк: CRC press. ISBN 978-0-8493-0149-0 .

[5] Эрлих, Гертруда (2013). Основные понятия абстрактной алгебры . Дуврские книги по математике. Курьерская корпорация. п. 69. ИСБН 9780486291864 .

[6] Фрэли 1993 , с. 103

[7] Ротман 2006 , с. 108

[8] Саган 1991 , с. 2

[10] Ротман 2006 , с. 117, 121

[11] Ротман 2006 , с. 118, п. 2.35.

[12] Ротман 2006 , с. 122

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[9]

[10]

[11]