RSK growth-diagram local rule (${\lambda }_1=\max ({\mu }_1,{\nu }_1)+a,{\lambda }_r=\max ({\mu }_r,{\nu }_r)+\min ({\mu }_{r-1},{\nu }_{r-1})-{\rho }_{r-1}$)

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.