The Exchange Lemma

The Exchange Lemma

Lemma: If (i₁,...,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_ilI( 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₁,...,i_l),(j₁, ...,j_l) are elements of RS( p), then there exist k £l=l( p) such that

(j₁,i₁, ..., [^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₁,j₁+1)= s_i1 ...s_ir-1(i_r,i_r+1).

But this implies (since s_j1 transposes j₁ and j₁+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₁,...,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.

The Exchange Lemma