RS to RSK correspondence

The RS correspondence is a correspondence which associates to each permutation a pair of standard Young tableaux of the same shape.

The RSK correspondence associates to each integer matrix (with non-negative entries) a pair of semistandard Young tableaux of the same shape.

Given an integer matrix, replace it by a permutation matrix whose rows and columns, when partitioned according to the row and column sums of the original matrix, have block sums equal to the entries of the original matrix. There is a unique such permutation matrix with the property that there are no descents within any of the blocks (each block is a partial permutation).

For example, if

$A=\begin{pmatrix} 2 & 1\\ 1 & 0\end{pmatrix}$

then the corresponding permutation matrix is

$\tilde A =\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}$

Here the row and column partitions are both $(3,1)$.

It seems to be well-known (for example, it is implicit in Fulton's matrix ball construction) that to obtain the SSYT's for $A$, one may substitute for each entry in the SYT's for $\tilde A$ the integers corresponding to the blocks the rows and columns corresponding to these entries belong.

In the above example, the SYT's associated to $\tilde A$ are

$P = Q = \begin{array}{cc} 1 & 2 & 3 \\ 4 & &\end{array}$

into which we would saubstitute $1$ for $1,2,3$ and $2$ for $4$ to get the SSYT's for $A$:

$P = Q = \begin{array}{cc} 1 & 1 & 1 \\ 2 & & \end{array}$.

Is there a nice reference for this result?

• I think the growth diagram construction is clearer than the matrix ball construction. However I don't know of an account of growth diagrams for the RSK correspondence for integer matrices. I would be interested to hear of one. – Bruce Westbury Jun 20 '12 at 8:35
• Dear Bruce, this was essentially done by S. Fomin himself in "Schur operators and Knuth correspondences". – Philippe Nadeau Jun 20 '12 at 8:54
• Dear Philippe, thanks. I could do with some help in understanding that paper in terms of growth diagrams. – Bruce Westbury Jun 20 '12 at 10:32
• Stanley's book Enumerative Combinatorics, Volume 2, discusses Fomin's viewpoint and is written with students in mind. Look at Section 7.13, Symmetry of the RSK Algorithm. – Patricia Hersh Jun 20 '12 at 10:59
• Thanks Patricia. What I am missing is growth diagrams for the two Knuth correspondences. It is clear what to do for $(0,1)$-matrices. It is not clear to me what to do for integer matrices. I realise this is not an issue for experts. The point I am not clear on is how one arrives at growth diagrams starting from the paper by Fomin that Philippe refers to. – Bruce Westbury Jun 20 '12 at 12:15

I would look at chapter 7 in Enumerative Combinatorics, Volume 2, by Richard Stanley. A second place that can also be helpful for getting a good understanding of RS is Bruce Sagan's book called The Symmetric Group.

• It is Lemma 7.11.6 in Stanley. – Amritanshu Prasad Jun 20 '12 at 8:04

[Responding particularly to Bruce...] You may want to take a look at my thesis, which was the first place that the Knuth versions of RSK were "Fominized". There are lots of examples, which others have told me they've found helpful in understanding this material. (I'm sure Fomin already understood that this could be done, but it doesn't appear in his papers before 1991.) I put a scan on the web at:

http://www.math.uconn.edu/~troby/research.html

Scroll down to:

Applications and Extensions of Fomin's Generalization of the Robinson-Schensted Correspondence to Differential Posets, Ph.D. Thesis, Massachusetts Institute of Technology, 1991.

The key idea is just that RS commutes with "standardization" of words or SSYT, where one adds subscripts from Left to Right in the word and corresponding tableaux. See EC2, Lemma 7.11.6.

Thanks to Tricia Hersh for mentioning this thread at the SIAM DM conference. This is my first posting to MathOverflow, so I'm not allowed to comment.

Hope this helps!

Tom

Warning: I do not know nothing about combinatorial problems, so what I say now might be completely wrong. However: Rota in his talk at the Birkhoff memorial conference (The many lives of lattice theory, easily available online) has, in the section about semiprimary lattices, something which seemes strongly related.

Edit: citing from the article: each of the two chains is associated with a standard Young tableau, hence we obtain the statement and proof of the Schensted algorithm, which precisely associates a pair of standard Young tableaux to every permutation.

• I found an article with that title in the Notices. It did not mention the RSK correspondence. – Amritanshu Prasad Jun 20 '12 at 8:07