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

В математике и, в частности, в теории групп , циклическая перестановка (или цикл ) - это перестановка элементов некоторого множества 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).

Определение [ править ]

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

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

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

${\ displaystyle {\ 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) \ 6 \ 7 \ 6 \ end; (2) (5),}$

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

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

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

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

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

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

Более формально, перестановка множества X , рассматриваемая как биективная функция , называется циклом, если действие на X подгруппы, сгенерированной с помощью, имеет не более одной орбиты с более чем одним элементом. ^[3] Это понятие чаще всего используется, когда 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-цикл является тождественной перестановкой . ^[4] Когда используется обозначение цикла, 1-циклы часто подавляются, когда не возникает путаницы. ^[5]

Основные свойства [ править ]

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

Число 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}}}$

К -циклу имеет подпись (-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.${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}$

Свойства [ править ]

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

${\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).}$

Это означает , что первоначальный запрос , чтобы перейти к , чтобы к и , наконец , чтобы вместо можно свернуть элементы сохраняя где, выполнив правый фактор первым (как обычно , в обозначениях оператора, и после конвенции в статье о подстановках ). После первой перестановки элементы переместились в позицию so и еще не достигли своих конечных позиций. После этого выполняется транспонирование , затем адреса по индексу, чтобы поменять местами то, что изначально было, и${\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 (смежные транспозиции), и все отношения имеют определенную форму.

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

Источники [ править ]

• Андерсон, Марлоу и Фейл, Тодд (2005), Первый курс абстрактной алгебры , Chapman & Hall / CRC; 2-е издание. ISBN 1-58488-515-7 . 
• Фрали, Джон (1993), первый курс абстрактной алгебры (5-е изд.), Addison Wesley, 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 / Share-Alike License .