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

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

В математике , и в частности в теории групп , циклическая перестановка — это перестановка, состоящая из одного цикла. ^{[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 является циклом , если ограничение на S является циклической перестановкой S. Если X конечно , его циклы не пересекаются , а их объединение равно X. То есть они образуют разбиение , называемое циклической декомпозицией . Таким образом, согласно более разрешительному определению, перестановка X является циклической тогда и только тогда, когда X является ее единственным циклом. ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma .}$

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

${\displaystyle {\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-циклом

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

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

${\displaystyle \sigma (s_{i})=s_{i+1}}$для 0 ≤ i < k

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

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

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

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

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

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

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

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

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

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

Матрица​ ${\displaystyle \pi }$

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

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

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

${\displaystyle (k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).}$

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

${\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}$

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

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

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

Смотрите также

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

Примечания

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

Ссылки

1. Gross, Jonathan L. (2008). Комбинаторные методы с компьютерными приложениями . Дискретная математика и ее приложения. Бока-Ратон, Флорида: Chapman & Hall/CRC. стр. 29. ISBN 978-1-58488-743-0.
2. Knuth, Donald E. (2002). Искусство программирования . Addison-Wesley. стр. 35.
3. Богарт, Кеннет П. (2000). Вводная комбинаторика (3-е изд.). Лондон: Harcourt Academic Press. стр. 554. ISBN 978-0-12-110830-4.
4. Rosen, Kenneth H. (2000). Справочник по дискретной и комбинаторной математике . Boca Raton London New York: CRC press. ISBN 978-0-8493-0149-0.
5. Эрлих, Гертруда (2013). Основные понятия абстрактной алгебры. Dover Books on Mathematics. Courier Corporation. стр. 69. ISBN 9780486291864.
6. Фрейли 1993, стр. 103
7. Ротман 2006, стр. 108
8. Саган 1991, стр. 2
9. Ротман 2006, стр. 117, 121
10. Ротман 2006, стр. 118, Предложение 2.35
11. Ротман 2006, стр. 122

Источники

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

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

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

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