Robinson-Schensted-Knuth correspondence ($A⟷(P,Q)$)

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$.

If a standard Young tableau of shape $(n-1,1)$ has second-row entry $a$, then its self-pair under RSK corresponds to the adjacent transposition $(a-1,a)$. Inserting the word $1,\dots ,a-2,a,a-1,a+1,\dots ,n$ first appends increasing entries to the first row. At time $a$, inserting $a-1$ bumps $a$ into the unique second-row cell. Every later entry appends to the first row. Thus the insertion tableau is the stated tableau, and the recording tableau has its second-row label $a$ as well. This proves the correspondence directly, including $n=2$, without invoking a separate theorem about involutions.

At one matrix entry $a$, let $\rho ,\mu ,\nu ,\lambda$ be the shapes of the northwest, northeast, southwest and southeast matrix prefixes under the RSK correspondence. The displayed row-length recurrence expresses merged insertion paths: the new entry supplies the first-row carry, and the overlap of the two incoming row extensions beyond the northwest shape is bumped into the next row. Zero boundary shapes determine the whole diagram. Transposing the matrix exchanges $\mu ,\nu$, leaving the rule invariant.

For a symmetric nonnegative integer matrix, the two neighboring prefix shapes along the diagonal are equal. In the RSK growth-diagram local rule, set $\mu =\nu$ and take alternating sums of row lengths. The two occurrences of the alternating sum of $\mu$ cancel, leaving $o(\lambda )=o(\rho )+a_{ii}$. Induction along the diagonal proves the formula. Each column contributes one to this alternating sum exactly when its length is odd.