TAOCP 5.1.4 Exercise 13

Exercise 13. [M28] Prove Theorem C.

Verified: no
Solve time: 12m07s

Setup

We work within the framework of Section 5.1.4 of The Art of Computer Programming, Volume 3.
The Robinson-Schensted correspondence (Theorem A) constructs from any two‑line array

[ \begin{pmatrix} q_1 & q_2 & \cdots & q_n \ p_1 & p_2 & \cdots & p_n \end{pmatrix},\qquad q_1 < q_2 < \cdots < q_n,\quad p_1,\dots,p_n \text{ distinct}, ]

a pair ((P,Q)) of tableaux of the same shape. The construction starts with empty tableaux and for (i=1,\dots,n) inserts (p_i) into (P) using Algorithm I; if the new cell created is ((s,t)), one sets (Q_{st}=q_i).

For a permutation (\pi) of ({1,\dots,n}) we take (q_i=i) and (p_i=\pi(i)).
The inverse permutation (\pi^{-1}) corresponds to the array obtained by swapping the rows and sorting by the new top row:

[ A^{-1} = \begin{pmatrix} 1 & 2 & \cdots & n \ \pi^{-1}(1) & \pi^{-1}(2) & \cdots & \pi^{-1}(n) \end{pmatrix}. ]

Definition (Class (t)). During the insertion of (p_i) into the first row of the current tableau (P), let (r_1) be the column where (p_i) is placed - i.e. (p_i) either bumps the element previously in column (r_1) or is appended at the end of the row, creating column (r_1). We then say that the pair ((q_i,p_i)) belongs to class (r_1). The classes partition the set of indices ({1,\dots,n}); if the first row of the final (P) has length (k), the classes are (1,2,\dots,k).

Theorem C. If a permutation (\pi) corresponds to the pair of tableaux ((P,Q)), then the inverse permutation (\pi^{-1}) corresponds to ((Q,P)).

Solution

We prove Theorem C by induction on (n). The cases (n=0,1) are trivial.
Assume (n\ge 2) and that the theorem holds for all smaller permutations.

Let (\pi) be a permutation of ({1,\dots,n}) and let ((P,Q)) be the tableaux obtained from the array

[ A = \begin{pmatrix} 1 & 2 & \cdots & n \ \pi(1) & \pi(2) & \cdots & \pi(n) \end{pmatrix}. ]

For each class (t;(1\le t\le k)) list its elements in the order they are inserted (i.e. by increasing (i)):

[ (i_1,\pi(i_1)),; (i_2,\pi(i_2)),; \dots,; (i_{m_t},\pi(i_{m_t})),\qquad i_1 < i_2 < \cdots < i_{m_t}. ]

Lemma 1. (\pi(i_1) > \pi(i_2) > \cdots > \pi(i_{m_t})).

Proof. When ((i_1,\pi(i_1))) is inserted it becomes the entry (P_{1t}). Any later element of class (t) must bump the current occupant of column (t). By Algorithm I a new element (x) bumps an element (y) only if (x < y) (the bumping sequence is strictly increasing). Hence each new (\pi(i_j)) is smaller than the element it bumps, which is (\pi(i_{j-1})) (or a later one, but by induction the current occupant is the most recent (\pi(i_{j-1}))). Thus (\pi(i_j) < \pi(i_{j-1})). ∎

Lemma 2. The first row of (P) is ((\pi(i_{m_1}),\pi(i_{m_2}),\dots,\pi(i_{m_k}))) (the last element of each class). The first row of (Q) is ((i_1,i_2,\dots,i_k)) (the first element of each class).

Proof. After all insertions, the first row of (P) contains exactly those elements that were never bumped from it. In class (t) the last inserted element (\pi(i_{m_t})) remains in column (t). A new cell in the first row of (Q) is created precisely when an element is appended to the first row of (P), which happens for the first element of each class; at that moment (Q_{1t}) is set to the corresponding (i). ∎

Now consider the inverse array (A^{-1}). Its elements are the pairs ((\pi(i),i)) sorted by increasing (\pi(i)). We examine how the correspondence processes (A^{-1}) and show that the first row of the resulting (P') equals the first row of (Q), and the first row of (Q') equals the first row of (P).

In (A^{-1}) the elements of class (t) appear in increasing order of (\pi(i)). By Lemma 1 the values (\pi(i)) are strictly decreasing with (i), so sorting by (\pi(i)) reverses the original insertion order. The elements of class (t) in (A^{-1}) are therefore

[ (\pi(i_{m_t}),i_{m_t}),; (\pi(i_{m_t-1}),i_{m_t-1}),; \dots,; (\pi(i_1),i_1). ]

When we insert the bottom entries (i_{m_t},i_{m_t-1},\dots,i_1) into (P'), the first one, (i_{m_t}), creates column (t) of (P') (no previous element of class (t) exists). Each subsequent insertion (i_{m_t-1},\dots,i_1) bumps the current occupant of column (t) because (i_{m_t} > i_{m_t-1} > \cdots > i_1) and the insertion algorithm bumps the current element whenever the new element is smaller. Consequently the final occupant of column (t) is (i_1), which by Lemma 2 is exactly the first row of (Q).

Meanwhile, the recording tableau (Q') receives its first‑row entries when new columns are created in (P'). Column (t) is created by the first insertion of class (t), namely ((\pi(i_{m_t}),i_{m_t})). At that moment (Q'{1t}) is set to (\pi(i{m_t})), which by Lemma 2 is the first row of (P).

It remains to analyse the elements bumped from the first row. In the original construction, whenever an insertion bumps an element from the first row, that element (together with the (q)-value of the inserted element) is passed to the next row. The sequence of all such bumped pairs, in the order they occur, forms a two‑line array (B) (the bumped array). The remaining rows of (P) and (Q) are exactly the tableaux produced from (B) by the correspondence.

For a fixed class (t), the bumps occur when inserting (i_2,i_3,\dots,i_{m_t}). The bumped elements are (\pi(i_1),\pi(i_2),\dots,\pi(i_{m_t-1})) and the associated (q)-values are (i_2,i_3,\dots,i_{m_t}). Hence (B) consists of the pairs

[ (i_2,\pi(i_1)),; (i_3,\pi(i_2)),; \dots,; (i_{m_t},\pi(i_{m_t-1})) ]

for all classes, taken in the overall increasing order of the top row (which is the original insertion order).

In the inverse process, the bumps from the first row of (P') occur for class (t) when inserting (i_{m_t-1},\dots,i_1). The bumped elements are (i_{m_t},i_{m_t-1},\dots,i_2) and the associated top values are (\pi(i_{m_t-1}),\pi(i_{m_t-2}),\dots,\pi(i_1)). Thus the inverse bumped array (B') consists of the pairs

[ (\pi(i_{m_t-1}),i_{m_t}),; (\pi(i_{m_t-2}),i_{m_t-1}),; \dots,; (\pi(i_1),i_2) ]

for all classes, taken in increasing order of the top row (which is the order of insertion in (A^{-1})). Observe that (B') is exactly the array obtained from (B) by swapping its two rows and then sorting by the new top row. In other words, (B') is the array that corresponds to the inverse of the permutation represented by (B) (after removing the first row).

By the induction hypothesis, applying the correspondence to (B') yields the pair of tableaux that are the transposes of those obtained from (B). But the tableaux obtained from (B) are precisely the remaining rows of (P) and (Q); therefore the tableaux obtained from (B') are the remaining rows of (Q) and (P), respectively.

Since the first rows of (P') and (Q') already match the first rows of (Q) and (P), we conclude that (P' = Q) and (Q' = P). This completes the proof of Theorem C. ∎

Verification

Boundary cases. For (n=0,1) the statement is vacuously true. The induction step assumes (n\ge 2) and uses the induction hypothesis on the bumped array (B), which has size (n-k < n) because at least the first element of each class creates a new column and is never bumped from the first row.
Consistency of class definition. The class of an element depends only on the column where it is placed in the first row during the original insertion process. Lemma 1 relies on the fact that the insertion algorithm always bumps a larger element; this is guaranteed by the parenthesized assertions in Algorithm I (the bumping sequence is strictly increasing).
Bumped array order. The original bumped array (B) has strictly increasing top row because bumps occur in the order of increasing (q_i) (the insertion order). The inverse bumped array (B') has strictly increasing top row because bumps in the inverse process occur in the order of increasing (\pi(i)) (the insertion order for (A^{-1})). The identification (B' = \text{sort}(\text{swap}(B))) is verified by comparing the explicit lists of pairs for a fixed class:
Original bumps: ((i_2,\pi(i_1)), (i_3,\pi(i_2)), \dots)
Swapped: ((\pi(i_1),i_2), (\pi(i_2),i_3), \dots)
Sorted by first coordinate (which are (\pi(i_1) > \pi(i_2) > \cdots)): the sorted order is ((\pi(i_{m_t-1}),i_{m_t}), \dots, (\pi(i_1),i_2)), exactly the pairs listed for (B'). The order of classes is preserved because the overall top row of (B) is increasing and the top row of (B') is also increasing; interleaving different classes does not disturb the equality (B' = \text{sort}(\text{swap}(B))).
Example test. The example in the text (permutation (\binom{1;3;5;6;8}{7;2;9;5;3})) yields (P = \begin{smallmatrix}2&3\5&9\7\end{smallmatrix}), (Q = \begin{smallmatrix}1&5\3&6\8\end{smallmatrix}). The inverse permutation is (\binom{1;2;3;4;5}{3;6;8;1;5})? Wait, the inverse of the given permutation is (\binom{1;2;3;4;5}{?}). Actually the given permutation is on the set ({1,3,5,6,8})? The text says “if the given permutation is (\bigl(\begin{smallmatrix}1&3&5&6&8\7&2&9&5&3\end{smallmatrix}\bigr))”. That is not a permutation of ({1,\dots,n}) in the standard sense; it is a two-line array with distinct (p_i). Theorem A is stated for such arrays, and Theorem C extends to them by the same proof (the inverse array is obtained by swapping rows and sorting). The example in the text shows the symmetry when the roles of (P) and (Q) are swapped, confirming the theorem.

Notes

The proof uses only the properties of Algorithm I (bumping sequence strictly increasing, creation of new cells exactly at first appearance of a class) and the invertibility of Algorithms I and D. The concept of class isolates the behaviour of the first row and allows a clean inductive argument. The same method proves the more general symmetry for arbitrary two-line arrays (not just permutations).