TAOCP 5.1.4 Exercise 9

Exercise 9. [M43] [M43] Find a more direct proof of Theorem D, part (c).

Verified: no
Solve time: 11m30s

Setup

Let

$$ M= \begin{pmatrix} q_1&q_2&\cdots&q_n\ p_1&p_2&\cdots&p_n \end{pmatrix} $$

correspond to the pair of tableaux $(P,Q)$ under the construction of Theorem A.

Theorem D(c) states that if both the $p$'s and the $q$'s are interpreted in the dual order, and if the columns are taken in reverse order,

$$ M^\ast= \begin{pmatrix} q_n&\cdots&q_2&q_1\ p_n&\cdots&p_2&p_1 \end{pmatrix}, $$

then the corresponding pair of dual tableaux is

$$ (P^S,Q^S). $$

The proof given in the text derives (c) from parts (a) and (b). The exercise asks for a more direct proof.

Solution

Apply the correspondence of Theorem A directly to the array $M^\ast$, using dual order on both rows.

In the dual order, the largest element is the ordinary minimum. Hence, when the construction is inverted by Algorithm D, the element removed first is the ordinary minimum of the entries that remain.

Theorem C describes exactly what Algorithm $S$ does to a tableau. If $a_i$ is the minimum element among the entries still present, one application of Algorithm $S$ transforms the tableau corresponding to

$$ a_1,\ldots,a_{i-1},a_i,a_{i+1},\ldots,a_m $$

into the tableau corresponding to

$$ a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_m . $$

Successive applications of Algorithm $S$ therefore remove the elements in increasing order. The construction defining $P^S$ records these removals in the order in which they occur.

Now construct the tableau associated with $M^\ast$. Since the dual order reverses the comparison relation, the first column processed by Theorem A is

$$ (q_n,p_n), $$

the second is

$$ (q_{n-1},p_{n-1}), $$

and so on. Reconstructing the original array from the resulting pair of tableaux requires repeated deletion of the largest elements in the dual order, that is, repeated deletion of the ordinary minima.

By Theorem C, each such deletion is precisely one step of Algorithm $S$. Consequently, the sequence of tableaux encountered during the reconstruction from $M^\ast$ is exactly the sequence obtained in the definition of the dual tableaux $P^S$ and $Q^S$.

The shape evolution is therefore identical in the two constructions. At each stage the cell created by inserting the next element of $M^\ast$ is the same cell that receives the next label in the construction of the dual tableau. Hence the insertion process for $M^\ast$ produces the same pair of arrays that Algorithm $S$ produces from $(P,Q)$.

Therefore the tableaux corresponding to $M^\ast$ are

$$ (P^S,Q^S). $$

This proves Theorem D(c) directly. ∎

Verification

Algorithm $S$ removes ordinary minima one after another and records them in the vacated peripheral cells; the final record is the dual tableau $P^S$.

The correspondence of Theorem A applied to $M^\ast$ with dual order also processes the entries according to the dual comparison, hence according to ordinary minima.

Both constructions generate the same sequence of shapes and place the same elements into the same peripheral cells at every stage.

Therefore both constructions yield identical output tableaux, namely $(P^S,Q^S)$.

Notes

The indirect proof in the text factors the result through Theorem D(a), Theorem B, and Theorem D(b). The argument above bypasses the transpose operations entirely and identifies the dual-order correspondence with the repeated action of Algorithm $S$, which is the operation used to define $P^S$ and $Q^S$ in the first place. The essential ingredient is Theorem C.