В математике , и в частности в теории групп , циклическая перестановка — это перестановка , состоящая из одного цикла. [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-циклов.
Не существует единого мнения относительно точного определения циклической перестановки. Некоторые авторы определяют перестановку σ множества X как циклическую, если «при последовательном применении каждый объект перестановленного набора будет последовательно проходить через позиции всех остальных объектов» [1] или, что то же самое, если ее представление в обозначениях цикла состоит одного цикла. [2] Другие дают более либеральное определение, допускающее фиксированные точки. [3] [4]
Непустое подмножество S множества X является циклом , если ограничение на S является циклической перестановкой S. Если X конечно , его циклы не пересекаются , а их объединение есть X. То есть они образуют разбиение , называемое циклическим разложением So. Согласно более разрешающему определению, перестановка X является циклической тогда и только тогда, когда X является ее уникальным циклом.
Например, перестановка, записанная в циклической и двухстрочной записи (двумя способами) как
имеет один 6-цикл и два 1-цикла, диаграмма его цикла показана справа. Некоторые авторы считают эту перестановку циклической, другие - нет.
В расширенном определении существуют циклические перестановки, не состоящие из одного цикла.
Более формально, для расширенного определения, перестановка множества X , рассматриваемая как биективная функция , называется циклом, если действие на X подгруппы, порожденной, имеет не более одной орбиты с более чем одним элементом. [6] Это понятие чаще всего используется, когда X — конечное множество; тогда наибольшая орбита S также конечна. Позвольте быть любым элементом S и поставьте для любого . Если S конечно, существует минимальное число, для которого . Тогда , и является перестановкой, определяемой формулой
и для любого элемента . Нефиксированные элементы можно представить как
Циклическую перестановку можно записать, используя обозначение компактного цикла (в этом обозначении между элементами нет запятых, чтобы избежать путаницы с k - кортежем ). Длина цикла равна числу элементов его наибольшей орбиты . Цикл длины k также называется k -циклом.
Орбита 1-цикла называется неподвижной точкой перестановки, но как перестановка каждый 1-цикл является тождественной перестановкой . [7] Когда используется обозначение цикла, 1-циклы часто опускаются, чтобы не возникло путаницы. [8]
Один из основных результатов о симметричных группах состоит в том, что любую перестановку можно выразить как произведение непересекающихся циклов (точнее: циклов с непересекающимися орбитами); такие циклы коммутируют друг с другом, и выражение перестановки уникально с точностью до порядка циклов. [a] Таким образом , мультимножество длин циклов в этом выражении ( тип цикла ) однозначно определяется перестановкой, и ею определяются как сигнатура, так и класс сопряженности перестановки в симметричной группе. [9]
Число k -циклов в симметрической группе Sn определяется при , следующими эквивалентными формулами:
k -цикл имеет сигнатуру (−1) k − 1 .
Обратный цикл задается изменением порядка записей : . В частности, поскольку , каждый двухцикл является своим обратным. Поскольку непересекающиеся циклы коммутируют, обратное произведение непересекающихся циклов является результатом обращения каждого из циклов в отдельности.
Цикл, состоящий только из двух элементов, называется транспозицией . Например, перестановка , меняющая местами 2 и 4. Поскольку это 2-цикл, ее можно записать как .
Любую перестановку можно выразить как композицию (произведение) транспозиций — формально они являются генераторами группы . [10] Фактически, когда перестановочный набор равен {1, 2, ..., n } для некоторого целого числа n , тогда любая перестановка может быть выражена как произведениесмежные транспозиции и так далее. Это следует из того, что произвольную транспозицию можно выразить как произведение соседних транспозиций. Конкретно, можно выразить транспозицию,перемещая k в l по одному шагу за раз, а затем возвращая l туда, где было k , что меняет эти два места и не вносит никаких других изменений:
Разложение перестановки в произведение транспозиций получается, например, путем записи перестановки в виде произведения непересекающихся циклов, а затем итеративного разбиения каждого из циклов длины 3 и длиннее на произведение транспозиции и цикла длины один. меньше:
Это означает, что первоначальный запрос состоит в том, чтобы перейти к to и, наконец, к . Вместо этого можно перекатывать элементы, сохраняя их положение, сначала выполнив правильный фактор (как обычно в операторной нотации и следуя соглашению в статье «Перестановка» ). Это переместилось в положение так, что после первой перестановки элементы и еще не заняли свои окончательные позиции. После этого выполняется транспонирование , затем адреса по индексу для замены того, что было изначально , и
Фактически симметрическая группа является группой Кокстера , то есть она порождается элементами порядка 2 (смежными транспозициями), а все отношения имеют определенный вид.
Один из основных результатов о симметричных группах гласит, что либо все разложения данной перестановки в транспозиции имеют четное количество транспозиций, либо все они имеют нечетное количество транспозиций. [11] Это позволяет четности перестановки быть четко определенным понятием.
В эту статью включены материалы из цикла PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .