For now, we will switch gears and study the combinatorics of the matrices and where run over all partitions of d>0. Eventually, we will show that there is a matrix K such that:
where J is the permutation matrix swapping and its transpose. To achieve that, we will need to digress a little.
Let be any partition; we will use a Young diagram for comprising of boxes. A filling of 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
If the following are examples:
is called the shape of a filling, while the tuple where 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.
Given an SSYT P and positive integer k, we write for the filling which has 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, is always an SSYT (to be proved later).
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.
For convenience, we let denote the set of squares whose contents were replaced (or added). Each square is denoted by , where i is the row number and j is the column number. In the above example, we obtain:
Lemma 1. The replaced squares move to the left (weakly) as we proceed down the rows, i.e. if , then
Suppose ; consider the square directly below it. Either it is or it does not exist. In the latter case, we do not worry about In the former case, since is larger than the bumping number no square after can be bumped. ♦
Lemma 2. The resulting is a semistandard Young tableau.
By construction, the rows of are weakly increasing so we need to show that its columns are strictly increasing. Suppose bumps out ; since a number can only bump out something bigger, the number directly beneath (if it exists) is
What about the number above ? Suppose the bumped number in row was By lemma 1, we have . As was bumped out, the new entry at is . Since , the new number at is also . ♦
Lemma 3. If , then the replaced squares lie strictly to the left of
The proof is by induction on row. Say, on the first row, bumps out in , and bumps out in . Since and can only bump out something bigger, bumps out something strictly to the right of Since the induction may proceed onto the next row. ♦
Prove that if , then lie weakly to the right of
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 and the additional box is on b.
Suppose the rightmost square of row r in P is . 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 and replace it with Note that such a square must exist since the square directly above is already Repeat until we reach the top row. ♦
For each row in SSYT P below, remove the rightmost square and find the corresponding such that
Write a program in Python to perform row insertion and removal.