[proofplan] We use the insertion characterization of Knuth equivalence: two words are Knuth equivalent exactly when they have the same Schensted insertion tableau. Thus it is enough to prove that both the row reading word and the column reading word insert back to the original tableau $T$. We prove these two reconstruction facts directly from the row-insertion rule, using induction over rows for $\operatorname{row}(T)$ and induction over columns for $\operatorname{col}(T)$. [/proofplan]

[step:Fix the insertion and reading conventions] Let $A$ be the totally ordered alphabet of entries of $T$. For a word $w=w_1\cdots w_m$ in $A$, let $P(w)$ denote the tableau obtained by starting with the empty tableau and successively applying Schensted row insertion to $w_1,w_2,\dots,w_m$, using the convention that an inserted letter bumps the leftmost entry in the current row that is strictly larger than it. Index the rows of $T$ from top to bottom by $1,\dots,r$. For each $1\le i\le r$, let \begin{align*} R_i=(t_{i,1},t_{i,2},\dots,t_{i,\lambda_i}) \end{align*} denote the $i$-th row, where $\lambda_i$ is the number of boxes in row $i$ and $t_{i,j}\in A$ is the entry in column $j$. Thus $t_{i,j}\le t_{i,j+1}$ whenever both entries are defined, and $t_{i,j}<t_{i+1,j}$ whenever both entries are defined. With this notation, \begin{align*} \operatorname{row}(T)=R_rR_{r-1}\cdots R_1. \end{align*} For each column index $j\ge 1$, let $C_j$ denote the word formed by reading the entries in column $j$ from bottom to top. If the height of column $j$ is $h_j$, then \begin{align*} C_j=t_{h_j,j}t_{h_j-1,j}\cdots t_{1,j}. \end{align*} The column reading word is \begin{align*} \operatorname{col}(T)=C_1C_2\cdots C_{\lambda_1}. \end{align*} [/step]

[step:Insert the row reading word back to $T$]For $0\le k\le r$, let $T_k$ be the subtableau of $T$ consisting of the bottom $k$ rows. Thus $T_0$ is empty and $T_r=T$. We prove by induction on $k$ that \begin{align*} P(R_rR_{r-1}\cdots R_{r-k+1})=T_k. \end{align*} The case $k=0$ is the definition of insertion into the empty word. Assume the assertion holds for some $0\le k<r$, and set $i=r-k$. By the induction hypothesis, before inserting the row word $R_i$ the current tableau is the subtableau $T_k$, consisting of rows $i+1,\dots,r$ of $T$. Write \begin{align*} R_i=(a_1,a_2,\dots,a_{\lambda_i}), \end{align*} where $a_j=t_{i,j}$. We insert $a_1,a_2,\dots,a_{\lambda_i}$ in this order. Since row $i$ of $T$ is weakly increasing, we have $a_1\le a_2\le\cdots\le a_{\lambda_i}$. Since columns of $T$ are strictly increasing, whenever the entry $t_{i+1,j}$ exists we have \begin{align*} a_j=t_{i,j}<t_{i+1,j}. \end{align*} We record the precise bumping invariant. After the letters $a_1,\dots,a_{j-1}$ have been inserted, for each lower row index $\ell\ge 1$ for which the relevant entries exist, row $\ell$ of the current tableau has entries $t_{i+\ell-1,1},\dots,t_{i+\ell-1,j-1}$ in columns $1,\dots,j-1$ and has $t_{i+\ell,j}$ in column $j$. Thus, when the letter $t_{i+\ell-1,j}$ reaches this row, every entry to the left of column $j$ is at most $t_{i+\ell-1,j}$ by weak increase along row $i+\ell-1$, while the entry in column $j$ is $t_{i+\ell,j}$ and satisfies $t_{i+\ell-1,j}<t_{i+\ell,j}$ by strict increase down columns. Therefore the row-insertion rule bumps exactly the entry in column $j$. If there is no entry $t_{i+\ell,j}$, then every existing entry in that row is at most $t_{i+\ell-1,j}$, and the incoming letter is appended at the end of the row. It follows by induction on $j$ that inserting $a_j=t_{i,j}$ bumps entries down column $j$ and creates exactly the boxes of column $j$ belonging to row $i$. After inserting all letters of $R_i$, the new top row is exactly $R_i$, and the rows below it are exactly rows $i+1,\dots,r$ of $T$. Hence \begin{align*} P(R_rR_{r-1}\cdots R_i)=T_{k+1}. \end{align*} This completes the induction, and taking $k=r$ gives \begin{align*} P(\operatorname{row}(T))=T. \end{align*}[/step]

[guided]The point of the row reading convention is that row insertion builds the tableau from bottom to top. For $0\le k\le r$, define $T_k$ to be the subtableau consisting of the bottom $k$ rows of $T$. We prove the precise invariant \begin{align*} P(R_rR_{r-1}\cdots R_{r-k+1})=T_k. \end{align*} For $k=0$, no letters have been inserted, so the insertion tableau is empty, which is $T_0$. Now assume the invariant holds for some $0\le k<r$. Let $i=r-k$, so the next row to insert is row $i$ of $T$. Write this row as \begin{align*} R_i=(a_1,a_2,\dots,a_{\lambda_i}), \end{align*} where $a_j=t_{i,j}$. By the induction hypothesis, the current tableau is exactly the part of $T$ consisting of rows $i+1,\dots,r$. We must check what happens when the entries $a_1,\dots,a_{\lambda_i}$ are inserted from left to right. The weak row condition gives \begin{align*} a_1\le a_2\le\cdots\le a_{\lambda_i}. \end{align*} The strict column condition gives, whenever the box below $(i,j)$ exists, \begin{align*} a_j=t_{i,j}<t_{i+1,j}. \end{align*} These two inequalities determine the insertion path, but we must track the changing rows carefully. Suppose that $a_1,\dots,a_{j-1}$ have already been inserted. At this stage, the first $j-1$ columns have been restored with row $i$ placed on top, while column $j$ of the current first row is still the old entry $t_{i+1,j}$ when that entry exists. More generally, if the letter $t_{i+\ell-1,j}$ has reached the $\ell$-th row of the current tableau, then the entries to the left of column $j$ in that row are \begin{align*} t_{i+\ell-1,1},\dots,t_{i+\ell-1,j-1}. \end{align*} Each of these entries is at most $t_{i+\ell-1,j}$ because row $i+\ell-1$ of $T$ is weakly increasing. The entry in column $j$ of the current row is $t_{i+\ell,j}$, provided this box exists, and strict increase down columns gives \begin{align*} t_{i+\ell-1,j}<t_{i+\ell,j}. \end{align*} Therefore the first entry in that row which is strictly larger than the incoming letter is exactly the entry in column $j$, so row insertion bumps the entry in column $j$. If the box $(i+\ell,j)$ does not exist, then there is no entry in column $j$ to bump and all existing entries in the row are at most the incoming letter, so the incoming letter is appended. Thus, for each fixed $j$, the bumping path follows column $j$ until it terminates, and it restores the lower rows exactly as they appear in $T$. After the letters $a_1,\dots,a_{\lambda_i}$ have been inserted, the inserted row $R_i$ has become the new top row of the current subtableau, and the rows underneath remain rows $i+1,\dots,r$ of $T$. Therefore \begin{align*} P(R_rR_{r-1}\cdots R_i)=T_{k+1}. \end{align*} The induction is complete. Setting $k=r$ yields \begin{align*} P(\operatorname{row}(T))=T. \end{align*}[/guided]

[step:Insert the column reading word back to $T$]For $0\le q\le \lambda_1$, let $T_{\le q}$ be the subtableau of $T$ consisting of the first $q$ columns. Thus $T_{\le 0}$ is empty and $T_{\le \lambda_1}=T$. We prove by induction on $q$ that \begin{align*} P(C_1C_2\cdots C_q)=T_{\le q}. \end{align*} The case $q=0$ is immediate. Assume the assertion holds for some $0\le q<\lambda_1$. Let $h=h_{q+1}$ be the height of column $q+1$, and define letters $b_s\in A$ for $1\le s\le h$ by $b_s=t_{s,q+1}$. Then \begin{align*} C_{q+1}=b_hb_{h-1}\cdots b_1. \end{align*} By the induction hypothesis, the current tableau before this column is inserted is $T_{\le q}$. We use a second induction while inserting the letters $b_h,b_{h-1},\dots,b_1$. After the letters $b_h,b_{h-1},\dots,b_{s+1}$ have been inserted, the current tableau is obtained from $T_{\le q}$ by adjoining one extra box in column $q+1$ to rows $1,\dots,h-s$, with entries \begin{align*} b_{s+1},b_{s+2},\dots,b_h \end{align*} in those rows from top to bottom. This assertion is empty when $s=h$. Now insert $b_s$. In row $\ell$ with $1\le \ell\le h-s$, the incoming letter is $b_{s+\ell-1}=t_{s+\ell-1,q+1}$. Every entry in the first $q$ columns of row $\ell$ is at most $t_{s+\ell-1,q+1}$: indeed, for $1\le c\le q$, weak increase along rows and strict increase down columns give \begin{align*} t_{\ell,c}\le t_{s+\ell-1,c}\le t_{s+\ell-1,q+1}. \end{align*} The extra entry in column $q+1$ of that row is $b_{s+\ell}=t_{s+\ell,q+1}$, and strict increase down column $q+1$ gives \begin{align*} t_{s+\ell-1,q+1}<t_{s+\ell,q+1}. \end{align*} Therefore the row-insertion rule bumps exactly the entry in column $q+1$ of row $\ell$. After this has happened for $\ell=1,\dots,h-s$, the letter $b_h=t_{h,q+1}$ reaches row $h-s+1$, which has only the first $q$ columns. Every entry in that row is at most $b_h$ by the same row and column monotonicity argument, so $b_h$ is appended in column $q+1$. Thus inserting $b_s$ changes the extra entries in rows $1,\dots,h-s+1$ to \begin{align*} b_s,b_{s+1},\dots,b_h \end{align*} from top to bottom, while the first $q$ columns remain those of $T_{\le q}$. This proves the inner induction. Taking $s=1$ shows that after inserting all of $C_{q+1}$, the current tableau is exactly $T_{\le q+1}$. Hence, by induction on $q$, \begin{align*} P(C_1C_2\cdots C_{\lambda_1})=T. \end{align*} Since the left-hand word is $\operatorname{col}(T)$, this says \begin{align*} P(\operatorname{col}(T))=T. \end{align*}[/step]

[guided]The delicate point is that row insertion always starts in the first row. Therefore the letter meant to become the entry of row $s$ in the new column does not immediately jump to row $s$; instead, it starts at the top and pushes a chain of already inserted lower-column entries downward. Fix $q$ and assume, by the outer induction, that the columns $1,\dots,q$ have already been built, so the current tableau is $T_{\le q}$. Let $h=h_{q+1}$ be the height of the next column and define $b_s=t_{s,q+1}$ for $1\le s\le h$. The word for this column is \begin{align*} C_{q+1}=b_hb_{h-1}\cdots b_1, \end{align*} so the entries are inserted from bottom to top. We prove the exact intermediate shape. After inserting $b_h,b_{h-1},\dots,b_{s+1}$, the tableau is $T_{\le q}$ together with an added box in column $q+1$ in the first $h-s$ rows. The entries in these added boxes are \begin{align*} b_{s+1},b_{s+2},\dots,b_h \end{align*} from top to bottom. For $s=h$, no letters have yet been inserted from this column, so this assertion is just the statement that the current tableau is $T_{\le q}$. Now insert $b_s$. The first row contains the old first $q$ entries of $T$, followed by the temporary added entry $b_{s+1}$. The entries in the first $q$ columns are at most $b_s$: for every $1\le c\le q$, \begin{align*} t_{1,c}\le t_{s,c}\le t_{s,q+1}=b_s, \end{align*} where the [first inequality](/theorems/2897) uses increase down columns and the second uses weak increase along row $s$. On the other hand, \begin{align*} b_s=t_{s,q+1}<t_{s+1,q+1}=b_{s+1} \end{align*} by strict increase down column $q+1$. Hence row insertion bumps the temporary entry $b_{s+1}$ from column $q+1$ of the first row. The same computation now repeats with indices shifted. Suppose the bump has reached row $\ell$, where $1\le \ell\le h-s$, and the incoming letter is $b_{s+\ell-1}=t_{s+\ell-1,q+1}$. For every $1\le c\le q$, the entry $t_{\ell,c}$ in the old part of row $\ell$ satisfies \begin{align*} t_{\ell,c}\le t_{s+\ell-1,c}\le t_{s+\ell-1,q+1}=b_{s+\ell-1}. \end{align*} The first inequality is column monotonicity, and the second is row monotonicity. The temporary entry in column $q+1$ of row $\ell$ is $b_{s+\ell}=t_{s+\ell,q+1}$, and strict column increase gives \begin{align*} b_{s+\ell-1}<b_{s+\ell}. \end{align*} Therefore the first entry strictly larger than the incoming letter is exactly the temporary entry in column $q+1$, so it is bumped to the next row. After the bumping chain has passed through rows $1,\dots,h-s$, the incoming letter is $b_h=t_{h,q+1}$ and it reaches row $h-s+1$, which has no temporary entry in column $q+1$ yet. Every entry in the first $q$ columns of that row is at most $b_h$ by the same inequality \begin{align*} t_{h-s+1,c}\le t_{h,c}\le t_{h,q+1}=b_h. \end{align*} Thus row insertion appends $b_h$ at the end of row $h-s+1$. So inserting $b_s$ replaces the temporary column entries by \begin{align*} b_s,b_{s+1},\dots,b_h \end{align*} from top to bottom in rows $1,\dots,h-s+1$, and it does not change the first $q$ columns. This proves the inner induction. At $s=1$, the added column has entries $b_1,b_2,\dots,b_h$, which are exactly \begin{align*} t_{1,q+1},t_{2,q+1},\dots,t_{h,q+1}. \end{align*} Therefore the tableau after inserting all of $C_{q+1}$ is $T_{\le q+1}$. The outer induction over $q$ gives \begin{align*} P(C_1C_2\cdots C_{\lambda_1})=T. \end{align*} Since $C_1C_2\cdots C_{\lambda_1}=\operatorname{col}(T)$, we conclude \begin{align*} P(\operatorname{col}(T))=T. \end{align*}[/guided]

[step:Apply the Knuth equivalence characterization] We have proved \begin{align*} P(\operatorname{row}(T))=T \end{align*} and \begin{align*} P(\operatorname{col}(T))=T. \end{align*} Therefore \begin{align*} P(\operatorname{row}(T))=P(\operatorname{col}(T)). \end{align*} Both $\operatorname{row}(T)$ and $\operatorname{col}(T)$ are finite words over the same totally ordered alphabet $A$, and $P$ is the Schensted row-insertion tableau map for words over $A$. By the [Knuth equivalence theorem](/theorems/8432), two words over a totally ordered alphabet have the same insertion tableau if and only if they are Knuth equivalent. Applying this theorem to the two words $\operatorname{row}(T)$ and $\operatorname{col}(T)$ gives \begin{align*} \operatorname{row}(T)\equiv_K \operatorname{col}(T). \end{align*} This is the desired conclusion. [/step]