= Solution
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 $\binom ij$, 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 $\binom ij$ 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
$$
\boxed{\operatorname{content}_j(P)=\sum_i a_{ij},
\qquad \operatorname{content}_i(Q)=\sum_j a_{ij}.}
$$
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 is
$$
\lambda_1=\max(\mu_1,\nu_1)+a_{ij},\qquad
\lambda_r=\max(\mu_r,\nu_r)+\min(\mu_{r-1},\nu_{r-1})-\rho_{r-1}\quad(r\ge2).
$$
This 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 becomes
$$
\lambda_1=\mu_1+a_{ii},\qquad
\lambda_r=\mu_r+\mu_{r-1}-\rho_{r-1}.
$$
Taking alternating sums makes the two sums involving $\mu$ cancel, leaving
$$
o(\lambda)=o(\rho)+a_{ii}.
$$
Starting from the empty northwest corner and proceeding along the diagonal proves the <trace and odd columns in symmetric RSK> identity
$$
\boxed{\operatorname{tr}A=o(\operatorname{shape}P)
=\#\{\text{odd-length columns of }P\}.}
$$
This also accommodates arbitrary diagonal entries, rather than only <permutation matrices>.
Back to article page
