The Exchange Lemma |

Lemma:If(i, then_{1},...,i_{l})ÎRS( p)I( p)= { s_{il}...s_{ir+1}(i_{r},i_{r}+1) | 1 £r £l=l( p) }.

Proof: By induction on *l=l( p)*. The case *l=0* yields the empty set
which is in fact the set of inversions of * p=1*. If *l ³1*, then we
can consider * p':= ps _{il}= s_{i1} ...s_{il
-1}*, which is of reduced length

I( p')= { s_{il-1}...s_{ir+1}(i_{r},i_{r}+1) | 1 £r £l-1 },

and from equation we know how *I( p)* can be obtained from *I( p')*,
since *l( p)= l( p')+1* shows which of the two cases holds:

I( p= p' s_{il})= s_{il}I( p') È{(i_{l}, i_{l}+1) }

= { s_{il}...s_{ir+1}(i_{r},i_{r}+1) | 1 £r £l-1 } È{(i_{l},i_{l}+1) }

= { s_{il}...s_{ir+1}(i_{r},i_{r}+1) | 1 £r £l },

as it is stated.

We are now in a position to prove the following important result:

The Exchange LemmaIf(iare elements of_{1},...,i_{l}),(j_{1}, ...,j_{l})RS( p), then there existk £l=l( p)such thatwhere(j_{1},i_{1}, ..., [^i]_{k}, ...,i_{l}) ÎRS( p),[^i]means that_{k}iis left out._{k}

Proof: We know that
*I( p ^{-1})= { s_{i1} ...s_{ir-1}(i_{r},i_{r}+1) | 1 £r £l },*
and hence there exists an

(j_{1},j_{1}+1)= s_{i1}...s_{ir-1}(i_{r},i_{r}+1).

But this implies (since * s _{j1}*

s_{j1}= s_{i1}...s_{ir-1}s_{ir}( s_{i1}...s_{ir-1})^{-1},

and so
* s _{j1} s_{i1} ...s_{ir-1}= s_{i1} ...s_{ir-1} s_{ir}*,
which proves the statement.

This result will be used much later in order to introduce an important class
of polynomials, the Schubert polynomials. They correspond to the
permutations and form an
important basis of the polynomial ring * È _{n>0} Z[x_{1},...,x_{n}]*. They will be
defined with the aid of a differential operator that corresponds to a
reduced decomposition, and the Exchange Lemma will be used in order to
prove that this operator is independent of the chosen reduced decomposition.
Moreover, they form a natural generalization of the so-called Schur
polynomials which are important both for the enumeration theory of symmetry
classes of mappings and for the representation theory of symmetric groups.

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 Exchange Lemma |