| | | The Exchange Lemma |
Lemma: If (i1,...,il)ÎRS( p), thenProof: 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':= psil= si1 ...sil -1, which is of reduced length l( p)-1. The induction hypothesis givesI( p)= { sil ...sir+1(ir,ir+1) | 1 £r £l=l( p) }.
I( p')= { sil-1 ...sir+1(ir,ir+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' sil)= silI( p') È{(il, il+1) }
= { sil...sir+1(ir,ir+1) | 1 £r £l-1 } È{(il,il+1) }
= { sil...sir+1(ir,ir+1) | 1 £r £l },as it is stated.
We are now in a position to prove the following important result:
The Exchange Lemma If (i1,...,il),(j1, ...,jl) are elements of RS( p), then there exist k £l=l( p) such thatProof: We know that I( p-1)= { si1 ...sir-1(ir,ir+1) | 1 £r £l }, and hence there exists an r such that(j1,i1, ..., [^i] k, ...,il) ÎRS( p),where [^i] k means that ik is left out.
(j1,j1+1)= si1 ...sir-1(ir,ir+1).But this implies (since sj1 transposes j1 and j1+1):
sj1= si1 ...sir-1 sir( si1 ...sir-1)-1,and so sj1 si1 ...sir-1= si1 ...sir-1 sir, 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[x1,...,xn]. 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 |