The Lehmer code and reduced decompositions |

For exampleL( p):= bar (l_{1}( p) ...l_{n}( p)), where l_{i}( p) := | {i<j | pi> pj } | .

If it is clear whichL([54132])= bar (43010).

arising fromL( p)^{+}

It is not difficult to see howL([54132])^{+}= bar (4301).

Furthermore, eachL( p):= bar (23100) yields p=[35214].

Since there are" i În: l_{i}( p) £n-i.

Corollary:The Lehmer code establishes a bijection betweenSand the set of sequences_{n}bar (lin_{1}( p) ...l_{n}( p)),N^{ n}l, for each_{i}( p) £n-ii.

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) that right multiplication ofl_{i}( p) <= l_{i+1}( p) Û pi< p(i+1), l_{i}( p)>l_{i+1}( p) Û pi> p(i+1),

Lemma:For eachpÎSand each_{n}swe have_{i}ÎS_{ n}ifL( ps_{i})= bar (l_{1}( p), ...,l_{i-1}( p),l_{i+1}( p), l_{i}( p)-1,l_{i+2}( p), ...),l, while_{i}( p)>l_{i+1}( p)L( ps_{i})= bar (l_{1}( p), ...,l_{i-1}( p),l_{i+1}( p)+1,l_{i}( p),l_{i+2}( p), ...),l._{i}( p) <= l_{i+1}( p)

The main point is that the shift from * p* to * ps _{i}* amounts
(cf. the Lemma above) to an increase or a decrease in

by 1. Hence the following holds:l( p):= å_{i}l_{i}( p)

Corollary:The suml( p)of the entries of the Lehmer codeL( p)ofpÎSis equal to the minimal number of elementary transpositions_{n}swhich are needed in order to express_{i}pas a product of elementary transpositions. Moreover, this yields a canonic way of expressingpas a product ofl( p)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 *l( p)* the
*reduced length*
of * p* and we call such an expression of * p* as a product of
*l( p)* elementary transpositions, which is of minimal length, a
*reduced decomposition.*
A reduced decomposition of *[54132],* for example, is obtained from the following sequence of manipulations
of Lehmer codes, according to the
corollary:

This shows that

is a reduced decomposition. Try to compute the reduced composition of some permutations.[54132]= s_{4}s_{3}s_{2}s_{1}s_{4}s_{3}s_{2}s_{4}

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

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

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

The Lehmer code and reduced decompositions |