Permuting the rows in ascending order first and then the columns of any Young tableau gives a standard Young tableau

Question

Show that if you take any Young tableau and permute the rows in ascending order first and then the columns in ascending order (or columns first and then row), then you get a standard Young tableau.

I considered this (arbitrarily chosen) example to start with- \begin{array}{rrrrrrrrr} 8 &&4 &&9 &&15 &&5\\ 17 &&16 &&14 &&2 &&13\\ 6 &&18 &&7 &&19\\ 11 &&1 &&20\\ 12 &&22\\ 3 &&10\\ 21 \end{array} Arranging each row in ascending order first gives the following tableau- \begin{array}{rrrrrrrrr} 4 &&5 &&8 &&9 &&15\\ 2 &&13 &&14 &&16 &&17\\ 6 &&7 &&18 &&19\\ 1 &&11 &&20\\ 12 &&22\\ 3 &&10\\ 21 \end{array} Now, arranging each column of this in ascending order gives the following tableau- \begin{array}{rrrrrrrrr} 1 &&5 &&8 &&9 &&15\\ 2 &&7 &&14 &&16 &&17\\ 3 &&10 &&18 &&19\\ 4 &&11 &&20\\ 6 &&13\\ 12 &&22\\ 21 \end{array} which is clearly a standard Young tableau.

But, I don't have any idea on how to prove that it will hold for any tableau.

This problem was given by our professor at the end of his lecture on Hook Length formula. So, this formula may be useful for the problem, although I don't see how they even vaguely connect. If not this formula, then maybe a key lemma used in the proof will be helpful-

Let the hook numbers of the hook of the $(i,j)$-th element be $h_{i,j}, h_{i,j+1},\dots h_{i,\alpha_i}$ along the row of the hook and $h_{i,j}, h_{i+1,j},\dots h_{\beta_j,j}$ along the column. Then, the numbers $h_{i,j}, h_{i,j+1},\dots h_{i,\alpha_i},h_{i,j}-h_{i+1,j},\dots h_{i,j}-h_{\beta_j,j}$ form a partition of $1,2,\dots h_{i,j}$.

However, I should also mention that our professor is notorious enough for this problem to have no connection with the lecture at all.

Note: If anyone knows how to draw a Young tableau with gridlines and borders, please place an edit.

Answer 1

Some ideas

Look at the obtained Young Tableau. Try characterizing its $(i,j)$-th element in terms of the elements of the initial Young tableau.

It is the $i$-th smallest element among all elements each of which is the $j$-th smallest element of some row in the initial Young tableau.

It is also the largest element in the upper left $i\times j$ matrix, in which each element is the $t$-th smallest element of some row in the initial Young tableaus where $t\le i$.

A proof

Let $B$ denote the Young tableau after arranging each row in ascending order.
Let $C$ denote the Young tableau after arranging each column of $B$ in ascending order.
The question is how we can prove $C$ is a standard Young tableau.

Since each column of $C$ comes from sorting the corresponding column of $B$, each column of $C$ is sorted.

Consider element $C_{i,j}$ and $C_{i,k}$ on the $i$-th row of $C$, where $j<k$. Since $C_{i,k}$ is the $i$-th smallest element in the $k$-th column of $B$, there are $i$ elements in the $k$-th column of $B$ that are at most than $C_{i,k}$. Supposed they are $B_{t_1,k}$, $B_{t_2,k}$, $\cdots$, $B_{t_i,k}$.

• Since the $t_1$-th row of $B$ is sorted, $B_{t_1,j}<B_{t_1,k}$.
• Since the $t_2$-th row of $B$ is sorted, $B_{t_2,j}<B_{t_2,k}$.
• $\vdots$
• Since the $t_i$-th row of $B$ is sorted, $B_{t_i,j}<B_{t_i,k}$.

Hence, $B_{t_1,j}$, $B_{t_2,j}$, $\cdots$, $B_{t_i,j}$ are smaller than $C_{i,k}$. In other words, $i$ elements in the $j$-th column of $B$ are smaller than $C_{i,k}$. So must be the $i$-th smallest element in the $j$-th column of $B$. That is, $C_{i,j}< C_{i,k}$. We have proved each row of $C$ is sorted.