The Lehmer code and reduced decompositions |

The *Lehmer code*
is the sequence of numbers of white buttons in the columns of * L( p):*

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

For example

L([54132])= bar (43010).

If it is clear which *n* is meant, then we may replace *L( p)* by the
shorter sequence

L( p)^{+}

arising from *L( p)* by canceling the zeros at the end of *L( p)*, for
example

L([54132])^{+}= bar (4301).

It is not difficult to see
how * p* can be reconstructed from *L( p)*. Clearly * p1* is the *(l _{1}
( p)+1)*-th element of

L( p):= bar (23100) yields p=[35214].

Furthermore, each *L( p)*, * pÎS _{n} *, is

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

Since there are *n!* such
sequences in * N^{ n}*, we have obtained:

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

l_{i}( p) <= l_{i+1}( p) Û pi< p(i+1), l_{i}( p)>l_{i+1}( p) Û pi> p(i+1),

we can easily derive (exercise)
that right multiplication of * p* by the elementary
transposition * s _{i}=(i,i+1)* has the following effect on

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

l( p):= å_{i}l_{i}( p)

by 1. Hence the following holds:

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

[54132]= s_{4}s_{3}s_{2}s_{1}s_{4}s_{3}s_{2}s_{4}

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

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 "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

The Lehmer code and reduced decompositions |