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 (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 $\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}}$

blue-lin

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:

matrix_ball_example

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:

matrix_ball_iteration

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:

matrix_ball_example_iter2

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.$

blue-lin

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.

matrix_ball_last_entry

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, $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':$

matrix_ball_last_entry_multiple

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 (P, Q)

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.

blue-lin

Polynomials and Representations VIII

Matrix Balls