Разложение перестановки в композицию независимых циклов

Независимые циклы коммутируют: φψ = ψφ.

Циклы φ,ψ ∈ Sn вида  φ = (a₁ a₂ ... a_k ), ψ = (b₁ b₂ ... b_l )
называются независимыми, если они перемещают разные элементы:
{a₁ a₂ ... a_k } ∩ {b₁ b₂ ... b_l } = ∅.

Например:   φ,ψ ∈ S₆ , φ = (3 1 5), ψ = (4 6).

Пример разложения перестановки на независимые циклы:

 Пусть

Видим, что φ(1) = 4,φ(4) = 6, φ(6) = 2, φ(2) = 1.

На элементе 1 цикл замкнулся:  1 → 4 → 6 → 2 → 1.

Говорят, что элементы 1,2,4,6 попарно φ-эквивалентными, а множество {1,2,4,6} является φ-орбитой точки 1 (это также φ-орбита каждой из точек 2,4,6). Любые две из этих точек можно связать посредством φ, например:
6 = φ² (1), 4 = φ⁻¹ (6) = φ³ (6), и т. п.

Заметим, что на множестве {1,2,4,6} перестановка φ действует так же, как цикл (1 4 6 2).
Точка 3 не вошла в орбиту точки 1. Действуем на неё перестановкой φ до тех пор, пока не вернёмся обратно в 3: 3 → 7 → 3. Это соответствует циклу (3 7). Осталась точка 5, которая соответствует вырожденному циклу (5) = e.

Получаем:   φ = (1 4 6 2)(3 7)(5)    φ-эквивалентность.

Пример 2. Разложить в произведение циклов

1 переходит в 2, 2 в 3, 3 снова в один - первый цикл и т.д.

 Калькулятор для разложение перестановки в композицию независимых циклов

(примечание: в калькулятор вставляем вторую строку)

 

 

Пусть φ ∈ Sn . Элементы i,j ∈ Xn будем называть φ-эквивалентными и писать   , если если существует такое k ∈ Z, что φ_k (i) = j. 

Это отношение эквивалентности:

Орбита. Пусть φ ∈ Sn , j ∈ Xn . Орбитой элемента j относительно перестановки φ (короче, φ-орбитой элемента j) называют класс элемента φ по отношению φ-эквивалентности, т. е. множество всех элементов вида φ_k (j), где k ∈ Z.

Множество всех φ-орбит есть разбиение Xn .