First we describe the Schensted algorithm, which associates to each permutation two Young tableaux of the same shape but possibly different types; it consists of bumping numbers into a greedy patience sorting procedure.
- In the first step we write down.
- After the first k steps, we have a Young tableau of boxes, filled in with . Now we consider , if it’s bigger than all the numbers in the first row, we simple append at the end of the first row. Otherwise we replace the smallest number bigger than in the first row with ; we say that bumps into , denoted . this results in a new tableau of size and an extra number that’s the one being displaced, which we denote by . Now let be with the first row deleted and we repeat the procedure on and as we did with and . The end product is a Young tableau of certain shape and will be denoted .
- We now define another Young tableau also of shape , which assigns the number to box if position is the newest box added in the th step of the above bumping process for .
We will show that the map is a bijection. Now recall a permutation can be represented as a two-row list:
Knuth extended it to allow for repeated values in both rows above, i.e.,
where , and within the block of equal ‘s, the underneath ‘s are weakly increasing as well. These two-line arrays always arise in the following way: take a finite matrix with natural number entries. Now we scan the entries from left to right first and then up to down. If we see the number in the th position, then we write down over in the two-line array times. Clearly this gives a two-line array with the requisite monotonicity properties. Furthermore it’s not hard to see that every such two-line array can arise in this fashion in a unique way. We can similarly define and SSYTs (as opposed to SYT) with the same shape , associated with (or equivalently the matrix ). Notice that takes values from and from . Furthermore we have
- The number of boxes in the first row of equals the length of the longest weakly increasing subsequence of ,
- The number of boxes in the first column equals the length of the longest strictly decreasing subsequence of .
As a reference, C. Greene in his “An extension of Schensted’s Theorem” interprets the length of the other rows and columns as well.
Some open-ended questions:
- for , one can always find valued matrix with those two as row and column sums, by working off the diagonal from upper left corner down, taking the maximally allowed value at each entry. This procedure can be shown not to get stuck if . But is there any combinatorially canonical choice for A?
- Given , what does the shape of tell us about ? And is there a natural metric on the space of all matrices with prescribed row and column sums?
Proposition 7 The tableau given by a two line array defined above is Semi-standard.
Proof: It suffices to show that inserting a number into the top row of a SSYT yields another SSYT. The only bad thing that could happen to the shape is if at some stage the displaced number is appended to the end of the next row. But this can’t happen due to the strictly increasing property down the columns of SSYT.
Next observe that the weak increasingness down columns are still preserved, in particular the column below . Rows are weakly increasing by inspection. Strict monotonicity down the columns is true because of the choice of the box we bump at each stage: it cannot be inserted into the box right below its original position.
Proposition 8 is also SSYT.
Proof: We only need to worry about the monotonicity property defining SSYT. Weak monotonicity is easy to see, just because the boxes are added in the natural way of building a Ferrers diagram. We only need to show strict monotonicity down the column. So suppose are two equal elements in the top row of the 2-line array . We need to show they are in different columns of . But by definition of 2-line array, , hence one could show that the insertion path of (i.e., the sequence of boxes inserted at each row until the bottom row is reached or until some box is appended), lies strictly to the left of that of , (see Stanley p. 314), and could never go below that of , hence and are not in the same column.
From and we can reconstruct by following the monotonicity requirements of the latter. It’s not too hard to show this reconstruction is a bijection. (Details are in Stanley vol II of course)
This bijectivity allows us to establish
hence form a basis of .
Proof: Expanding geometrically we have
For weak compositions and ,
by inspection (the are suggestive of the matrix with the requisite row and column sum , .
On the other hand, in the right hand side of (10), we also have 3, because essentially we are summing over all which by Schensted-Knuth bijection is equal to the number of all 2-line arrays with first row given by and second row given by , which in turn is equal to all matrices with row sum and column sum .
Thus forms a basis by the duality result established in the last lecture.