В математике и, в частности, в теории групп , циклическая перестановка (или цикл ) - это перестановка элементов некоторого множества 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). [1]
Например, перестановка, записанная в двухстрочной записи (двумя способами), а также обозначения цикла,
шестицилиндровый; его диаграмма цикла показана справа.
Некоторые авторы ограничивают определение только теми перестановками, которые состоят из одного нетривиального цикла (то есть не допускаются неподвижные точки). [2]
Например, перестановка
является циклической перестановкой в соответствии с этим более ограничительным определением, в то время как предыдущий пример - нет.
Более формально, перестановка множества X , рассматриваемая как биективная функция , называется циклом, если действие на X подгруппы, сгенерированной с помощью, имеет не более одной орбиты с более чем одним элементом. [3] Это понятие чаще всего используется, когда X - конечное множество; тогда, конечно, самая большая орбита S также конечна. Позвольте быть любым элементом из S и положить для любого . Если S конечно, существует минимальное число, для которого . Тогда и - перестановка, определяемая формулой
- для 0 ≤ i < k
и для любого элемента . Элементы, не закрепленные с помощью, можно изобразить как
- .
Цикл может быть записан с использованием компактной записи цикла (в этой записи нет запятых между элементами, чтобы избежать путаницы с k - кортежем ). Длина цикла является количество элементов своей самой большой орбите. Цикл длины k также называют k -циклом.
Орбита 1-цикла называется фиксированной точкой перестановки, но в качестве перестановки каждый 1-цикл является тождественной перестановкой . [4] Когда используется обозначение цикла, 1-циклы часто подавляются, когда не возникает путаницы. [5]
Основные свойства [ править ]
Один из основных результатов о симметрических группах состоит в том, что любую перестановку можно выразить как произведение непересекающихся циклов (точнее: циклов с непересекающимися орбитами); такие циклы коммутируют друг с другом, и выражение перестановки уникально с точностью до порядка циклов. [а] мультимножеством длин циклов в этом выражении (The типа цикла ), таким образом , однозначно определяется перестановкой, и оба подпись и класс сопряженных элементов перестановки в симметрической группе определяются ею. [6]
Число k -циклов в симметрической группе S n определяется по следующим эквивалентным формулам
К -циклу имеет подпись (-1) K - 1 .
Обратного цикла определяется изменением порядка записи: . В частности, поскольку каждый двухцикл является своим обратным. Поскольку непересекающиеся циклы коммутируют, обратное к произведению непересекающихся циклов является результатом обращения каждого из циклов по отдельности.
Транспозиции [ править ]
Цикл, состоящий всего из двух элементов, называется транспозицией . Например, перестановка, которая меняет местами 2 и 4.
Свойства [ править ]
Любая перестановка может быть выражена как композиция (продукт) транспозиций - формально они являются генераторами для группы . [7] Фактически, когда переставляемый набор равен {1, 2, ..., n } для некоторого целого числа n , тогда любая перестановка может быть выражена как произведение смежных транспозиций и так далее. Это следует потому, что произвольное транспонирование может быть выражено как произведение смежных транспозиций. Конкретно, можно выразить транспозицию, где , перемещая k на l по одному шагу за раз, затем перемещая l обратно туда, где k was, который меняет местами эти два и не вносит никаких других изменений:
Разложение перестановки в продукт транспозиций получается, например, записывая перестановку как продукт непересекающихся циклов, а затем итеративно разбивая каждый из циклов длины 3 и более на продукт перестановки и цикла длины один. меньше:
Это означает , что первоначальный запрос , чтобы перейти к , чтобы к и , наконец , чтобы вместо можно свернуть элементы сохраняя где, выполнив правый фактор первым (как обычно , в обозначениях оператора, и после конвенции в статье о подстановках ). После первой перестановки элементы переместились в позицию so и еще не достигли своих конечных позиций. После этого выполняется транспонирование , затем адреса по индексу, чтобы поменять местами то, что было изначально, и
Фактически, симметрическая группа является группой Кокстера , что означает, что она порождается элементами порядка 2 (смежные транспозиции), и все отношения имеют определенную форму.
Один из основных результатов о симметрических группах утверждает, что либо все разложения данной перестановки на транспозиции имеют четное число транспозиций, либо все они имеют нечетное число транспозиций. [8] Это позволяет четности перестановки быть четко определенным понятием.
См. Также [ править ]
- Циклическая сортировка - алгоритм сортировки, основанный на идее, что сортируемая перестановка может быть разложена на циклы, которые можно индивидуально чередовать для получения отсортированного результата.
- Циклы и фиксированные точки
- Циклическая перестановка целого числа
- Обозначение цикла
- Круговая перестановка в белках
Заметки [ править ]
- ^ Обратите внимание, что обозначение цикла не является уникальным: каждый k -цикл может быть записан k различными способами, в зависимости от выборана его орбите.
Ссылки [ править ]
- ^ Богарт, Кеннет П. (1990), Введение в комбинаторику (2-е изд.), Харкорт, Брейс, Йованович, стр. 486, ISBN 0-15-541576-X
- ^ Гросс, Джонатан Л. (2008), Комбинаторные методы с компьютерными приложениями , Chapman & Hall / CRC, стр. 29, ISBN 978-1-58488-743-0
- ^ Fraleigh 1993 , стр. 103
- ^ Ротман 2006 , стр. 108
- Перейти ↑ Sagan 1991 , p. 2
- ^ Ротман 2006 , стр. 117, 121
- ^ Ротман 2006 , стр. 118, Предложение 2.35
- ^ Ротман 2006 , стр. 122
Источники [ править ]
- Андерсон, Марлоу и Фейл, Тодд (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), Симметричная группа / представления, комбинаторные алгоритмы и симметричные функции , Уодсворт и Брукс / Коул, ISBN 978-0-534-15540-7
Внешние ссылки [ править ]
Эта статья включает материалы из цикла PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .