The RSK correspondence for two-line arrays

Extend row insertion to weak rows and strict columns using the stated leftmost-strictly-greater rule. Carried labels strictly increase whenever a bump occurs. Route positions weakly decrease: if the old entry $x_{i+1}$ at position $r_i$ of row $i$ has a box below it, that box has value $>x_{i+1}$ by column strictness, so the next leftmost-exceeding position is at most $r_i$; if no such box exists, the next row has length $<r_i$ and its bump or append position is again at most $r_i$. Only finitely many occupied rows can be visited, so the process terminates at an append box, which is addable: if it lies in row $s>1$, then ${\lambda }_s+1=r_s\le r_{s-1}\le {\lambda }_{s-1}$. Exactly one box is added and the entry multiset gains the inserted letter.

Reverse deletion also works for semistandard tableaux. Remove a corner $(s,t)$ and carry its old value upward. If the carried value from row $i+1$ is $z$, choose the rightmost entry $a<z$ in row $i$ and replace it by $z$, carrying $a$ upward. Such an entry exists at the column of the just-removed or replaced cell in row $i+1$, by strictness of the column before that lower change; the chosen column is at least that lower column. The row remains weak, since entries left of the chosen cell are $\le a<z$ and entries to its right are $\ge z$. The upper neighbour is smaller than the old value $a<z$. Any remaining lower neighbour is larger than $z$: in the lower row the preceding reverse step replaced its carried value by a strictly larger value, and all entries to its right are at least that larger value; at the first removed corner there is no lower neighbour to its right. At the next upward replacement, the value placed above the current changed row is smaller than its carried $z$, so strictness is preserved throughout. Thus deletion terminates with a semistandard tableau and removes one occurrence of the expelled letter, which may still occur elsewhere.

For transpose interchange define a directed graph on the labelled occurrences of pairs $(u,v)$: for unequal pairs draw an arc when both coordinates weakly increase, and order occurrences of an identical pair by their original occurrence index, drawing forward arcs between them. Lexicographic order is a topological order, so the graph is acyclic. Divide it into source layers $C_1,\dots ,C_d$ by successively removing all sources. A vertex lies in $C_l$ exactly when the longest path ending there has $l-1$ arcs, by induction on a topological order. Within a layer the first coordinates strictly increase and the second strictly decrease when vertices are listed by first coordinate: equal coordinates or simultaneous weak increase would give an arc and different layers. Write $C_l=((u_{l1},v_{l1}),\dots ,(u_{l{n}_l},v_{l{n}_l}))$ in that order.

The output is semistandard. At a replaced box in row $i$, left entries are $\le x_i$ and right entries are at least the old displaced value $x_{i+1}>x_i$. For its upper neighbour, if $r_i=r_{i-1}$ the new value above is $x_{i-1}<x_i$; if $r_i<r_{i-1}$, the unchanged entry above lies left of the previous leftmost-exceeding position and is $\le x_{i-1}<x_i$. Its lower neighbour is either the new carried value $x_{i+1}>x_i$ if the next bump is in that column, or an unchanged value exceeding the old displaced value by column strictness. The same upper-neighbour argument applies at the appended box, whose row has all prior entries $\le x_s$ and which has no box below. Hence rows stay weak and columns stay strict, including at equal input letters.

These extended procedures are inverse. Along an insertion route, the resulting row has at its chosen position $x_i<x_{i+1}$, entries to the left $\le x_i$, and entries to the right $\ge x_{i+1}$; hence reverse deletion carrying $x_{i+1}$ chooses exactly that position and restores its old entry. Inducting upward from the appended box restores the input tableau. Conversely, a reverse step replacing $a$ by $z>a$ leaves all entries to its left $\le a$ and entries to its right $\ge z$, so reinserting $a$ chooses precisely that cell and bumps $z$. Inducting downward restores the original tableau and corner. This proves both directions without requiring the expelled value to disappear from the entry set.

Compare successive insertions of $x\le x^{\mathrm{\prime }}$. On every common row, their carried values satisfy $x_i\le x_i^{\mathrm{\prime }}$ and their positions satisfy $r_i<r_i^{\mathrm{\prime }}$: after the first replacement, all entries up to $r_i$ are $\le x_i\le x_i^{\mathrm{\prime }}$, so the second bump or append is to its right. If both bump, the second displaced value is at least the first displaced value, by the old weak row order, proving the carried-value induction. The second insertion stops no lower than the first: at the first process's append row its own position would be to the right of that append, so it must append there if it has not already stopped. Its new column $t^{\mathrm{\prime }}$ is strictly larger than the first new column $t$: in the same row it appends one cell further right; in a higher row, that old row length is at least $t$ by addability of the first appended box, so its append column is at least $t+1$.

For successive $x>x^{\mathrm{\prime }}$, the carried values satisfy $x_i>x_i^{\mathrm{\prime }}$ and positions satisfy $r_i^{\mathrm{\prime }}\le r_i$ on common rows. At row $1$ the second process meets a value exceeding $x^{\mathrm{\prime }}$ at or before the first chosen position, whose new value is $x>x^{\mathrm{\prime }}$. If it bumps before that position, the bumped old value is $\le x_i<x_{i+1}$ by the first leftmost-exceeding choice; if at that position, it bumps $x_i<x_{i+1}$. This proves the strict carried-value induction. At the first append row the smaller carried value bumps an entry at or before that append instead of stopping, so the second insertion ends strictly lower. Its final column $t^{\mathrm{\prime }}$ is at most $t$, since its position in the first append row is at most $t$ and subsequent route positions weakly decrease.

Construction A produces semistandard $P$ by step 2.1. Its contents and shape follow from step 1.1. The rows of $Q$ are weakly increasing because boxes are appended at row ends and the chronological labels $u_k$ weakly increase. A lower box in a column is created later, so its label is at least the upper label. All equal labels form a consecutive block of insertions, whose inputs $v_k$ weakly increase; step 3.1 makes their new columns strictly increase at every adjacent step, hence throughout that block. Equal labels therefore never share a column, and $Q$ has strictly increasing columns. Both contents and the common shape are as stated.

Construction B is defined on any semistandard pair. A rightmost maximum entry of $Q$ has no cell to its right, since that would be a larger or an equal maximum further right, and no cell below, since columns are strict. It is thus removable. Maximum entries occupy distinct columns. Removing the rightmost one leaves semistandard $Q$, and step 1.2 allows reverse deletion in $P$ at the same corner. Repeating yields expelled letters $v_N,\dots ,v_1$ and labels $u_N\ge \cdots \ge u_1$. Step 2.2 ensures that forward reinsertion rebuilds the tableaux and chosen boxes. Within each equal-label deletion block the removed columns strictly decrease, so the rebuilding insertion columns strictly increase. The contrapositive of step 3.2 then gives $v_k\le v_{k+1}$ when $u_k=u_{k+1}$. The recovered array is therefore lexicographically ordered.

For a pair produced by A, its final label block has strictly increasing insertion columns by step 3.1; the last-created box is its rightmost maximum box. Step 2.2 recovers its last input letter, and induction recovers all columns, so $B\circ A$ is the identity. For an arbitrary pair, step 4.2 and the other inverse direction in step 2.2 give $A\circ B$ as the identity. Thus the first assertion is a bijection, including the empty array and empty pair, where no operation is performed.

The first row of $P$ consists of $v_{1n_1},\dots ,v_{d{n}_d}$, and the first row of $Q$ of $u_{11},\dots ,u_{d1}$. Moreover, the events which touch first-row position $l$ are exactly the successive vertices of $C_l$. Prove this simultaneously by induction on the array length. Adding the next lexicographic pair $(u,v)$ introduces no outgoing arc. A layer has a predecessor of that vertex exactly when its minimum second coordinate $v_{l{n}_l}$ is $\le v$; hence the vertex's layer is $r=1+\max \{l:v_{l{n}_l}\le v\}$, with empty maximum $0$. By the induction hypothesis these minima are the weakly increasing entries of the first row. Thus insertion of $v$ replaces exactly position $r$, or appends there if $r=d+1$. In an existing layer its first coordinate is strictly greater than the previous member's and its second strictly smaller, since it has no predecessor in that layer; it becomes that layer's last member. Appending a new layer writes its first label $u$ in row one of $Q$, while replacement changes no existing $Q$ label. This proves every assertion of the induction.

The first-row bumped pairs are exactly $(u_{l,i+1},v_{li})$ for $1\le i<n_l$, across all layers. They appear chronologically in lexicographic order: bumping labels $u$ weakly increase; within one equal-label input block step 3.1 makes first-row positions strictly increase, and the entries bumped at those successively rightward positions weakly increase, because earlier replacements in that block occur to their left. Consequently the lower rows of both tableaux are obtained by applying A to this bump array. Row two is its first row, since the labels are written precisely when that bumped letter's lower-row insertion appends. Repeat this procedure for each successive row. The bump array has $N-d<N$ columns whenever $N>0$, so the recursion terminates.

Swapping coordinates gives an isomorphism of the two initial graphs, using the same order for occurrences of identical pairs. The source layers are the same sets of occurrences, but their within-layer order reverses: the old second coordinates strictly decrease, so the swapped first coordinates increase in the reverse order. The first-row formulas of step 5.2 therefore swap $P$ and $Q$. More importantly, the shifted pairs from a layer of the swapped graph are $(v_{li},u_{l,i+1})$ for $i=n_l-1,\dots ,1$, exactly the coordinate swaps, as a multiset, of the original bump pairs $(u_{l,i+1},v_{li})$. After lexicographic sorting their bump arrays are transposes of one another. Identical pairs can again be ordered correspondingly; changing the order of identical occurrences does not change the labelled array or insertion. Thus induction on $N$, using the smaller bump arrays in step 6.1, swaps every lower row as well. This proves that the transposed array corresponds to $(Q,P)$.

When $u_k=k$, all labels in $Q$ are distinct, and its semistandardness from step 4.1 makes it standard by [F2]. Construction A is precisely word insertion with chronological recording labels; the bijection of step 5.1 and transpose interchange of step 7.1 give all the commissioned assertions. No Choice is used: every procedure, maximum, ordering and induction here is finite and canonical, with identical pairs ordered by occurrence.