Macaulay2 » Documentation
Packages » Permutations :: Cyclic decomposition
next | previous | forward | backward | up | index | toc

Cyclic decomposition -- an overview of cyclic decompositions of permutations

Every permutation can be decomposed as a product of disjoint cycles. This can be computed with cycleDecomposition.

i1 : p = permutation {3,1,2,5,4}

o1 = Permutation{3, 1, 2, 5, 4}

o1 : Permutation
i2 : cycleDecomposition p

o2 = {(3, 2, 1), (5, 4)}

o2 : List

We follow the convention to write the decomposition in its "canonical" or "standard" form. So

1. each cycle is listed with its largest element first, and
2. the cycles are listed in increasing order.

A permutation's cycle type is the sequence consisting of the lengths of the cycles in its cycle decomposition, listed in weakly decreasing order.

i3 : cycleType p

o3 = (3, 2)

o3 : Sequence

Foata's fundamental bijection

Foata's fundamental bijection is a bijection between a permutation's standard cycle decomposition and another permutation read the same (in one-line notation) as the decomposition with its parentheses removed. For example, if $p = (3 \, 2 \, 1)(5 \, 4)$ (written in cycle notation), then its corresponding permutation (written in one-line notation) is $\hat{p} = (3 \, 2 \, 1 \, 5 \, 4)$.

i4 : p = permutation {3,1,2,5,4};
i5 : foataBijection p

o5 = Permutation{3, 2, 1, 5, 4}

o5 : Permutation

Decomposition into transpositions

A permutation can also be decomposed as a product of transpositions. When this is done minimally (with respect to the number of transpositions used), such decompositions are called reduced words. We can compute these with reducedWords.

i6 : p = permutation {3,1,2,5,4};
i7 : reducedWords p

o7 = {{1, 2, 4}, {1, 4, 2}, {4, 1, 2}}

o7 : List

We can verify that these reduced words multiply to the original permutation.

i8 : all(reducedWords p, word -> product reverse apply(word, transposition) == p)

o8 = true

The source of this document is in Permutations/Documentation/packageDocs.m2:204:0.