The Lehmer code and reduced decompositions

next up previous contents
Next: Sn as a Up: Actions Previous: Rothe diagram and

The Lehmer code and reduced decompositions

The Lehmer code is the sequence of numbers of white buttons in the columns of

For example

If it is clear which is meant, then we may replace by the shorter sequence

arising from by canceling the zeros at the end of , for example

It is not difficult to see how can be reconstructed from . Clearly is the -th element of , with respect to the natural order of . Correspondingly, is the -th element of , and so on. For example

Furthermore, each , , is , i.e.

Since there are such sequences in , we have obtained:

. Corollary   The Lehmer code establishes a bijection between and the set of sequences in , , for each .

This shows that in fact the Lehmer code is a code for permutations.

But there is much more to say about Lehmer codes. Applying the equivalences

we can easily derive (exercise gif) that right multiplication of by the elementary transposition has the following effect on :

. Lemma   For each and each we have

if , while


The main point is that the shift from to amounts (cf. gif) to an increase or a decrease in

by 1. Hence the following holds:

. Corollary   The sum of the entries of the Lehmer code of is equal to the minimal number of elementary transpositions which are needed in order to express as a product of elementary transpositions. Moreover, this yields a canonic way of expressing as a product of elementary transpositions by decreasing the rightmost nonzero entry of the Lehmer code by 1 and iterating this process until each entry is equal to zero.

We therefore call the reduced length of and we call such an expression of as a product of elementary transpositions, which is of minimal length, a reduced decomposition. A reduced decomposition of for example, is obtained from the following sequence of manipulations of Lehmer codes, according to gif:

This shows that

is a reduced decomposition. Try to compute the reduced composition of some permutations.

The lemma gif also shows how we can obtain all the reduced decompositions of a given permutation:

. Corollary   The complete set of reduced decompositions of is obtained by carrying out all the successive multiplications that reduce the Lehmer sequence by 1, according to gif.


E .   Check gif.

next up previous contents
Next: Sn as a Up: Actions Previous: Rothe diagram and

Herr Fripertinger
Sun Feb 05 18:28:26 MET 1995