### The Exchange Lemma

**Lemma: **
*
If ** (i*_{1},...,i_{l})ÎRS( p), then
*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 *l( p)-1*. The induction hypothesis gives
*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 Lemma**
If * (i*_{1},...,i_{l}),(j_{1}, ...,j_{l}) are elements of *RS( p)*, then there exist
*k £l=l( p)* such that
*(j*_{1},i_{1}, ..., [^i] _{k}, ...,i_{l}) ÎRS( p),

where * [^i] *_{k} means that *i*_{k} is left out.

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 *r* such that
*(j*_{1},j_{1}+1)= s_{i1} ...s_{ir-1}(i_{r},i_{r}+1).

But this implies (since * s*_{j1} *transposes* *j*_{1} and *j*_{1}+1):
* 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@kfunigraz.ac.at,

last changed: August 28, 2001