Correspondencia Robinson-Schensted-Knuth

En matemáticas , la correspondencia Robinson-Schensted-Knuth , también conocida como correspondencia RSK o algoritmo RSK , es una biyección combinatoria entre matrices A con entradas de números enteros no negativos y pares ( P , Q ) de cuadros de Young semiestándar de igual forma, cuyo tamaño es igual a la suma de las entradas de A . Más precisamente, el peso de P viene dado por las sumas de las columnas de A y el peso de Q por las sumas de las filas. Es una generalización de la correspondencia Robinson-Schensted , en el sentido de que tomando A como una matriz de permutación , el par ( P , Q ) será el par de cuadros estándar asociados a la permutación bajo la correspondencia Robinson-Schensted.

La correspondencia Robinson-Schensted-Knuth amplía muchas de las propiedades notables de la correspondencia Robinson-Schensted , en particular su simetría: la transposición de la matriz A da como resultado el intercambio de los cuadros P , Q.

La correspondencia Robinson-Schensted-Knuth

Introducción

La correspondencia Robinson-Schensted es un mapeo biyectivo entre permutaciones y pares de cuadros de Young estándar , ambos con la misma forma. Esta biyección se puede construir utilizando un algoritmo llamado inserción de Schensted , comenzando con un cuadro vacío e insertando sucesivamente los valores σ ₁ , ..., σ _n de la permutación σ en los números 1, 2, ..., n ; estos forman la segunda línea cuando σ se da en notación de dos líneas:

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

El primer cuadro estándar P es el resultado de inserciones sucesivas; el otro cuadro estándar Q registra las formas sucesivas de los cuadros intermedios durante la construcción de P.

La inserción de Schensted se generaliza fácilmente al caso en el que σ tiene entradas repetidas; en ese caso, la correspondencia producirá un cuadro semiestándar P en lugar de un cuadro estándar, pero Q seguirá siendo un cuadro estándar. La definición de la correspondencia RSK restablece la simetría entre los cuadros P y Q al producir también un cuadro semiestándar para Q.

matrices de dos líneas

La matriz de dos líneas (o permutación generalizada ) w _A correspondiente a una matriz A se define ^[1] como

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

en el que para cualquier par ( i , j ) que indexe una entrada Ai _{, j} de A , hay columnas Ai _{, j} iguales a y todas _las columnas están en orden lexicográfico, lo que significa _que ${\displaystyle {\tbinom {i}{j}}}$

1. ${\displaystyle i_{1}\leq i_{2}\leq i_{3}\cdots \leq i_{m}}$, y
2. si y entonces . ${\displaystyle i_{r}=i_{s}\,}$ ${\displaystyle r\leq s}$ ${\displaystyle j_{r}\leq j_{s}}$

Ejemplo

La matriz de dos líneas correspondiente a

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

es

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

Definición de la correspondencia

Al aplicar el algoritmo de inserción de Schensted a la línea inferior de esta matriz de dos líneas, se obtiene un par que consta de un cuadro semiestándar P y un cuadro estándar Q ₀ , donde este último puede convertirse en un cuadro semiestándar Q reemplazando cada entrada b de Q ₀ por la b -ésima entrada de la línea superior de w _A . Se obtiene así una biyección de matrices A a pares ordenados, ^[2] ( P , Q ) de cuadros de Young semiestándar de la misma forma, en los que el conjunto de entradas de P es el de la segunda línea de w _A , y el conjunto de entradas de Q es la de la primera línea de w _A . Por lo tanto , el número de entradas j en P es igual a la suma de las entradas en la columna j de A , y el número de entradas i en Q es igual a la suma de las entradas en la fila i de A.

Ejemplo

En el ejemplo anterior, el resultado de aplicar la inserción de Schensted para insertar sucesivamente 1,3,3,2,2,1,2 en un cuadro inicialmente vacío da como resultado un cuadro P y un cuadro estándar adicional Q ₀ que recodifica las formas sucesivas. , dada por

${\displaystyle 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}},}$

y después de reemplazar las entradas 1,2,3,4,5,6,7 en Q ₀ sucesivamente por 1,1,1,2,2,3,3 se obtiene el par de cuadros semiestándar

${\displaystyle 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}}.}$

Definición directa de la correspondencia RSK.

La definición anterior utiliza el algoritmo de Schensted, que produce un cuadro de registro estándar Q ₀ y lo modifica para tener en cuenta la primera línea de la matriz de dos líneas y producir un cuadro de registro semiestándar; esto hace evidente la relación con la correspondencia Robinson-Schensted . Sin embargo, es natural simplificar la construcción modificando la parte del algoritmo que registra la forma para tener en cuenta directamente la primera línea de la matriz de dos líneas; De esta forma se suele describir el algoritmo para la correspondencia RSK. Esto simplemente significa que después de cada paso de inserción de Schensted, el cuadro Q se extiende agregando, como entrada del nuevo cuadrado, la b -ésima entrada i _b de la primera línea de w _A , donde b es el tamaño actual de los cuadros. Que esto siempre produce un cuadro semiestándar se desprende de la propiedad (observada por primera vez por Knuth ^[2] ) de que para inserciones sucesivas con un valor idéntico en la primera línea de w _A , cada cuadrado sucesivo agregado a la forma está en una columna estrictamente a la derecha del anterior.

A continuación se muestra un ejemplo detallado de esta construcción de ambos cuadros semiestándar. Correspondiente a una matriz

${\displaystyle 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}}}$

uno tiene la matriz de dos líneas

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

La siguiente tabla muestra la construcción de ambos cuadros para este ejemplo.

Propiedades combinatorias de la correspondencia RSK.

El caso de las matrices de permutación.

Si es una matriz de permutación , RSK genera Young Tableaux (SYT) estándar, de la misma forma . Por el contrario, si SYT tiene la misma forma , entonces la matriz correspondiente es una matriz de permutación. Como resultado de esta propiedad, simplemente comparando las cardinalidades de los dos conjuntos en los dos lados del mapeo biyectivo obtenemos el siguiente corolario: ${\displaystyle A}$ ${\displaystyle P,Q}$ ${\displaystyle \lambda }$ ${\displaystyle P,Q}$ ${\displaystyle \lambda }$ ${\displaystyle A}$

Corolario 1 : Para cada uno tenemos donde las medias varían en todas las particiones de y es el número de cuadros de formas estándar de Young . ${\displaystyle n\geq 1}$ ${\displaystyle \sum _{\lambda \vdash n}(t_{\lambda })^{2}=n!}$ ${\displaystyle \lambda \vdash n}$ ${\displaystyle \lambda }$ ${\displaystyle n}$ ${\displaystyle t_{\lambda }}$ ${\displaystyle \lambda }$

Simetría

Sea una matriz con entradas no negativas. Supongamos que el algoritmo RSK se asigna a luego el algoritmo RSK se asigna a , donde es la transpuesta de . ^[1] ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle (P,Q)}$ ${\displaystyle A^{T}}$ ${\displaystyle (Q,P)}$ ${\displaystyle A^{T}}$ ${\displaystyle A}$

En particular para el caso de matrices de permutación, se recupera la simetría de la correspondencia Robinson-Schensted: ^[3]

Teorema 2 : Si la permutación corresponde a un triple , entonces la permutación inversa ,, corresponde a . ${\displaystyle \sigma }$ ${\displaystyle (\lambda ,P,Q)}$ ${\displaystyle \sigma ^{-1}}$ ${\displaystyle (\lambda ,Q,P)}$

Esto lleva a la siguiente relación entre el número de involuciones y el número de cuadros que se pueden formar (una involución es una permutación que es su propia inversa ): ^[3] ${\displaystyle S_{n}}$ ${\displaystyle S_{n}}$

Corolario 2 : El número de cuadros que se pueden formar es igual al número de involuciones de . ${\displaystyle \{1,2,3,\ldots ,n\}}$ ${\displaystyle \{1,2,3,\ldots ,n\}}$

Prueba : Si es una involución correspondiente a , entonces corresponde a ; por eso . Por el contrario, si alguna permutación corresponde a , entonces también corresponde a ; por eso . Entonces hay una correspondencia uno a uno entre involuciones y cuadros. ${\displaystyle \pi }$ ${\displaystyle (P,Q)}$ ${\displaystyle \pi =\pi ^{-}}$ ${\displaystyle (Q,P)}$ ${\displaystyle P=Q}$ ${\displaystyle \pi }$ ${\displaystyle (P,P)}$ ${\displaystyle \pi ^{-}}$ ${\displaystyle (P,P)}$ ${\displaystyle \pi =\pi ^{-}}$ ${\displaystyle \pi }$ ${\displaystyle P}$

El número de involuciones viene dado por la recurrencia: ${\displaystyle \{1,2,3,\ldots ,n\}}$

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

Dónde . Resolviendo esta recurrencia podemos obtener el número de involuciones en , ${\displaystyle a(1)=1,a(2)=2}$ ${\displaystyle \{1,2,3,\ldots ,n\}}$

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

Matrices simétricas

Dejemos que el algoritmo RSK asigne la matriz al par , donde hay un SSYT de forma . ^[1] Sea donde sean números enteros no negativos y . Luego el mapa establece una biyección entre matrices simétricas con y SSYT de peso . ${\displaystyle A=A^{T}}$ ${\displaystyle A}$ ${\displaystyle (P,P)}$ ${\displaystyle P}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\ldots )}$ ${\displaystyle \alpha _{i}}$ ${\textstyle \sum _{i}\alpha _{i}<\infty }$ ${\displaystyle A\longmapsto P}$ ${\displaystyle \mathrm {row} (A)=\alpha }$ ${\displaystyle \alpha }$

Aplicaciones de la correspondencia RSK

La identidad de Cauchy.

La correspondencia Robinson-Schensted-Knuth proporciona una prueba biyectiva directa de la siguiente identidad célebre para funciones simétricas:

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

¿Dónde están las funciones de Schur ? ${\displaystyle s_{\lambda }}$

Números de Kostka

Arreglar particiones , entonces ${\displaystyle \mu ,\nu \vdash n}$

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

donde y denotan los números de Kostka y es el número de matrices , con elementos no negativos, con y . ${\displaystyle K_{\lambda \mu }}$ ${\displaystyle K_{\lambda \nu }}$ ${\displaystyle N_{\mu \nu }}$ ${\displaystyle A}$ ${\displaystyle \mathrm {row} (A)=\mu }$ ${\displaystyle \mathrm {column} (A)=\nu }$

Referencias

1. Stanley, Richard P. (1999). Combinatoria enumerativa . vol. 2. Nueva York: Cambridge University Press. págs. 316–380. ISBN 0-521-55309-1.
2. Knuth, Donald E. (1970). "Permutaciones, matrices y cuadros de Young generalizados". Revista Pacífico de Matemáticas . 34 (3): 709–727. doi : 10.2140/pjm.1970.34.709 . SEÑOR  0272654.
3. Knuth, Donald E. (1973). El arte de la programación informática, vol. 3: Ordenar y buscar . Londres: Addison-Wesley. págs. 54–58. ISBN 0-201-03803-X.

• Brualdi, Richard A. (2006). Clases de matrices combinatorias. Enciclopedia de Matemáticas y sus aplicaciones. vol. 108. Cambridge: Prensa de la Universidad de Cambridge . págs. 135-162. ISBN 0-521-86565-4. Zbl  1106.05001.