Циклическая перестановка - NiNa.Az

В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка (1, 3, 2, 4), переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка (1, 3)( 2, 4), переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.

Цикл в перестановке — это подмножество элементов, которые переставляются циклическим образом. Множество S называется орбитой цикла. Каждую перестановку конечного множества элементов можно разложить в объединение циклов с непересекающимися орбитами. В некоторых контекстах циклическая перестановка сама по себе называется циклом.

Определение

перестановки

Перестановка называется циклической тогда и только тогда, когда она состоит из единственного нетривиального цикла (т.е. цикла длиной больше 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{pmatrix}}=(146837)(2)(5)}$

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

перестановки

Пример:

${\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}}=(14625837)}$

Более формально, перестановка множества X, которая является биективной функцией ${\displaystyle \sigma :X\to X}$, называется циклической, если действие на X подгруппы с генератором ${\displaystyle \sigma }$ имеет максимум одну орбиту из более чем одного элемента. Это понятие чаще всего используется, когда X является конечным множеством. Тогда, конечно, наибольшая орбита S также конечна. Пусть ${\displaystyle s_{0}}$ — любой элемент S, положим ${\displaystyle s_{i}=\sigma ^{i}(s_{0})}$ для любого ${\displaystyle i\in \mathbf {Z} }$. Если множество S конечно, имеется минимальное число ${\displaystyle k\geqslant 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}\quad }$ для ${\displaystyle 0\leq 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}}$.

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

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

По одному из основных свойств симметрических групп, любую перестановку можно представить как произведение непересекающихся циклов (более точно — циклов с непересекающимися орбитами). Такие циклы можно переставлять друг с другом, и выражение перестановки единственно с точностью до порядка циклов (заметим, что циклическая запись не единственна — любой k-цикл сам по себе может быть записан k различными способами в зависимости от выбора ${\displaystyle s_{0}}$ в его орбите). Мультимножество длин циклов (цикловый тип) однозначно определяется перестановкой.

Число различных циклов длины k в симметрической группе S_n задаётся для ${\displaystyle 1\leqslant k\leqslant 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.

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

Массив транспозиций

Цикл, состоящий из двух элементов, называется транспозицией. Например, перестановка {1, 4, 3, 2}, переводящая 1 в 1, 2 в 4, 3 в 3 и 4 в 2 является транспозицией (а именно, транспозицией, переставляющей 2 и 4).

Любую перестановку можно представить как композицию (произведение) транспозиций — формально, они являются генераторами группы. Более того, любую перестановку упорядоченного множества X = {1, 2, …, n} можно выразить как произведение смежных транспозиций, то есть транспозиций вида ${\displaystyle (k~~k+1).}$ Действительно, любую транспозицию можно представить в виде произведения смежных транспозиций.

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

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

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

Один из главных результатов элементарной теории симметрических групп утверждает, что либо все разложения данной перестановки на транспозиции имеют чётное число транспозиций, либо все разложения имеют нечётное число транспозиций. Это позволяет чётности перестановки быть хорошо определённой функцией.

См. также

• ^[англ.] — алгоритм сортировки, основанный на идее, что массив можно разложить на циклы, которые можно индивидуально прокрутить, чтобы получить сортированный массив
• ^[англ.]
• ^[англ.]
• ^[англ.]

Примечание

1. Bogart, 1990, с. 486.
2. Gross, 2008, с. 29.
3. Fraleigh, 1993, с. 103.
4. Sagan, 1991, с. 2.
5. Rotman, 2006, с. 118, Prop. 2.35.
6. Rotman, 2006, с. 122.

Литература

• Anderson M., Feil T. . A First Course in Abstract Algebra. 2nd edition. — Boca Raton: Chapman & Hall/CRC, 2005. — 696 p. — ISBN 1-58488-515-7.
• Fraleigh J. . A First Course in Abstract Algebra. 5th edition. — Reading: Addison-Wesley, 1993. — 576 p. — ISBN 978-0-201-53467-2.
• Rotman J. J. . A First Course in Abstract Algebra with Applications. 3rd edition. — Upper Saddle River: Prentice Hall, 2006. — 581 p. — ISBN 978-0-13-186267-8.
• Sagan B. E. . The Symmetric Group: Representations, Combinatorial Algorithms & Symmetric Functions. — Belmont: Wadsworth, 1991. — 197 p. — ISBN 978-0-534-15540-7.
• Bogart K. P. . Introductory Combinatorics. 2nd edition. — San Diego: Harcourt, Brace, Jovanovich, 1990. — 622 p. — ISBN 0-15-541576-X.
• Gross J. L. . Combinatorial Methods with Computer Applications. — Boca Raton: Chapman & Hall/CRC, 2008. — xvii + 644 p. — ISBN 978-1-58488-743-0.

Ссылки

• Permutations as a Product of Transpositions