Robinson–Schensted–Knuth correspondence

Remarks

The insertion rule is the one of the Robinson–Schensted correspondence: an inserted entry $x$ bumps the leftmost entry of the row that is strictly larger than $x$. Equal first coordinates are listed with increasing second coordinates, so the recording tableau stays semistandard. For a permutation matrix the construction gives back the Robinson–Schensted correspondence.

Example: for $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ the pairs are $(1,1), (1,2), (2,2)$. Inserting $1, 2, 2$ gives $P = \begin{smallmatrix} 1 & 2 & 2 \end{smallmatrix}$, and $Q = \begin{smallmatrix} 1 & 1 & 2 \end{smallmatrix}$. The column sums $1, 2$ of $A$ match the content of $P$, and the row sums $2, 1$ match the content of $Q$.

Going deeper

For a student

Summing over all matrices with weight $\prod_{i,j} (x_i y_j)^{a_{ij}}$ gives the Cauchy identity $$\prod_{i=1}^{m} \prod_{j=1}^{n} \frac{1}{1 - x_i y_j} = \sum_{\lambda} s_\lambda(x_1, \dots, x_m) \, s_\lambda(y_1, \dots, y_n),$$ where $s_\lambda$ is the Schur polynomial. Part 4 applied to symmetric matrices gives similar identities for $\sum_\lambda s_\lambda$. The correspondence is due to Knuth, and it is the main bijective tool in the theory of symmetric functions.