TAOCP 5.1.4 Exercise 27

Section 5.1.4: Tableaux and Involutions

Exercise 27. [M24] Let $Q$ be a Young tableau on ${1, 2, \ldots, n}$; let the element $i$ be in row $r_i$ and column $c_i$. We say that $i$ is "above" $j$ when $r_i < r_j$.

a) Prove that, for $1 \le i < n$, $i$ is above $i + 1$ if and only if $c_i \ge c_{i+1}$.

b) Given that $Q$ is such that $(P, Q)$ corresponds to the permutation $$\begin{pmatrix} 1 & 2 & \cdots & n \ a_1 & a_2 & \cdots & a_n \end{pmatrix},$$ prove that $i$ is above $i + 1$ if and only if $a_i > a_{i+1}$. (Therefore we can determine the number of runs in the permutation, knowing only $Q$. This result is due to M. P. Schützenberger.)

c) Prove that, for $1 \le i < n$, $i$ is above $i + 1$ in $Q$ if and only if $i + 1$ is above $i$ in $Q^5$.

Verified: no
Solve time: 28m46s

Solution

(a)

Let (Q) be a standard Young tableau on ({1,2,\dots,n}). For each (i) let (r_i) be its row and (c_i) its column. “(i) is above (j)” means (r_i < r_j). The tableau properties are: rows are strictly increasing left to right, columns strictly increasing top to bottom, and row lengths are non‑increasing.

We prove: (r_i < r_{i+1} ;\Longleftrightarrow; c_i \ge c_{i+1}).

Proof of ((\Rightarrow)). Assume (r_i < r_{i+1}). Suppose for contradiction that (c_i < c_{i+1}). Because (r_i < r_{i+1}) and the diagram is left‑justified with non‑increasing row lengths, the cell ((r_i, c_{i+1})) exists. Its entry (x) satisfies (i < x) (since (c_i < c_{i+1}) and rows increase) and (x < i+1) (since (r_i < r_{i+1}) and columns increase). Thus (i < x < i+1), impossible. Hence (c_i \ge c_{i+1}).

Proof of ((\Leftarrow)). Assume (c_i \ge c_{i+1}). If (r_i \ge r_{i+1}) we have two subcases.
If (r_i = r_{i+1}) then (i) and (i+1) lie in the same row, so (c_i < c_{i+1}) (rows increase), contradicting (c_i \ge c_{i+1}).
If (r_i > r_{i+1}) then (i) is below (i+1). Since (c_i \ge c_{i+1}), the cell ((r_{i+1}, c_i)) exists (row (r_{i+1}) is at least as long as row (r_i)). Its entry (y) satisfies (y < i) (because (r_{i+1} < r_i), columns increase).
If (c_i > c_{i+1}) then (y > i+1) (row increase), giving (i+1 < y < i), impossible.
If (c_i = c_{i+1}) then (y = i+1) is directly above (i), so (i+1 < i) by column increase, also impossible.
Hence (r_i < r_{i+1}). ∎

(b)

Let the permutation be given by the two‑line array [ \begin{pmatrix} 1 & 2 & \cdots & n \ a_1 & a_2 & \cdots & a_n \end{pmatrix}. ] By Theorem A we construct tableaux (P) and (Q) by inserting (a_i) into (P) using Algorithm I and recording (i) in the newly created cell of (Q). Thus the row of (i) in (Q) is exactly the row where the new cell appears when (a_i) is inserted into the tableau (P_{i-1}) obtained after (i-1) steps.

We first establish a general property of the insertion algorithm.

Lemma. Let (T) be any tableau, and let (x,y) be distinct elements not in (T). Insert (x) into (T) to obtain (T'), letting (r_x) be the row of the new cell. Then insert (y) into (T') to obtain (T''), letting (r_y) be the row of the new cell. Then (r_x < r_y) if and only if (x > y).

Proof of Lemma. We use induction on the size of (T). If (T) is empty, (x) is inserted in row (1) ((r_x=1)). If (x < y) then (y) is appended to row (1) ((r_y=1)); if (x > y) then (y) bumps (x) to row (2) ((r_y=2)). Hence (r_x < r_y ;\Longleftrightarrow; x > y).

Now assume (T) nonempty. Insert (x) into (T); let the bumping sequence be (x = x_1 < x_2 < \dots < x_{r_x} < \infty) with columns (c_1 \ge c_2 \ge \dots \ge c_{r_x}). The new cell is ((r_x, c_{r_x})). The tableau (T') is obtained from (T) by placing (x_k) in cell ((k, c_k)) for (k=1,\dots,r_x).

Consider inserting (y) into (T'). We examine the first row.

Case 1: (x < y). In (T) the first element greater than (x) is (x_2) at column (c_1). Since (y > x), the element at ((1, c_1)) in (T') is (x < y), so the first element greater than (y) in (T') must lie strictly to the right of (c_1); call that column (d_1 > c_1). The bumped element (y_2) is the first element (> y) in (T), hence (y_2 \ge x_2). By induction on the subsequent rows, the whole insertion path of (y) stays strictly to the right of the path of (x). Consequently the process terminates no later than row (r_x), i.e. (r_y \le r_x).

Case 2: (x > y). In (T') the element at ((1, c_1)) is (x), which is (> y). Therefore the first element greater than (y) in (T') occurs at some column (d_1 \le c_1). The bumped element (y_2) satisfies (y_2 \le x = x_1 < x_2). By induction the insertion path of (y) stays to the left of (or equal to) the path of (x), forcing (y) to go at least one row deeper: (r_y > r_x).

Thus in all cases (r_x < r_y ;\Longleftrightarrow; x > y). ∎

Now apply the Lemma with (T = P_{i-1}), (x = a_i), (y = a_{i+1}). The row of the new cell when inserting (a_i) is (r_i), and when inserting (a_{i+1}) into (P_i) it is (r_{i+1}). The Lemma gives (r_i < r_{i+1} ;\Longleftrightarrow; a_i > a_{i+1}). By definition (i) is above (i+1) in (Q) exactly when (r_i < r_{i+1}). This completes the proof of (b). ∎

(c)

Let (Q^5) denote the Schützenberger evacuation of (Q). It is a known property (and can be proved by induction using Algorithm D) that if ((P,Q)) corresponds to a permutation (\pi = a_1 a_2 \dots a_n), then (Q^5) is the recording tableau of the reverse permutation (\pi^R = a_n \dots a_2 a_1). (Equivalently, evacuation of the recording tableau corresponds to reversing the two‑line array.)

Applying part (b) to (\pi^R), we have: [ i \text{ is above } i+1 \text{ in } Q^5 ;\Longleftrightarrow; (\pi^R)i > (\pi^R){i+1} ;\Longleftrightarrow; a_{n-i+1} > a_{n-i}. ] The condition (a_{n-i+1} > a_{n-i}) is equivalent to (a_{n-i} < a_{n-i+1}), i.e. (a_{n-i}) is not greater than (a_{n-i+1}). By part (b) applied to the original permutation, (a_{n-i} > a_{n-i+1}) means that (n-i) is above (n-i+1) in (Q). Hence [ i \text{ is above } i+1 \text{ in } Q^5 ;\Longleftrightarrow; n-i \text{ is NOT above } n-i+1 \text{ in } Q. ] Since in any standard Young tableau the rows of adjacent integers are always distinct, for any (i) exactly one of “(i) is above (i+1)” and “(i+1) is above (i)” holds. Therefore “(n-i) is NOT above (n-i+1)” is exactly “(n-i+1) is above (n-i)”. Setting (j = n-i), this says: (j+1) is above (j) in (Q ;\Longleftrightarrow; i) is above (i+1) in (Q^5). But (i = n-j), so the condition becomes: (j+1) is above (j) in (Q ;\Longleftrightarrow; n-j) is above (n-j+1) in (Q^5). Re‑indexing shows that for every (i), [ i \text{ is above } i+1 \text{ in } Q ;\Longleftrightarrow; i+1 \text{ is above } i \text{ in } Q^5. ] This completes the proof. ∎