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

reducedWords -- computes the reduced words of a permutation

Description

A permutation $p$ can be expressed as a product of transpositions. A reduced word is a minimal-length expression of a permutation as a product of transpositions. The reducedWords method computes all of the reduced words of a permutation. A word is represented by a list of integers, where $i$ denotes the transposition $(i,i+1)$.

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

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

o1 : Permutation
i2 : words = reducedWords p

o2 = {{1, 2, 1, 3, 2, 1}, {1, 2, 3, 1, 2, 1}, {1, 2, 3, 2, 1, 2}, {1, 3, 2,
     ------------------------------------------------------------------------
     1, 3, 2}, {1, 3, 2, 3, 1, 2}, {2, 1, 2, 3, 2, 1}, {2, 1, 3, 2, 1, 3},
     ------------------------------------------------------------------------
     {2, 1, 3, 2, 3, 1}, {2, 3, 1, 2, 1, 3}, {2, 3, 1, 2, 3, 1}, {2, 3, 2, 1,
     ------------------------------------------------------------------------
     2, 3}, {3, 1, 2, 1, 3, 2}, {3, 1, 2, 3, 1, 2}, {3, 2, 1, 2, 3, 2}, {3,
     ------------------------------------------------------------------------
     2, 1, 3, 2, 3}, {3, 2, 3, 1, 2, 3}}

o2 : List

We can check that a reduced word multiplies out to the original permutation. Note that we need to multiply from right to left, so we must reverse the list.

i3 : word = words#0

o3 = {1, 2, 1, 3, 2, 1}

o3 : List
i4 : product reverse apply(word, i -> transposition i)

o4 = Permutation{4, 3, 2, 1}

o4 : Permutation

See also

Ways to use reducedWords:

  • reducedWords(Permutation)

For the programmer

The object reducedWords is a method function.


The source of this document is in Permutations/Documentation/mainDocs.m2:624:0.