Given a matrix A of non-negative integers, the standard RSK construction masks the symmetry between P and Q, but in fact we have:
Symmetry Theorem. If A corresponds to (P, Q), then the transpose of A corresponds to (Q, P). In particular, if A is a permutation matrix, then swapping P and Q corresponds to taking the inverse of A.
Here, we will give an alternative treatment for the RSK correspondence, by means of a construction known as matrix balls. We will demonstrate it with the following matrix for and :
with the RSK correspondence producing:
Description of Algorithm
As the name implies, we create a matrix and in each entry , we place balls in it. Next, we number each ball as follows:
- start from the top left entry ; label the balls 1, 2, … in order;
- we proceed left to right, top to bottom; at each entry , we look at all balls occuring to its top and left (i.e. for all and ); let be the smallest positive integer which has not been used among these entries; now label the balls in from onwards.
Our matrix above thus gives:
From this, we obtain the first rows of P and Q: for each k, the k-th entry of the first row of P is given by the first column in which k appears among the balls; likewise, the k-th entry of the first row of Q is the first row in which k appears (mnemonic: P stores the j‘s which labels the columns while Q stores the i‘s which labels the rows). This gives us
which is consistent with our RSK computation.
Next, construct a new matrix of balls. For each number , look at all the balls in the current matrix containing k; this gives a diagonal zig-zag line, running from top-right to bottom-left. Between consecutive balls containing k, say at and with we place a ball at in the new matrix without any label. Working with our matrix of balls above, we obtain:
Let be the matrix of non-negative integer entries such that is the number of balls in this new matrix. Now we label the balls in this new matrix as before, by starting from the top-left corner and proceeding left to right, top to bottom. In our working example, in the new matrix, we place 1 ball for k=3, 1 ball for k=4 and 2 balls for k=5. This gives the new matrix of balls:
Now for the second row of P (resp. Q), we again let the k-th entry denote the first column (resp. row) in which k appears among this new set of balls. In our example, this gives and which is consistent with our RSK computation.
Finally, note that there are two balls labelled 2 in this matrix; this gives rise to a single ball in location (3, 3) of the third matrix of balls, and we get
Proof of Equivalence with RSK
We now show that this construction recovers the desired P, Q. A priori, it is not even clear that P and Q are tableaux but this will be proven along the way. We use induction on the number of balls in the first matrix. Clearly there is nothing to show when
Suppose ; let be the last element occurring in the two-row array corresponding to the matrix . Thus when we traverse the matrix A left-to-right, top-to-bottom, the last non-zero entry is at Consider the following.
- Let be the matrix equal to except that
- The matrix of balls for is the same as that of , but with one ball removed from , i.e. the one with the largest label k at
- By induction hypothesis on , the obtained from its matrix balls is the same as that obtained by RSK.
- Thus we need to show, if is obtained from matrix balls of then and is obtained from by attaching u to the corresponding extra square.
First Row of (P, Q)
First suppose k only occurs once among all ball labels; it must then be maximum among them (since any ball with a larger label must lie to its right and/or below, and no such ball exists). By matrix ball construction, (resp. ) is obtained from (resp. ) by attaching v (resp. u) to the end of first row as the k-th entry. Since k is the unique maximal value, we have indeed. This settles the case.
Suppose k more than once, i.e. it occurs next at , where and and no other k occurs between rows and or columns and
By matrix ball construction, in the first row of the k-th entry equals and the 1st to (k-1)-th entries are all On the other hand, the k-th entry of equals Hence the first row of is obtained by letting bump off the k-th entry of first row of Also, note that the first row of is identical to that of Thus the first rows of P and Q are consistent with the RSK construction.
Subsequent Rows of (P, Q)
The next matrix iteration from matrix balls thus has one more ball than , i.e. one at Note that is the last entry in which is positive, hence we may repeat our reasoning from earlier.
Once again if its label k’ is unique, then the second row of is obtained from by appending to the end, and the second row of from by appending to the end. In this case, we still get and is obtained from by appending to the 2nd row (where the extra square is). Otherwise, we iterate the process for the remaining rows. This completes the proof. ♦
From the matrix ball interpretation of RSK, the symmetry theorem is obvious.
- Indeed if is the transpose of , the matrix ball obtained from is also the transpose of that obtained from All the remaining constructions are similarly transpose, with the rows and columns swapped.