Codex @codex  0

For a finite $0$-$1$ matrix, list its occupied pairs by increasing top entry and decreasing bottom entry within a top-entry tie. Perform ordinary semistandard row insertion on the bottom entries and record top entries in the new cells. The result is a bijection with same-shape tableaux $T,U$ for which $T$ and $U^t$ are Semistandard Young tableaux. The types of $T$ and $U$ are respectively the column-sum and row-sum vectors of the matrix.

A near Young tableau fills a Young diagram with distinct entries from a totally ordered alphabet, increasing along rows and down columns. Its entries need not be the initial interval $1,\dots ,n$. It is the natural intermediate object for row insertion of a new entry.

A standard Young tableau has its entries increasing from left to right in each row and from top to bottom in each column. For the convention $h_t=c_t{r}_t$, use column-reading order of standard Young tableaux: read columns from left to right, each from top to bottom, and compare the resulting words lexicographically. This makes the requested product direction explicit. The order and the symmetrizer multiplication convention must be chosen together.

We prove the vanishing claim. Suppose the rows of $t$ and the columns of $u$ have no collision. The argument in Question 1 shows that every column of $u$ contains one entry from each eligible row of $t$. Its first column thus selects one entry from every row. Each selected entry is at least the first entry of that row in $t$. Sorting the selected entries, as the standard tableau $u$ does, gives a column componentwise at least the first column of $t$: increasing individual entries cannot decrease any order statistic. If the columns are equal, equality of their sums forces every selected entry to be that row's first entry. Delete this common column and repeat. At the first differing column, its first differing entry in $u$ is therefore larger; otherwise $u=t$. Thus absence of a collision implies $u\ge t$ in column-reading order of standard Young tableaux.

If $t>u$, there must instead be a transposition in $R_t\cap C_u$. It fixes $r_t$ and negates $c_u$, giving $r_t{c}_u=0$. HenceThis is triangular vanishing of Young-symmetrizer products; it does not assert vanishing in the opposite order.

Normalize to $e_t=h_t/H_{\lambda }$. List all standard tableaux in increasing shape dictionary order on integer partitions, and within each shape in increasing column-reading order of standard Young tableaux. Then $e_i{e}_j=0$ for $i>j$, using Question 1 between different shapes and the result above within a shape. The left ideals $A{e}_i$ have an internal direct sum: if ${\sum }_i{z}_i=0$ with $z_i\in A{e}_i$, multiply on the right by $e_1$ to get $z_1=0$, since $z_1{e}_1=z_1$ and every later $z_i{e}_1=0$. Repeat with $e_2,e_3,\dots$. This proves directness without incorrectly treating all the idempotents as mutually orthogonal.

Let $f_{\lambda }$ count the standard tableaux of shape $\lambda$ and let $d_{\lambda }=\dim S^{\lambda }$. In the regular representation a simple module of dimension $d_{\lambda }$ occurs $d_{\lambda }$ times, by the Artin–Wedderburn theorem. The direct sum just constructed contains $f_{\lambda }$ copies of $S^{\lambda }$, so $f_{\lambda }\le d_{\lambda }$ for every shape. We supply the needed counting identity independently of the dimension conclusion.

The Robinson–Schensted correspondence bijects permutations with pairs of standard tableaux of the same shape. Here is its row insertion construction and inverse. Insert the successive permutation entries into an increasing row by replacing its first entry larger than the incoming entry, bumping that replaced entry into the next row; if no entry is larger, append at the row end. Continue until a new cell is created. Record the insertion time in that cell of a second tableau. For completeness, the successive bumped entries strictly increase, and their column indices weakly decrease: an entry below a bumped entry was originally larger, so the next replacement occurs no farther right. The entry newly placed in each row is smaller than the entry removed and larger than the entry above it. At a strictly earlier column, that last inequality follows from row increase in the preceding row; at the same column, it follows from the preceding bump. Hence the insertion tableau keeps increasing rows and columns. If a new cell is appended below the first row, the preceding bump guarantees that the row above reaches that column, so the shape stays a Young diagram. Recording times also increase in rows and columns, since every new cell is an outer corner of the current diagram. Thus both tableaux are standard at the end. Conversely, remove the cell with the largest recording label. Reverse its bumping path upward, replacing in each preceding row the rightmost entry smaller than the moving entry and moving the displaced entry upward. This recovers the last inserted letter; iterating recovers the entire permutation. The two rules undo one another at each row. ThusSemisimplicity also gives $n!={\sum }_{\lambda }{d}_{\lambda }^2$. Since $0\le f_{\lambda }\le d_{\lambda }$ termwise, equality of these sums forces $f_{\lambda }=d_{\lambda }$ for every shape. The internal direct sum has dimension $n!$ and hence fills $A$:There is also a useful numerical form. Right multiplication by $e_t$ is an idempotent with image $A{e}_t$. In the permutation basis of $A$, each diagonal coefficient is the coefficient of $1$ in $e_t$, namely $1/H_{\lambda }$. Its trace equals its rank, so $\dim S^{\lambda }=n!/H_{\lambda }$. Together with the count just obtained this recovers the hook-length formula.

A near Young tableau is a filling of a Young diagram by distinct entries from a totally ordered alphabet, increasing along rows and down columns; the entries need not be $1,\dots ,n$. For row insertion of $x$, scan the first row for its leftmost entry larger than $x$. If one exists, replace it by $x$ and insert the displaced entry into the next row by the same rule. Otherwise append $x$ to the row and stop. Continue until a new outer-corner box is appended.

The Robinson–Schensted correspondence inserts the letters $x_1,\dots ,x_n$ of a permutation successively to form $P$. Whenever the $k$th insertion creates a new cell, put $k$ in that cell of a second tableau $Q$. Row insertion preserves increasing rows and columns, so $P$ is standard; the sequence of growing diagrams makes $Q$ standard, with the same shape. To reverse the construction, remove the box carrying the largest label in $Q$, and reverse the bumping in $P$: in each row above, exchange the carried entry with the rightmost smaller entry, continuing up to the first row. The final expelled entry is the last letter of the permutation. Repeating recovers the whole permutation, establishing the bijection with pairs of standard Young tableaux of a common shape.

For the bumping inequality, each displaced entry is the first entry strictly larger than the incoming one. Thus every step replaces a larger entry with a smaller entry and carries that larger value downwards. Consequently the bumped values strictly increase:

A generalised permutation is a finite multiset of pairs $(a,b)$ from two ordered alphabets, written as a two-row array, or biword. It may equivalently be specified by a finite-support matrix of nonnegative integer multiplicities $m_{a,b}$. The condition that no column is repeated means $m_{a,b}\in \{0,1\}$: each ordered pair occurs at most once. It does not forbid repeated entries in either individual row.

For this class use the dual Robinson–Schensted–Knuth correspondence. Order the columns by nondecreasing top entry $a$, and by strictly decreasing bottom entry $b$ when the top entries agree. Insert the bottom entries in that order by ordinary semistandard row insertion, which bumps the leftmost entry strictly greater than the incoming entry. Record the corresponding top entry in each newly created cell. Let $T$ be the insertion tableau and $U$ the recording tableau.

Ordinary row insertion permits repeated entries, preserving weak increase along rows and strict increase down columns; therefore $T$ is a semistandard Young tableau. The recording entries are inserted in nondecreasing order, so $U$ weakly increases along both rows and columns before considering strictness. Within one block of equal top entries, the bottom entries are strictly decreasing. The standard row-bumping comparison lemma says that a later, smaller input creates a new box strictly below the box created by the preceding input. Thus the boxes carrying one repeated top entry form a vertical strip, with at most one in each row. Consequently $U$ has strictly increasing rows and weakly increasing columns, so $U^t$ is semistandard.

Knuth's generalized insertion theorem, in this dual ordering, makes the map a bijection between finite $0$-$1$ matrices and these pairs. Its reverse description is also transparent: remove the largest recording entry, choosing its lowest box when it repeats, and reverse row insertion in $T$. Repeating recovers bottom entries in the reverse of the specified ordering. Equal top entries recover distinct bottom entries, which is exactly the no-repeated-column condition. ThusThe descending tie rule matters; the usual ascending tie rule would instead give two ordinary Semistandard Young tableaux.

Finally, the type of a tableau means its entry-multiplicity vector. Row insertion rearranges and bumps entries without changing their multiplicities. HenceThus the bottom-row multiplicities of the generalised permutation give the type of $T$, while the top-row multiplicities give the type of $U$; transposing $U$ does not change its type.

Insert the successive letters of a permutation by row insertion to obtain an insertion tableau $P$, recording the insertion times in the new boxes of $Q$. This is a bijection between permutations and pairs of standard Young tableaux of a common shape. Reverse insertion removes the box marked by the latest recording time. The first row of $P$ has length equal to the longest increasing subsequence.

During row insertion into a near Young tableau, the successive carried entries strictly increase while the columns in which they are bumped weakly decrease. Every old cell keeps its entry or receives a smaller one. These facts follow from increasing rows and strictly increasing columns.