First we have an easy result
where is the number of SSYT of shape and type .
Proof: We know that
Equating coefficient of both sides, we get on LHS and on RHS.
Thus we also have .
It is known that computing is a -P complete problem (M. Dyer). But does that imply is also -P complete to compute? Nobody knows.
Important special case: the number of standard Young tableaux of shape is equal to which counts many things, in particular the dimension of the irreducible representation of corresponding to (as we mentioned in the previous lecture). Consider
Looking at the coefficient of both sides, we get LHS = and RHS because (look at the term).
Also for any group , we have .
The next topic is to remove the K from RSK (joke of course), i.e., one could use -arrays without repeated values. This is achieved by standardization of the 2-line array with repeated values, and it is done in the most naive way:
- Replace the top row by .
- Suppose there were ones in the second row before, now replace them in order by , and if there were twos before, replace them from left to right by , i.e., in the most natural way to fill the second row with nonrepeating natural numbers.
- Perform Schensted algorithm on the standardized 2-line array to obtain and .
- One could then recover the original SSYTs and by replacing in and by and respectively.
This doesn’t seem that interesting.
Next we explore the symmetries of RSK algorithm:
Proposition 2 Let the -matrix correspond via RSK to the pair of Young tableaux , then corresponds to .
Persi didn’t give a proof in class because it wasn’t so inspiring, but I find the following geometric proof in Stanley worth mentioning; note that it only works for permutations matrices , corresponding to 2-line arrays with no repetition in each row. Proof: Consider the following procedure:
- Draw an grid.
- Replace the s in the permutation matrix by X’s in the corresponding positions of the grid.
- Label all the leftmost and bottom corners (so there are of them) of the grid with .
- Inductively label the interior corners using four local rules, which we do not detail because the book didn’t address the well-definedness of these rules very well, imbedded several claims such as necessarily without explanation, and also seems to contain a typo in the top row second to the last entry of the table (7.50) (it should be instead of ).
- The last column forms a sequence of partitions, increasing in the dominance order, by viewing say as the partition . Insert into the box that the th partition differs from the th. This gives a standard Young tableau; call it . Similarly call the SYT obtained from the top row . This indeed gives the RSK correspondence.
Now the symmetry of RSK with respect to transposition is immediate, as the procedure above works on the matrix itself.
This in particular implies that if corresponds to , then corresponds to .
- is symmetric if and only if if and only if .
- implies .
which which we suggestively separated into the diagonal and off-diagonal terms.
The coefficient of the left hand side is given thus by the number of ways of choosing ‘s and ‘s with such that for each , , where the last summand comes from reversing the row of and in (5). This is the number of -matrices with row sum equal to .
The right hand side clearly gives the number of SSYT of type , because we are summing over all shapes that can potentially afford type . Finally, by the previous corollary, these two numbers are equal.
2. Dual RSK
Here we work with matrices, in anticipation of the duality between bononic and fermionic space, or that between ‘s and ‘s. As an example, from the following matrix
we obtain the two-line array
from which we perform an RSK algorithm that bumps a number in the first row that’s largest and smaller than or equal to the current number (as opposed to smallest and larger than the current).
with corresponding tableau
Theorem 5 There is a 1-1 correspondence of matrices with of the same shape such that are SSYTs. Furthermore and .
The proof is analogous to the bosonic case, and authors usually omit it.
Proof: Same reasoning as before: the coefficient on left hand side counts the number of matrices with row sum and colsum . Note there is no inverse sign on the left. And that on the right hand side counts SSYTs whose shapes are transposes of each other, and with type for one and for the other.
Corollary 7 Recall the involution , with . We have
Proof: We already proved several lectures ago that
By orthonormality of , we also know that
Applying ( acting on only the variable) to everything and using the previous corollary finishes the proof.
3. Classical definition of Schur functions
Let be a composition that terminates at th term, and let act on by
where is the signature. Then we have
Theorem 8 For , and a partition, viewed as a composition of length . Then
This apparently was first known to Cauchy by fiddling.