Utilisateur:ManiacParisien/Brouillons/Bio-3

En mathématiques, et notamment en combinatoire algébrique, la correspondance de Robinson–Schensted–Knuth, aussi appelée la correspondance RSK ou l'algorithme RSK, est une bijection entre matrices $A$ à coefficients entiers naturels et paires de tableaux de Young semi-standard de même forme, dont la taille est égale à la somme des entrées de la matrice $A$. Cette correspondance généralise la correspondance de Robinson-Schensted, en ce sens que si $A$ est une matrice de permutation, alors la paire $(P,Q)$ est la paire de tableaux standard associés à la permutation par la correspondance de Robinson–Schensted.

La correspondance de Robinson–Schensted–Knuth étend bon nombre des propriétés remarquables de la correspondance de Robinson–Schensted, et notamment la propriété de symétrie : la transposition de la matrice $A$ revient à l'échange des tableaux $P$ et $Q$.

La correspondance de Robinson–Schensted–Knuth

Introduction

La correspondance de Robinson-Schensted est une bijection entre permutations et paires de tableaux de Young standard de même forme. Cette bijection peut être construite au moyen d'un algorithme appelé l'insertion de Schensted. Cet algorithme commence avec un tableau $P$ vide et insère successivement les valeurs $\sigma _{1},\ldots ,\sigma _{n}$ de la permutation $\sigma$, avec $\sigma$ donnée sous forme fonctionnelle :

$\sigma ={\begin{pmatrix}1&2&\ldots &n\\\sigma _{1}&\sigma _{2}&\ldots &\sigma _{n}\end{pmatrix}}$.

Le tableau $P$ obtenu est le premier de la paire correspondant à $\sigma$; le deuxième tableau standard, noté $Q$, enregistre les formes successives parcourues durant la construction de $P$.

La construction de Schensted peut en fait prendre en compte des suites de nombres plus générales que celles obtenues par des permutations (notamment on peut autoriser des répétitions); dans ce cas, la construction produit un tableau $P$ semi-standard plutôt qu'un tableau standard, mais $Q$ reste un tableau standard. La correspondance RSK rétablit la symétrie entre tableaux en produisant un tableaux semi-standard pour $Q$ aussi.

Tables à deux lignes

Un table à deux lignes (« two-line array » en anglais) ou permutation généralisée $w_{A}$ correspondant à une matrice $A$ est définie comme suit est une matrice

$w_{A}={\begin{pmatrix}i_{1}&i_{2}&\cdots &i_{m}\\j_{1}&j_{2}&\cdots &j_{m}\end{pmatrix}}$

qui vérifie les propriétés suivantes:

• Les colonnes sont ordonnées en ordre lexicographique, ce qui signifie que
  1. $i_{1}\leq i_{2}\leq i_{3}\leq \cdots \leq i_{m}$, et
  2. si $i_{r}=i_{s}$ et $r\leq s$, alors $j_{r}\leq j_{s}$.
• pour chaque paires d'indices $(i,j)$ de la matrice $A$, il y a $A_{i,j}$ colonnes égales à ${\tbinom {i}{j}}$.

En particulier, l'entier $m$ est égal à la somme des coefficients de la matrice $A$.

Exemple

La table à deux lignes correspondant à la matrice :

$A={\begin{pmatrix}1&0&2\\0&2&0\\1&1&0\end{pmatrix}}$

est :

$w_{A}={\begin{pmatrix}1&1&1&2&2&3&3\\1&3&3&2&2&1&2\end{pmatrix}}$

Définition de la correspondance

En appliquant l'algorithme d'insertion de Schensted à la deuxième ligne d'une table à deux lignes, on obtient une paire consistant en un tableau semi-standard $P$ et un tableau standard noté $Q_{0}$. Ce deuxième tableau peut lui aussi être transformé en un tableau semi-standard noté $Q$ en remplaçant chaque entrée $h$ de $Q_{0}$ par la $h$-ième entrée de la première ligne de $w_{A}$.

On obtient ainsi une bijection des matrices A sur des paires (P,Q) de tableaux de Young semi-standard de même forme; les coefficients de P sont les coefficients de la deuxième ligne de w_A, et les coefficients de Q sont les coefficients de la première ligne de w_A. De plus, le nombre de coefficients de P égaux à j est égal à la somme des coefficients de la colonne d'indice j de A, et le nombre de coefficients égaux à i dans Q est égal à la somme des coefficients de la ligne d'indice i de A.

One thus obtains a bijection from matrices A to ordered pairs, (P,Q) of semistandard Young tableaux of the same shape, in which the set of entries of P is that of the second line of w_A, and the set of entries of Q is that of the first line of w_A. The number of entries j in P is therefore equal to the sum of the entries in column j of A, and the number of entries i in Q is equal to the sum of the entries in row i of A.

Example

In the above example, the result of applying the Schensted insertion to successively insert 1,3,3,2,2,1,2 into an initially empty tableau results in a tableau P, and an additional standard tableau Q₀ recoding the successive shapes, given by

$P\quad =\quad {\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}},\qquad Q_{0}\quad =\quad {\begin{matrix}1&2&3&7\\4&5\\6\end{matrix}},$

and after replacing the entries 1,2,3,4,5,6,7 in Q₀ successively by 1,1,1,2,2,3,3 on obtains the pair of semistandard tableaux

$P\quad =\quad {\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}},\qquad Q\quad =\quad {\begin{matrix}1&1&1&3\\2&2\\3\end{matrix}}.$

Direct definition of the RSK correspondence

The above definition uses the Schensted algorithm, which produces a standard recording tableau Q₀, and modifies it to take into account the first line of the two-line array and produce a semistandard recording tableau; this makes the relation to the Robinson–Schensted correspondence evident. It is natural however to simplify the construction by modifying the shape recording part of the algorithm to directly take into account the first line of the two-line array; it is in this form that the algorithm for the RSK correspondence is usually described. This simply means that after every Schensted insertion step, the tableau Q is extended by adding, as entry of the new square, the b-th entry i_b of the first line of w_A, where b is the current size of the tableaux. That this always produces a semistandard tableau follows from the property (first observed by Knuth) that for successive insertions with an identical value in the first line of w_A, each successive square added to the shape is in a column strictly to the right of the previous one.

Here is a detailed example of this construction of both semistandard tableaux. Corresponding to a matrix

$A={\begin{pmatrix}0&0&0&0&0&0&0\\0&0&0&1&0&1&0\\0&0&0&1&0&0&0\\0&0&0&0&0&0&1\\0&0&0&0&1&0&0\\0&0&1&1&0&0&0\\0&0&0&0&0&0&0\\1&0&0&0&0&0&0\\\end{pmatrix}}$

one has the two-line array

$w_{A}={\begin{pmatrix}2&2&3&4&5&6&6&8\\4&6&4&7&5&3&4&1\end{pmatrix}}.$

The following table shows the construction of both tableaux for this example

Inserted pair	${\tbinom {2}{4}}$	${\tbinom {2}{6}}$	${\tbinom {3}{4}}$	${\tbinom {4}{7}}$	${\tbinom {5}{5}}$	${\tbinom {6}{3}}$	${\tbinom {6}{4}}$	${\tbinom {8}{1}}$
P	${\begin{matrix}4\end{matrix}}$	${\begin{matrix}4&6\end{matrix}}$	${\begin{matrix}4&4\\6\end{matrix}}$	${\begin{matrix}4&4&7\\6\end{matrix}}$	${\begin{matrix}4&4&5\\6&7\end{matrix}}$	${\begin{matrix}3&4&5\\4&7\\6\end{matrix}}$	${\begin{matrix}3&4&4\\4&5\\6&7\end{matrix}}$	${\begin{matrix}1&4&4\\3&5\\4&7\\6\end{matrix}}$
Q	${\begin{matrix}2\end{matrix}}$	${\begin{matrix}2&2\end{matrix}}$	${\begin{matrix}2&2\\3\end{matrix}}$	${\begin{matrix}2&2&4\\3\end{matrix}}$	${\begin{matrix}2&2&4\\3&5\end{matrix}}$	${\begin{matrix}2&2&4\\3&5\\6\end{matrix}}$	${\begin{matrix}2&2&4\\3&5\\6&6\end{matrix}}$	${\begin{matrix}2&2&4\\3&5\\6&6\\8\end{matrix}}$

Combinatorial properties of the RSK correspondence

The case of permutation matrices

If $A$ is a permutation matrix then RSK outputs standard Young Tableaux (SYT), $P,Q$ of the same shape $\lambda$. Conversely, if $P,Q$ are SYT having the same shape $\lambda$, then the corresponding matrix $A$ is a permutation matrix. As a result of this property by simply comparing the cardinalities of the two sets on the two sides of the bijective mapping we get the following corollary:

Corollary 1: For each $n\geq 1$ we have $\sum _{\lambda \vdash n}(f^{\lambda })^{2}=n!$ where $\lambda \vdash n$ means $\lambda$ varies over all partitions of $n$ and $f^{\lambda }$ is the number of standard Young tableaux of shape $\lambda$.

Symmetry

Let $A$ be a matrix with non-negative entries. Suppose the RSK algorithm maps $A$ to $(P,Q)$ then the RSK algorithm maps $A^{T}$ to $(Q,P)$, where $A^{T}$ is the transpose of $A$.

In particular for the case of permutation matrices, one recovers the symmetry of the Robinson–Schensted correspondence:

Theorem 2: If the permutation $\sigma$ corresponds to a triple $(\lambda ,P,Q)$, then the inverse permutation, $\sigma ^{-1}$, corresponds to $(\lambda ,Q,P)$.

This leads to the following relation between the number of involutions on $S_{n}$ with the number of tableaux that can be formed from $S_{n}$ (An involution is a permutation that is its own inverse):

Corollary 2: The number of tableaux that can be formed from $\{1,2,3,\ldots ,n\}$ is equal to the number of involutions on $\{1,2,3,\ldots ,n\}$.

Proof: If $\pi$ is an involution corresponding to $(P,Q)$, then $\pi =\pi ^{-}$ corresponds to $(Q,P)$; hence $P=Q$. Conversely, if $\pi$ is any permutation corresponding to $(P,P)$, then $\pi ^{-}$ also corresponds to $(P,P)$; hence $\pi =\pi ^{-}$. So there is a one-one correspondence between involutions $\pi$ and tableax $P$

The number of involutions on $\{1,2,3,\ldots ,n\}$ is given by the recurrence:

$a(n)=a(n-1)+(n-1)a(n-2)\,$

Where $a(1)=1,a(2)=2$. By solving this recurrence we can get the number of involutions on $\{1,2,3,\ldots ,n\}$,

$I(n)=n!\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {1}{2^{k}k!(n-2k)!}}$

Symmetric matrices

Let $A=A^{T}$ and let the RSK algorithm map the matrix $A$ to the pair $(P,P)$, where $P$ is an SSYT of shape $\alpha$. Let $\alpha =(\alpha _{1},\alpha _{2},\ldots )$ where the $\alpha _{i}\in N$ and $\sum \alpha _{i}<\infty$. Then the map $A\longmapsto P$ establishes a bijection between symmetric matrices with row($A$) $=\alpha$ and SSYT's of type $\alpha$.

Applications of the RSK correspondence

Cauchy's identity

One has

$\prod _{i,j}(1-x_{i}y_{j})^{-1}=\sum _{\lambda }s_{\lambda }(x)s_{\lambda }(y)$

where $s_{\lambda }$ are Schur functions.

Kostka numbers

Fix partitions $\mu ,\nu \vdash n$, then

$\sum _{\lambda \vdash n}K_{\lambda \mu }K_{\lambda \nu }=N_{\mu \nu }$

where $K_{\lambda \mu }$ and $K_{\lambda \nu }$ denote the Kostka numbers and $N_{\mu \nu }$ is the number of matrices $A$, with non-negative elements, with row row($A$) $=\mu$ and column($A$) $=\nu$.

Notes et références

Bibliographie

• William Fulton, Young tableaux, Cambridge University Press, coll. « London Mathematical Society Student Texts » (n^o 35), 1997 (ISBN 978-0-521-56144-0; 978-0-521-56724-4^{[à vérifier : ISBN invalide]})lien Math Reviews

• Donald E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34,‎ 1970, p. 709–727 (ISSN 0030-8730, lire en ligne)

• Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, Second Edition, Addison-Wesley, 2005 (ISBN 0-201-89685-0, présentation en ligne)

• Gilbert de Beauregard Robinson, « On the Representations of the Symmetric Group », American Journal of Mathematics, vol. 60, n^o 3,‎ 1938, p. 745–760 (ISSN 0002-9327, DOI 10.2307/2371609, JSTOR 2371609) Zentralblatt 0019.25102

• (en) Bruce E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Springer, coll. « Graduate Texts in Mathematics » (n^o 203), 2001, 2^e éd. (ISBN 0-387-95067-2)

• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999 (ISBN 0-521-56069-1, présentation en ligne)lien Math Reviews

• Craige Schensted, « Longest increasing and decreasing subsequences », Canadian Journal of Mathematics, vol. 13,‎ 1961, p. 179–191 (ISSN 0008-414X, DOI 10.4153/CJM-1961-015-3, lire en ligne)lien Math Reviews