Last update: 25 June 2013
For each integer let denote the symmetric group of degree that is to say the group of all permutations of the set Each is a mapping of onto itself. As is customary, we write all mappings on the left of their arguments, so that the image of under is We shall sometimes denote by the sequence Thus for example is the element of that sends 1 to 5, 2 to 3, 3 to 2, 4 to 1 and 5 to 4.
For let denote the transposition that interchanges and and fixes all other elements of We have
Also, for each let
We regard as a subset of the square and we shall adopt the convention of matrices, that in the first coordinate increases from north to south, and the second coordinate from west to east. The group acts on In particular, acts diagonally:
Let Then is the permutation
and it is clear that
Let Then from (1.2) we have
(1.4) generate the group
We shall show by induction on that each is a product of If then and there is nothing to prove. If then for some and hence by (1.3). Hence say, and therefore (as
For each the length of is the minimal length of a sequence such that
(1.5) The length of is equal to
Let temporarily denote the length of The proof of (1.4) shows that can be written as a word of length in the so that Conversely, let be any expression of as a product of To show that it is enough to show that Let from (1.3) we have and hence
Hence the proof is completed by induction on
(1.6) Let Then
|(i)||if and only if|
|(ii)||if and only if|
(i), (ii) require no comment. Also (iii) is clear, since if and only if
(iv) The set consists of all such that so that Next, we have
so that is the complement of in and therefore
Finally, since we have, by virtue of (iii) above,
The element is called the longest element of
For each let denote the set of all sequences of length such that Such sequences are called reduced words for Clearly,
(1.7) Let Then
Let Then and hence by (1.2) and (1.3) we have
from which (1.7) follows by induction on
(1.8) (Exchange Lemma). Let Then
By (1.7), applied to we have and hence
for some It follows that
so that and therefore
(1.9) Let where Then
for some pair such that
Since and there exists such that
Let so that and whence by (1.3) we have Let be a reduced word for then and are reduced words for By (1.8) (applied to it follows that for some and hence
If let denote the transposition that interchanges and and fixes each For each permutation let denote the number of such that and lies between and Consideration of and shows that
In particular, if and only if
(1.11) Let be permutations and let be a reduced word for Then the following conditions are equivalent:
|(i)||and is a transposition,|
(i) (ii). Suppose that so that Then (1.10) shows that so that Hence by (1.7) we have for some and therefore
(ii) (i). Clearly and the calculation above shows that is the transposition (1).
Let be permutations such that
|(b)||where is a transposition.|
|where is also a transposition.|
(1.12) Let and let be the longest element of Then the following conditions are equivalent
This follows from the definition and (1.6)(iii), (iv).
Let be a
reduced word for Then if and only if
such that is reduced.
This follows from (1.11).
(1.14) Let be a permutation and let Then either or Moreover we have if and only if there is a reduced word for starting with
The first statement follows from (1.3) and (1.6)(iii). If let be a reduced word for then is a reduced expression for Conversely if is reduced, it is clear that and hence
(1.15) Let be permutations and let be such that
Then if and only if both and
Assume that and let be a reduced word for Suppose that By (1.13) we have for some If then and if then has length so that by (1.14). Since both these possibilities are excluded by our hypothesis, we can conclude that Hence (1.14) shows that It follows that is a reduced expression for and is one for Hence (1.13) shows that
Conversely, assume that and As before, let be a reduced expression. Then is reduced, and since it follows from (1.13) that for some Hence and so by (1.13) again.
The Bruhat order, denoted by is the partial order on that is the transitive closure of the relation In other words, if and are permutations, means that there exists and in such that
(which implies that
(1.16) Let and be such that and Then the following conditions are equivalent:
(i) (ii). We have hence
(ii) (i). By definition there exist where such that
We have and Hence there exists such that for and
Suppose Then and also otherwise we should have and hence Hence by (1.15) we have
Next, we have and If we should by (1.15) have contradicting the definition of Hence
From (1) and (2) it follows that
This shows that (i) and (iii) are equivalent. To show that (ii) and (iii) are equivalent, assume that for some let be the longest element of and replace respectively by and Then we have
and the proof is complete.
(1.17) Let be permutations and let be a reduced word for Then the following conditions are equivalent:
|(ii)||there exists a subsequence of such that|
|(iii)||there exits a reduced subsequence of such that|
It follows from (1.13) that (i) (iii), and from (1.9) that (ii) and (iii) are equivalent. Thus it remains to prove that (iii) (i).
We proceed by induction on If we have so assume that We distinguish two cases:
(a) In this case we have hence is a subsequence of which is a reduced word for By the inductive hypothesis we have hence
(b) In this case and If we have and if then is a non-reduced subsequence of Hence the inductive hypothesis implies that But also hence by (1.16).
(1.18) Let and let be a transposition. Then
This follows from (1.11) and (1.17).
To recognize when two permutations are comparable for the Bruhat order, the following rule may be used. For each let denote the column-strict tableau (of shape whose column, for consists of the numbers arranged in increasing order from north to south.
(1.19) Let Then if and only if (i.e., each entry in is less than or equal to the corresponding entry in
If it is easily seen that and hence implies
Conversely, suppose that and let be the smallest integer such that (If we define We proceed by descending induction on If we have so assume Then is not equal to any and hence is equal to for some For each the columns of and are identical, and since it follows that i.e. Let then by (1.10) we have and hence by (1.18). Also for and so that Hence by the inductive hypothesis, and therefore
We may regard as a "diagram" of However, for many purposes it is more convenient to define the diagram of to be
Thus we have if and only if that is
Hence the points in the square not in are those for which either or
The graph of is the set of points or equivalently The complement of in therefore consists of all the lattice points due south or due east of some point of hence is the union of the hooks with corners at the points of For example, if and the diagram consists of the points circled in the picture below:
If we shall identify with the subgroup of permutations that fix We may then form the group
consisting of all permutations of the set of positive integers that fix all but a finite number of them.
The diagram of is unchanged by this identification of with the subgroup of fixing all and hence is well-defined for all Also, it is clear from the definitions and (1.7) that
|(i)||is the transpose of (i.e., we have if and only if|
|(iii)||If then consists of the lattice points for|
In particular, it follows from (iii) above that
Let and for each let
Thus is the number of points in the row of or equivalently the number of points in the row of The vector
is called the code of As with partitions, we may disregard any string of zeros at the right-hand end of and with this convention the code (like the diagram is unchanged by the embedding of in where and is well-defined for all
The permutation may be reconstructed from its code as follows :- for each is the element, in increasing order, of the sequence of positive integers from which have been deleted. The sum is equal to Each sequence of non-negative integers such that occurs as the code of a unique permutation
The length of is the largest such that From the definition, is the last descent of the permutation that is to say and
|(i)||If (i.e., if then where is the sequence with in the place and elsewhere.|
(i) follows from (1.21)(i), and (ii) follows from (i) by induction on
(1.24) Let Then
Suppose that Then the row of is strictly contained in the row, whence Conversely, if then the row of is contained in the row, so that
To compute the code of in terms of the code of we introduce the following notation. If is any sequence and is an integer let
so that the operation introduces a zero after the place. Then we have
where is the sequence consisting of 1's.
By induction on the length of it is enough to show that if is the permutation whose code is then
Now the diagram of is obtained from that of by deleting the first row (of length and then moving each column after the one space to the left. On reading the diagrams of and by columns, we obtain (1).
The shape of a permutation is the partition whose parts are the non-zero arranged in weakly decreasing order. We have
Next, recall that for two partitions and the relation means that and for all [Mac1979, Ch.I], With this understood, the shapes of and are related by
Let Define a matrix as follows: if and otherwise. Then is a matrix with row-sums in some order, and column-sums in some order. Hence (see e.g. [Mac1979, Ch.I, §6]) we have
Special interest attaches to those permutations for which They may be characterized in various ways:
(1.27) The following conditions on a permutation are equivalent:
|(i)||the set of rows of is totally ordered by inclusion;|
|the set of rows of is totally ordered by inclusion;|
|(ii)||the set of columns of is totally ordered by inclusion;|
|the set of columns of is totally ordered by inclusion;|
|(iii)||there do not exist such that and|
|(iv)||there exist such that is the diagram of a partition|
Since it is clear that (i) and (ii) Morever (i) (ii), for either is false if and only if there exist such that and belong to whilst and do not. Let and then we have and Thus (i), (ii) and (iii) are all equivalent.
Next, it is clear that the conjunction of (i) and (ii) is equivalent to (iv). Thus it remains to show that (iv) and (v) are equivalent. If (iv) is satisfied, then and whence (v) is satisfied. Conversely, if and then can be brought into coincidence with by suitable permutations of the rows and of the columns, whence (iv) is satisfied.
An element is said to be vexillary if it satisfies the equivalent conditions of (1.27). By (1.27) (iii), the first non-vexillary permutation is in
For each let
where as before is the longest element of Then
|(ii)||is the reflection of in the "antidiagonal"|
(i) follows from (1.6) (or from (ii) below).
(ii) If then
(iii) now follows from (ii).
From (1.27) and (1.28) it follows that
(1.29) is vexillary is vexillary is vexillary.
We consider next two particular types of vexillary permutations.
(1.30) Let Then the following conditions are equivalent:
|(i)||the code of is a partition;|
|(ii)||the code of is a partition;|
|(iii)||is the diagram of a partition.|
Clearly (iii) implies (i) and (ii).
Conversely, suppose that is a partition where We shall show by induction on that
This is true for so assume that and that the statement is true for Then we have for and for some Since it follows that the row of consists of the points as required. Hence (i) implies (iii), and the same argument applied to shows that if the code of is a partition, then is the diagram of a partition. Hence so is by (1.21) (i), and the proof is complete.
A permutation is said to be dominant if it satisfies the equivalent conditions of (1.30). Dominant permutations are clearly vexillary, and is dominant if and only if is dominant.
(1.31) Let Then the following conditions are equivalent:
(i) (ii). By (1.15) we have and (ii) (i). We have
If satisfies the equivalent conditions of (1.31), is called a Grassmannian permutation. By (1.27)(iii), Grassmannian permutations are vexillary, and is Grassmannian if and only if is Grassmannian.
Let be a permutation, its code. Consider the following two conditions on the sequence
|(V1)||If and then|
|(V2)||If and then whenever|
(1.32) A permutation is vexillary if and only if its code satisfies (V1) and (V2).
For each let
be the row of
Suppose first that is vexillary with code Let be such that Then (where denotes strict containment), hence there exists Let then and (since we have and Hence for fixed such that and the number of between and such that is at most so that (V1) is satisfied.
Next let be vexillary, and so that Let If then so that lies in but not in which is impossible. Hence and therefore So we have and (V2) is satisfied.
Conversely, suppose that the code of satisfies (V1) and (V2). Then so does the sequence and we may therefore assume that the set is totally ordered by inclusion.
Let and suppose first that If there exists such that so that There are at least elements such that and since each such satisfies it is of the form for some between and Since it follows that Since either or we conclude that (strict inclusion) and hence that Hence there are at least values of between and for which contradicting (V1). Hence
Finally, let and so that If there exists such that we have for some between and and since we have contradicting (V2). Hence in this case, and the proof is complete.
Remark. It is stated in [LSc1985, prop. 2.4] that is vexillary if and only if satisfies (V1) and
|(V3)||If for some then for all|
Since (V3) is implied by (V2), it follows from (1.32) that every vexillary code satisfies (V1) and (V3). However, the conjuction of (V1) and (V3) is not sufficient for vexillarity: for example, the permutation is not vexillary (since e.g. it contains the subword 2163) but its code is which satisfies (V1) and (V3) (but not (V2)).
Let be a permutation with code For each such that let
Arrange the numbers in increasing order of magnitude, say The sequence
is called the flag of It is a sequence of length equal to where is the shape of
Remark. There is another definition of the flag of a permutation due to M.Wachs [Wac1985]. For each such that let
Arrange the numbers in increasing order of magnitude, say and let
These two notions are not equivalent. In fact
(1.33) (J. Alfano) We have if and only if the permutation satisfies (V2).
If we have for and hence for these values of Hence in all cases, and we shall have if and only if for each But this condition means that, for each the set of such that is an interval; and this is just a restatement of the condition (V2).
We shall show that a vexillary permutation is uniquely determined by its shape and its flag
Let us write in the form
where and each For let
so that If is the code of each nonzero is equal to for some and
It follows that (whether is vexillary or not)
Moreover we must have
since in the sequence there are terms and they must all occur in the first places of the sequence.
(1.37) Suppose is a vexillary pennutation with shape and flag given by (1.34) and (1.35). Then the must satisfy the inequalities
If there is nothing to prove, so assume that and therefore Let
Since and is vexillary, we have by (V1)
since exactly terms of the sequence are equal to
Finally we have
because for all and for all such that by virtue of (V2).
From (1), (2), and (3) we deduce that
which proves (1.37).
(1.38) For each sequence satisfying (1.36) and (1.37) there is a unique vexillary permutation with shape and flag The code of is constructed as follows: first the entries equal to are inserted at the right-hand end of the interval then the entries in equal to are inserted in the rightmost available spaces in the interval and so on: for each when all the terms in the sequence have been inserted, the entries equal to are inserted in the rightmost available spaces of the interval
Suppose first that is vexillary. If and then by (V2) we have for all such that Hence the entries equal to in the sequence must be inserted as described above.
Conversely, if the sequence is constructed as above, we claim that satisfies (V1) and (V2), and hence is vexillary by (1.32). Suppose first that and say Then the number of such that and is equal to the number of blank spaces in the interval after all the entries have been inserted, hence is at most
which by (1.37) is Hence the sequence satisfies (V1). Suppose next that and say with Then we have From the definition of the sequence it follows that for each such that we have and hence whenever Consequently the condition (V2) is satisfied, and the proof is complete.
If is a permutation and we denote by the permutation
Let us say that two permutations are diagonally equivalent if either or for some Graphically, this means that the diagram of can be brought into coincidence with that of by a translation along the diagonal and is vexillary if and only if is vexillary. The equivalence classes of vexillary permutations of a given shape are then determined by the differences and hence it follows from (1.37) and (1.38) that
(1.39) The number of diagonal equivalence classes of vexillary permutations of shape is
We may remark that this number is the product of the hook lengths at the re-entrant nodes of the border of the diagram of (i.e., the nodes with coordinates
Example. If the flag must satisfy Hence there are vexillary classes, and the representatives of these classes for which (or equivalently are as follows:
Let as before and let
be the conjugate partition, where and each We have
where The border of the diagram of is a staircase with risers of heights (starting from the top) and treads of lengths (starting at the bottom).
Recall (1.27) that if is vexillary of shape then is vexillary of shape
(1.41) Let be a vexillary permutation of shape and flag Then the flag of is
We proceed by induction on Let be the code of and let be the permutation with code We may assume that Then for some and we have
Since is vexillary, its code satisfies the conditions (V1) and (V2). Hence also satisfies these conditions, and therefore is vexillary. It follows that so that
where We have so that the inductive hypothesis applies to Hence if are defined by the formula we have
But if has code then by (1.25) we have
From (1) and (2) and (1.40) it follows that
If let where is the longest element in If is vexillary, of shape then is vexillary of shape by (1.27) and (1.28). Let
be the flag of Then we have
For once we shall leave the proof to the reader.
Let denote the number of non-vexillary and let
be the probability that an element of is non-vexillary. The first few values of and are
was computed by A. Garsia. I would guess that is of the order of
If we divide up the sequence into consecutive blocks of length and observe that the probability that such a block satisfies the vexillarity condition (1.27)(iii) is (because contains only one non-vexillary permutation), we see that the probability that is vexillary is at most hence decreases exponentially to zero. (A. Lascoux.) Thus the vexillary permutations in become sparser and sparser as increases.
Instead of counting non-vexillary permutations, we may attempt to count vexillary permutations. Let us say that a permutation is primitive if and For each let (resp. denote the number of vexillary (resp. primitive vexillary) permutations Since each primitive vexillary gives rise to imprimitive vexillary permutations in namely where and it follows that
Hence the generating functions
are related by
For each partition let denote the number of primitive vexillary permutations of shape in and let
Each is a polynomial, and we shall now show how to compute it. Write in the form
as before, where By (1.37) a vexillary permutation of shape is uniquely determined by its flag where is any vector of positive integers satisfying the inequalities (1.36), (1.37):
Moreover we shall have if and only if the first element of the code of is not zero, and this will be the case if and only if
In general, if is the code of a permutation then if and only if for where is the length of In other words, the least for which is In the case of a vexillary permutation as above, with flag the numbers will increase strictly as runs through each non-empty interval and hence will be primitive in if and only if satisfies (1) above and
Let for and put
so that for each From (1.36) we have
It now follows that
summed over the integer vectors having at least one zero component, and satisfying the inequalities (3), (4) above. We have
(since is primitive vexillary of shape if and only if is primitive vexillary of shape
Julian West, a student of R. Stanley, has recently shown that
where is the degree of the irreducible representation of the symmetric group indexed by the partition From this and results of A. Regev (Advances in Math. 41 (1981) 115-136) it follows that
as where is a constant that Regev determines explicitly.
The formula (1) gives that
This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.