Polynomials and Representations VIII

Matrix Balls

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 (PQ), then the transpose of A corresponds to (QP). 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 \lambda = (5, 3, 3) and \mu = (5, 3, 3):

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

with the RSK correspondence producing:

P = \boxed{\begin{matrix}1 & 1 & 1 & 1 & 1 & 2 & 3 \\2 & 2 & 3 \\3 \end{matrix}} \qquad Q = \boxed{\begin{matrix}1 & 1 & 1 & 1 & 1 & 3 & 3 \\2 & 2 & 2 \\3\end{matrix}}


Description of Algorithm

As the name implies, we create a matrix and in each entry (i, j), we place A_{ij} balls in it. Next, we number each ball as follows:

  • start from the top left entry (i,j)=(1,1); label the balls 1, 2, … in order;
  • we proceed left to right, top to bottom; at each entry (i,j), we look at all balls occuring to its top and left (i.e. (i',j') for all i\le i', j\le j' and (i',j') \ne (i,j)); let k be the smallest positive integer which has not been used among these entries; now label the balls in (i,j) from k 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

P_1 = (1, 1, 1, 1, 1, 2, 3), \qquad Q_1 = (1, 1, 1, 1, 1, 3, 3).

which is consistent with our RSK computation.

Next Step

Next, construct a new matrix of balls. For each number k=1, 2, \ldots, 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 (u,v) and (u',v') with u > u', v < v', we place a ball at (u, v') in the new matrix without any label. Working with our matrix of balls above, we obtain:


Let A' = (A'_{ij}) be the matrix of non-negative integer entries such that A'_{ij} 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 P_2 = (2, 3, 3) and Q_2 = (2, 2, 2) 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 P_3 = (3) = Q_3.


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 |\lambda| = |\mu|, the number of balls in the first matrix. Clearly there is nothing to show when |\lambda| \le 1.

Suppose d := |\l| > 1; let (u, v) be the last element occurring in the two-row array (i_r, j_r) corresponding to the matrix A_{ij}. Thus when we traverse the matrix A left-to-right, top-to-bottom, the last non-zero entry is at (u, v). Consider the following.

  • Let B := (B_{ij}) be the matrix equal to A_{ij} except that B_{uv} = A_{uv} - 1.
  • The matrix of balls for (B_{ij}) is the same as that of (A_{ij}), but with one ball removed from (u, v), i.e. the one with the largest label k at (u,v).
  • By induction hypothesis on (B_{ij}), the (P', Q') obtained from its matrix balls is the same as that obtained by RSK.
  • Thus we need to show, if (P, Q) is obtained from matrix balls of (A_{ij}), then P = P' \leftarrow v and Q is obtained from Q' by attaching u to the corresponding extra square.


First Row of (PQ)

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, P (resp. Q) is obtained from P' (resp. Q') 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 P = P' \leftarrow v indeed. This settles the case.

Suppose k more than once, i.e. it occurs next at (u',v'), where u' <u and v'> v and no other k occurs between rows u and u' or columns v and v':


By matrix ball construction, in the first row of P', the k-th entry equals v' and the 1st to (k-1)-th entries are all \le v. On the other hand, the k-th entry of P equals v. Hence the first row of P is obtained by letting v bump v' off the k-th entry of first row of P'. Also, note that the first row of Q is identical to that of Q'. Thus the first rows of P and Q are consistent with the RSK construction.

Subsequent Rows of (PQ)

The next matrix iteration A'_{ij} from matrix balls thus has one more ball than B'_{ij}, i.e. one at (u, v'). Note that (u, v') is the last entry in A'_{ij} which is positive, hence we may repeat our reasoning from earlier.

Once again if its label k’ is unique, then the second row of P is obtained from P' by appending v' to the end, and the second row of Q from Q' by appending u to the end. In this case, we still get P = P'\leftarrow v and Q is obtained from Q' 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 B_{ij} is the transpose of A_{ij}, the matrix ball obtained from (B_{ij}) is also the transpose of that obtained from (A_{ij}). All the remaining constructions are similarly transpose, with the rows and columns swapped.


This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s