### Sn as a Coxeter Group

Reduced decompositions play a role also in the theory of other groups.
The symmetric group * S*_{n} is in fact a *Coxeter group,*
which means that
there exists a set of generators *s*_{i} such that the relations
are of the particular form *(s*_{i}s_{j})^{mij}=1, where
*m*_{ij} Î**N**, m_{ii}=1, m_{ij}=m_{ji}>1, if i not =j.

In the case of the symmetric group * S*_{n} , the Coxeter system of generators is the
subset
* S*_{ n} of elementary transpositions * s*_{i}=(i,i+1), as we have
seen already.
Furthermore, this leads us to introduce the *weak
Bruhat order*
* * on * S*_{n} , which is the transitive closure of
* p ·r : Û l( r)=l( p)+1, and
$ s*_{i} :r= ps_{i}.

The Bruhat order of the symmetric group *S*_{ 4} is shown in
figure.
We note that the number of reduced decompositions (and also the *set* of reduced decompositions)
can be obtained by going from the identity upwards in all the possible ways until the permutation in
question is reached.

The Bruhat order of *S*_{ 4}

We are now approaching a famous result on reduced sequences for the proof of
which we need a better knowledge of the set of inversions.
In order to describe how *I( ps*_{i}), s_{i} ÎS_{ n}, arises from
*I( p)*, we use that * S*_{n} acts on * *__n__^{2} in a canonic way: * r(i,j)=
( ri, rj)*. Keeping this in mind, we easily obtain:

*
I( ps*_{i})= s_{i}I( p) È{(i,i+1) } if pi< p(i+1)

and
*I( ps*_{i})=
s_{i}I( p) \{(i,i+1) } if pi> p(i+1).

This yields for the corresponding reduced lengths:
*
l( ps*_{i})= l( p)+1 if pi< p(i+1)

and
*l( ps*_{i})=
l( p)-1 if pi> p(i+1),

in accordance with the Lemma.
If * w*_{n} denotes the permutation *[n, ...,1]* of maximal length,
then
*
l( w*_{n})=[n choose 2], l( w_{n} r)=[n choose 2]-l( r)=l(
rw_{n}).

Proof: Clearly *I( w*_{n})= {(i,j) Î__n__^{2} | i<j }, and hence
*l( w*_{n})=[n choose 2]. Moreover
* rw*_{n}=[ rn, ..., r1],

so *I( rw*_{n})= __n__^{2} \I( r), and
*l( rw*_{n})=[n choose 2]- l( r). Finally we note that
*l( w*_{n} r)=l(( w_{n} r)^{-1})=l( r^{-1} w_{n})
=[n choose 2]-l( r^{-1})=[n choose 2]-l( r),

which completes the proof.

An expression

* p= s*_{i1}...s_{il}, s_{i} ÎS_{ n},

of * p* in terms of elementary transpositions and *minimal*
*l=l( p)* was called a reduced decomposition
of * p*. The set of corresponding
*sequences* of indices is indicated as follows:
*RS( p):= { (i*_{1},...,i_{l}) | p= s_{i1}...s_{il}, s_{i} ÎS_{n},l
minimal }.

These sequences are called *reduced sequences*
of * p*.

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001