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.

Use nonnegative integer matrix entries, including zero, and English Young diagram conventions: rows run left to right and columns run down. Replace $A$ by a two-line array containing $a_{ij}$ copies of $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$, sorted lexicographically by upper letter $i$ and then lower letter $j$. Finite support makes the array finite.

In the RSK algorithm, insert each lower letter $j$ into $P$ by row insertion. In the first row replace the leftmost entry strictly greater than $j$, carrying the replaced entry into the next row; if there is no such entry, append $j$ and stop. Repeat in subsequent rows until a new cell is made. Put the upper letter $i$ in that new cell of the recording tableau $Q$.

The insertion-path facts used here are the following: row insertion preserves weak rows and strict columns; inserting $u$ followed by $v\ge u$ puts the latter new cell strictly to the right of the former; reverse insertion undoes insertion; and the reverse paths from a right-to-left horizontal strip recover its input letters in weakly decreasing order. These standard path facts ensure that $P$ is a semistandard Young tableau. The upper letters are nondecreasing, so the entries of $Q$ are weakly increasing in rows. Equal upper letters have sorted lower letters, and hence create a horizontal strip; they cannot occupy the same column. Thus $Q$ is also a semistandard Young tableau, of exactly the same shape as $P$.

Here is the inverse on any such pair. Select a largest entry $i$ in $Q$, and among the cells carrying it select the rightmost one. It is an outer corner: there can be no larger entry below it, and any entry to its right would be another maximal entry farther right. Delete that cell from $Q$ and reverse-insert the value at its cell in $P$. In each preceding row replace the rightmost entry strictly smaller than the carried value and carry that old entry upward. The value emerging from the first row is $j$. Record $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$ and repeat. Equal maximal entries form a horizontal strip, so the reverse-path fact gives their $j$'s in weakly decreasing order. Reversing the recovered list therefore gives exactly a lexicographically sorted two-line array. The procedures are mutually inverse, proving the RSK correspondence bijection, including the zero matrix and the pair of empty tableaux.

Insertion only moves previous entries and adds one copy of its new letter; recording adds one copy of its upper letter. Consequently

For the trace assertion, use the insertion-path form of the RSK growth-diagram local rule. Let $\rho ,\mu ,\nu ,\lambda$ be the shapes from the northwest, northeast, southwest and southeast matrix prefixes around entry $a_{ij}$. Padding row lengths with zeros, the rule isThis local rule counts the two merging insertion paths row by row: the entry supplies the initial carry, the longer extension supplies the current row, and the overlap of the extensions beyond $\rho$ is bumped to the next row. It is a standard insertion-path fact being used in addition to the preceding monotonicity statements.

Define $o(\gamma )={\gamma }_1-{\gamma }_2+{\gamma }_3-\cdots$. Each column of the Young diagram contributes its alternating vertical sum, which is one for odd length and zero for even length. Thus $o(\gamma )$ counts odd-length columns. For symmetric $A$, transposition symmetry of RSK gives equal shapes for the two prefixes off the diagonal, so $\mu =\nu$ at entry $a_{ii}$. The rule becomesTaking alternating sums makes the two sums involving $\mu$ cancel, leavingStarting from the empty northwest corner and proceeding along the diagonal proves the trace and odd columns in symmetric RSK identityThis also accommodates arbitrary diagonal entries, rather than only permutation matrices.

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.

List each pair $(i,j)$ with multiplicity $a_{ij}$, sorted first by $i$ and then by $j$. Apply row insertion to the lower letters $j$, and record the upper letters $i$ in the new cells. The row insertion comparison is strictly greater than the carried entry. The result is a pair of Semistandard Young tableaux of the same shape. Reverse insertion removes the rightmost cell containing the largest recording entry, then replaces the rightmost strictly smaller entry in each preceding row. It reconstructs the ordered list, proving the bijection. The insertion and recording contents are respectively the column sums and row sums of $A$.

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.