Polynomials and Representations VI

For now, we will switch gears and study the combinatorics of the matrices $\mathbf M = (M_{\lambda\mu})$ and $\mathbf N = (N_{\lambda\mu}),$ where $\lambda, \mu$ run over all partitions of d>0. Eventually, we will show that there is a matrix K such that:

$\mathbf M = \mathbf K^t \mathbf K, \qquad \mathbf N = \mathbf K^t \mathbf J \mathbf K$

where J is the permutation matrix swapping $\lambda$ and its transpose. To achieve that, we will need to digress a little.

blue-lin

Young Tableaux

Let $\lambda$ be any partition; we will use a Young diagram for $\lambda$ comprising of boxes. A filling of $\lambda$ is obtained by writing a positive integer in each box. The filling is called a semistandard Young tableau (SSYT) if the rows are weakly increasing and columns are strictly increasing. Finally, it is called a standard Young tableau (SYT) if the entries are a permutation of 1 to $d = |\lambda|.$

If $\lambda = (4,3,1)$ the following are examples:

filling_ssyt_syt

$\lambda$ is called the shape of a filling, while the tuple $\mu = (\mu_1, \mu_2, \ldots)$ where $\mu_k$ is the number of occurrences of k, is called the type of the filling. Thus, the above 3 fillings all have shape (4, 3, 1); their types are (1, 3, 2, 1, 1), (2,2,2,0,1,1) and (1,1,1,1,1,1,1,1) respectively.

We will now describe an important operation to create new SSYTs.

Row Insertions

Given an SSYT P and positive integer k, we write $P\leftarrow k$ for the filling which has $k$ added to it in the following manner.

First we add k to the first row. If k ≥ the rightmost entry, we add another square to the tableau and write k in it; this ends the process.
Otherwise, starting from the rightmost entry and proceeding leftwards, we find the first square whose contents we can replace with k, while ensuring that the row is weakly increasing. In other words, we find the leftmost element which is greater than k, then swaps with k. If that square had content j, we say that k bumps out j.
Now we proceed to add j to the next row, via the above process.
If we finish all rows with square i left over, we add a row with a single square and write i in it.

As the reader may suspect, $P\leftarrow k$ is always an SSYT (to be proved later).

Example

Suppose we have an SSYT with three rows: (1,1,2,4,5,6,6), (2,3,5,5,7) and (3,4,6); to add an element 3 to it, we proceed as follows, ending with a tableau with four rows. Thus, 3 bumps out 4 in the first row, which bumps out 5 in the second row, etc.

young_tableau_updating

For convenience, we let $I(P, k)$ denote the set of squares whose contents were replaced (or added). Each square is denoted by $(i, j)$ , where i is the row number and j is the column number. In the above example, we obtain: $I(P, k) = \{(1, 4), (2, 3), (3, 3), (4, 1)\}.$

blue-lin

Basic Properties

Lemma 1. The replaced squares $I(P, k)$ move to the left (weakly) as we proceed down the rows, i.e. if $(i, j), (i+1, j') \in I(P, k)$ , then $j \ge j'.$

Proof

Suppose $(i, j) \in I(P, k)$ ; consider the square directly below it. Either it is $> P_{ij}$ or it does not exist. In the latter case, we do not worry about $(i+1, j') \in I(P, k).$ In the former case, since $P_{i+1, j}$ is larger than the bumping number $P_{ij},$ no square after $(i+1, j)$ can be bumped. ♦

Lemma 2. The resulting $P \leftarrow k$ is a semistandard Young tableau.

Proof

By construction, the rows of $P\leftarrow k$ are weakly increasing so we need to show that its columns are strictly increasing. Suppose $k'$ bumps out $P_{ij} = k''$ ; since a number can only bump out something bigger, the number directly beneath $(i,j)$ (if it exists) is $>k'' > k'.$

What about the number above $(i, j)$ ? Suppose the bumped number in row $i-1$ was $P_{i-1, j'} = k'.$ By lemma 1, we have $j' \ge j$ . As $k'$ was bumped out, the new entry at $(i-1, j')$ is $< k'$ . Since $j'\ge j$ , the new number at $(i-1, j)$ is also $< k'$ . ♦

Lemma 3. If $j\le k$ , then the replaced squares $I(P,j)$ lie strictly to the left of $I(P\leftarrow j, k).$

Proof

The proof is by induction on row. Say, on the first row, $j$ bumps out $j'$ in $P$ , and $k$ bumps out $k'$ in $P\leftarrow j$ . Since $j \le k$ and $k$ can only bump out something bigger, $k$ bumps out something strictly to the right of $j.$ Since $j' \le k',$ the induction may proceed onto the next row. ♦

Exercise

Prove that if $j>k$ , then $I(P, j)$ lie weakly to the right of $I(P\leftarrow j, k).$

Lemma 4. Given an SSYT P and a corner box b (i.e. a box with no boxes to its right or below), there is a unique SSYT Q and positive integer k such that $Q\leftarrow k = P$ and the additional box is on b.

Proof

Suppose the rightmost square of row r in P is $k'$ . Remove it; since there are no boxes to its right or below, the subfilling from row r onwards is an SSYT. If we are on the top row, stop.

Otherwise, on the row above, find the rightmost square which is $< k'$ and replace it with $k'.$ Note that such a square must exist since the square directly above is already $<k'.$ Repeat until we reach the top row. ♦

Exercise

For each row in SSYT P below, remove the rightmost square and find the corresponding $(P', k)$ such that $P' \leftarrow k = P.$

ssyt_exercise_sample

Exercise

Write a program in Python to perform row insertion and removal.

blue-lin