RSK via local transformations
Sam Hopkins · 2025
Read RSK via local transformations by Sam Hopkins (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22082.txt.
Introduction
Sam Hopkins explains a cornerstone of combinatorics, the Robinson-Schensted-Knuth correspondence, through small local moves called toggles. The correspondence links permutations and other objects to pairs of number tableaus and quietly powers results across algebra and probability. Its usual definition can feel like a magic trick performed row by row.
Hopkins rebuilds the definition from local transformations, so the global correspondence emerges from simple switches applied in the right pattern. The note grew out of presentations by Alex Postnikov, was written in two thousand fourteen, and circulated privately for years before being posted to the arXiv for preservation. As a teaching-flavored exposition, it offers specialists and students a more mechanical, transparent way to see why the correspondence works.
Catalog record
| CREATOR | Sam Hopkins |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22082
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RSK via local transformations Sam Hopkins Abstract 1. Introduction The Robinson–Schensted–Knuth correspondence is a map from n\times n \mathbb{N} -matrices (i.e., matrices with nonnegative integer entries) to pairs of semi-standard Young tableaux of the same shape. For basic definitions of and background on tableaux and the RSK algorithm, see [ 19 , Ch. 7] . Abstractly, we may regard RSK as a bijection \displaystyle\{\textrm{$n\times n$ $\mathbb{N}$-matrices}\} \displaystyle\xrightarrow{RSK}\left\{\parbox{216.81pt}{\begin{center}$(P,Q)\colon P,Q\textrm{ are SSYT with }\mathrm{sh}(P)=\mathrm{sh}(Q)$ \\ {and whose entries are in $[n]:=\{1,\ldots,n\}$} \end{center}}\right\} \displaystyle A \displaystyle\xmapsto{RSK}(P,Q) with the property that \mathrm{type}(P)=\mathrm{col}(A) and \mathrm{type}(Q)=\mathrm{row}(A) . Here for a SSYT T with entries in [n] , the type of T is defined to be \mathrm{type}(T):=(\mathrm{type}(T)_{1},\ldots,\mathrm{type}(T)_{n}), where \mathrm{type}(T)_{i}:=\textrm{the number of entries of $T$ equal to $i$}, and for a n\times n \mathbb{N} -matrix B=(b_{ij}) the column and row sums of B are \displaystyle\mathrm{col}(B) \displaystyle:=(\mathrm{col}(B)_{1},\ldots,\mathrm{col}(B)_{n}):=(\sum_{i=1}^{n}b_{i1},\ldots,\sum_{i=1}^{n}b_{in}) \displaystyle\mathrm{row}(B) \displaystyle:=(\mathrm{row}(B)_{1},\ldots,\mathrm{row}(B)_{n}):=(\sum_{i=1}^{n}b_{1i},\dots,\sum_{i=1}^{n}b_{ni}). RSK is normally defined in terms of a somewhat complicated procedure called row-insertion. This definition unfortunately masks the remarkable symmetry property that if A\xmapsto{RSK}(P,Q) then A^{t}\xmapsto{RSK}(Q,P) . Here we present an alternate description of RSK via local transformations that makes the symmetry obvious. Our approach is thus similar in spirit to the growth diagrams of Fomin [ 6 ] . In order to motivate this description, we first examine the Gelfand-Tsetlin patterns associated to the Young tableaux that result from RSK, and show how RSK can be thought of as a map between matrices. Definition 1 . A Gelfand-Tsetlin pattern is a triangular array of nonnegative integers \begin{array}[]{c}g_{1,1}\qquad\qquad g_{1,2}\qquad\qquad g_{1,3}\qquad\qquad\cdots\qquad\qquad g_{1,n}\\ g_{2,2}\qquad\qquad g_{2,3}\qquad\qquad\cdots\qquad\qquad g_{2,n}\\ g_{3,3}\qquad\qquad\cdots\qquad\qquad g_{3,n}\\ \ddots\qquad\qquad\qquad\iddots\\ g_{n,n}\end{array} such that g_{i,j}\geq g_{i+1,j+1}\geq g_{i,j+1} for all 1\leq i\leq j\leq n-1 . Gelfand-Tsetlin patterns with n rows are in bijection with semi-standard Young tableaux with entries among [n] in a natural way, as explained below. (There seems to be no consensus in the literature about how Gelfand-Tsetlin patterns are indexed so we are merely choosing one convention here.) Suppose A\xmapsto{RSK}(P,Q) . We associate an n -row Gelfand-Tsetlin pattern to P , denoted GT(P) , as follows. Define the series P^{1},\ldots,P^{n} of SSYT by • P^{1}:=P ; • P^{i+1} is obtained from P^{i} by removing all entries of n+1-i . Then GT(P) is just the Gelfand-Tsetlin pattern whose i -th row is \mathrm{sh}(P^{i}) . We define GT(Q) similarly. In other words, for a SSYT T with entries in [n] , we define GT(T) to be the Gelfand-Tsetlin pattern with n rows defined by g_{i,j}:=\textrm{number of entries $\leq n+1-i$ in row $j-i+1$ of $T$}. It is easy to check that the necessary inequalities on the entries hold. Note also that because \mathrm{sh}(P)=\mathrm{sh}(Q) , the first rows of GT(P) and GT(Q) are the same. So it is possible to glue GT(P) and GT(Q) along their first row to form a single n\times n \mathbb{N} -matrix that is weakly increasing in rows and columns. Formally, suppose GT(P)=(g_{ij}) and GT(Q)=(h_{ij}) ; then the matrix \widehat{A}=(\widehat{a}_{ij}) is given by \widehat{a}_{ij}:=\left\{\begin{array}[]{ll}g_{i-j+1,n+1-j}&\textrm{if $i\geq j$;}\\ h_{j-i+1,n+1-i}&\textrm{otherwise}.\end{array}\right. This series of combinatorial objects is best understood through an example. Example 2 . Suppose A=\begin{pmatrix}1&0&2\\ 0&2&0\\ 1&1&0\end{pmatrix}. Then A\xmapsto{RSK}\Bigg(P=\raisebox{-18.06749pt}{\hbox{}\hskip 0.0pt{\vbox{\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$1$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$1$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$2$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$2$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$2$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$3$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$3$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt}}\hskip 0.0pt},Q=\raisebox{-18.06749pt}{\hbox{}\hskip 0.0pt{\vbox{\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$1$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$1$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$1$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$3$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$2$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$2$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt\vbox{\hrule height=0.3pt\hbox{\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt\hbox to10.93333pt{\hfil$3$\hfil}\vrule height=8.74669pt,width=0.3pt,depth=2.18663pt}\hrule height=0.3pt}\vskip-0.3pt}}\hskip 0.0pt}\;\Bigg), and \displaystyle GT(P) \displaystyle={\begin{array}[]{c}4\qquad 2\qquad 1\\ 4\qquad 1\\ 2\end{array}} \displaystyle GT(Q) \displaystyle={\begin{array}[]{c}4\qquad 2\qquad 1\\ 3\qquad 2\\ 3\end{array}} so \widehat{A}=\begin{pmatrix}1&2&3\\ 1&2&3\\ 2&4&4\end{pmatrix}. Indeed, \widehat{A} is weakly increasing along rows and columns. \square We have built up a series of maps between combinatorial objects A\mapsto(P,Q)\mapsto(GT(P),GT(Q))\mapsto\widehat{A}. By ignoring the intermediary steps, we can really think of RSK as a map \displaystyle\{\textrm{$n\times n$ $\mathbb{N}$-matrices}\} \displaystyle\xrightarrow{RSK}\left\{\parbox{162.6075pt}{\begin{center}{$n\times n$ $\mathbb{N}$-matrices that are weakly} \\ {increasing in rows and columns} \end{center}}\right\} \displaystyle A \displaystyle\xmapsto{RSK}\widehat{A}. Because each intermediary step was bijective, it is clear that this map is a bijection. There are a few more properties of this map worth noting. First of all, the diagonal sums of \widehat{A} record information about the row and column sums of A . Definition 3 . For an n\times n \mathbb{N} -matrix B=(b_{ij}) and some i,j\in[n] , define the diagonal sum at entry (i,j) , denoted \mathrm{diag}_{B}(i,j) , to be \mathrm{diag}_{B}(i,j):=\sum_{k=0}^{\mathrm{min}(i,j)-1}b_{i-k,j-k}. Using the above notation, when A\xmapsto{RSK}\widehat{A} , we have for any i\in[n] \displaystyle\mathrm{diag}_{\widehat{A}}(n,i) \displaystyle=\sum_{k=1}^{i}\mathrm{col}(A)_{k}; \displaystyle\mathrm{diag}_{\widehat{A}}(i,n) \displaystyle=\sum_{k=1}^{i}\mathrm{row}(A)_{k}. To see why this is the case, observe that \mathrm{diag}_{\widehat{A}}(n,i) is just the sum of the entries in row (n+1)-i of GT(P) . But the sum of this row of GT(P) is the number of 1 ’s, 2 ’s, …, and i ’s in P . But this is just \sum_{k=1}^{i}\mathrm{type}(P)_{k} , and because \mathrm{type}(P)=\mathrm{col}(A) , the diagonal sum is as claimed. Similarly for Q and row sums. The final key property of our map is that if A\mapsto\widehat{A} then A^{t}\mapsto\widehat{A}^{t} , which follows from the above-mentioned symmetry property of the map to Young tableaux. To summarize, RSK is secretly a map A\xmapsto{RSK}\widehat{A} from n\times n \mathbb{N} -matrices to n\times n \mathbb{N} -matrices that are weakly increasing in rows and columns such that (a) the map is bijective; (b) \mathrm{diag}_{\widehat{A}}(n,i)=\sum_{k=0}^{i}\mathrm{col}(A)_{k} and \mathrm{diag}_{\widehat{A}}(i,n)=\sum_{k=0}^{i}\mathrm{row}(A)_{k} for i\in[n] ; (c) A^{t}\xmapsto{RSK}\widehat{A}^{t} . Our aim is to give an explicit construction of such a map where these essential properties are immediate from the construction. Remark 4 . These notes are not intended for publication. They record some ideas that were explained by Alex Postnikov during the MIT combinatorics preseminar. The ideas presented here are closely related to a certain birational lifting of RSK originally studied by Kirillov [ 11 ] which takes matrices with entries in \mathbb{R}_{>0} to other matrices of this form (or more generally, to certain three-dimensional arrays with entries in \mathbb{R}_{>0} ). Birational RSK has recently seen significant interest; see, e.g., [ 14 ] , [ 2 ] , [ 4 ] , [ 1 ] , [ 16 ] , [ 15 ] . The work of Danilov and Koshevoy [ 2 ] [ 3 ] in particular is closely related to the presentation of RSK given here because they explicitly observe the connection between RSK and the octahedron recurrence. Although everything written here naturally generalizes to the birational setting we choose to work in the combinatorial max-plus semiring setting because we are just trying to give an alternative description of classical RSK. In particular, our aim is to show how many classical combinatorial results (for instance, the “hook-length formula”) follow easily from this treatment of RSK, and at a greater level of generality as well. Thanks to Darij Grinberg for proofreading and helpful comments. Remark 5 . In May of 2017, Igor Pak pointed out his paper [ 17 ] to me, in which he develops essentially the same piecewise-linear “toggle” description of RSK that we will explain in the next section. The toggles can be seen specifically in §4 of [ 17 ] . That paper also cites an earlier paper of Berenstein and Kirillov [ 9 ] , who independently discovered a similar toggle map (and in fact, in [ 10 ] Berenstein–Kirillov studied the toggle description of RSK). 2. The RSK algorithm via toggles In fact, our map will work in a slightly more general setting than