The Exchange Lemma

. Lemma   If , then

Proof: By induction on . The case yields the empty set which is in fact the set of inversions of . If , then we can consider , which is of reduced length . The induction hypothesis gives

and from we know how can be obtained from , since shows which of the two cases holds:

as it is stated.

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

. The Exchange Lemma   If are elements of , then there exist such that

where means that is left out.

Proof: We know that and hence there exists an such that

But this implies (since transposes and ):

and so , 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 . 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.