Tres lecciones en combinatoria algebraica

1. Introducción

En esta serie de tres artículos, damos una exposición de varios resultados y problemas abiertos en tres áreas de la combinatoria algebraica y geométrica: las matrices totalmente no negativas, las representaciones de \(S_n\), y los arreglos de hiperplanos. Esta primera parte presenta una introducción a las matrices totalmente no negativas, y su relación con las funciones simétricas.

En marzo de 2003 se llevó a cabo el Primer Encuentro Colombiano de Combinatoria en Bogotá, Colombia. Como parte del encuentro, se organizaron tres minicursos, dictados por Federico Ardila, Mercedes Rosas, y Mark Skandera. Esta serie resume el material presentado en estos cursos en tres artículos: I. Matrices totalmente no negativas y funciones simétricas [3] lo estás leyendo, II. Las funciones simétricas y la teoria de las representaciones [4]F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 2. Representaciones del grupo simétrico, universo.math, por aparecer., y III. Arreglos de hiperplanos [5]F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 3. Aspectos combinatorios de los arreglos de hiperplanos, universo.math, por aparecer..

Uno de los mensajes que quisimos transmitir en nuestros minicursos es la idea de que muchos problemas en matemáticas se entienden mejor mediante el estudio de los objetos combinatorios que los subyacen, como grafos, particiones y conjuntos parcialmente ordenados (posets). En este primer artículo, veremos la utilidad de estos objetos combinatorios en el estudio de las matrices totalmente no negativas y las funciones simétricas.

2. Matrices totalmente no negativas

Sea \(A\) una matriz \(n \times n\) y sean \(I\) e \(I'\) dos subconjuntos de \([n] = \{1,\dotsc,n\} \).

Definimos \(A_{I,I'}\) como la submatriz de \(A\) que se construye a partir de \(A\) con las entradas correspondientes a las filas en \(I\) y las columnas en \(I'\). El determinante de esta submatriz recibe el nombre del menor \( (I,I')\) de \(A\), y se escribe $$ \Delta_{I,I'} = \det\ A_{I,I'}.$$ (Para hablar del menor \( (I,I') \) necesitamos que \( |I|=|I'|\).) Decimos que una matriz es totalmente no negativa si todos sus menores son mayores que o iguales a cero y totalmente positiva si todos los menores son mayores que cero.

Un ejemplo de una matriz totalmente no negativa es \begin{equation}\label{eqmatrizdecaminos} \begin{bmatrix} 5 & 6 & 3 & 0 \\ 4 & 7 & 4 & 0 \\ 1 & 4 & 4 & 2 \\ 0 & 1 & 2 & 3 \end{bmatrix}. \end{equation} Se puede verificar, aunque sea tedioso, que todos los menores de la matriz anterior, como por ejemplo \begin{equation*} \Delta_{\{1,2\},\{1,3\}} = \det\ \begin{bmatrix} 5 & 3 \\ 4 & 4 \end{bmatrix} = 8, \end{equation*} son mayores que o iguales a cero.

Las matrices totalmente no negativas aparecen en varias áreas de la matemática como ecuaciones diferenciales [16]F. R. Gantmacher and M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, AMS Chelsea Publishing, Providence, 2002, Edited by A.Eremenko. Translation based on the 1941 Russian original., raíces de polinomios [1]M. Aissen, I. J. Schoenberg, and A. Whitney, On generating functions of totally positive sequences, J. Anal. Math. 2 (1952), 93-103., [2, p.241]T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219., [15, Cap. 15]F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959., procesos estocásticos [20]S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141-1164., [10]S. Fomin, Loop-erased walks and total positivity, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3563-3583., matroides [22]B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90., grupos de Lie [25]G. Lusztig, Total positivity in reductive groups, Lie Theory and Geometry: in Honor of Bertram Kostant, Progress in Mathematics, vol. 123, Birkhäuser, Boston, 1994, pp. 531-568., geometría algebraica [11]S. Fomin and M. Shapiro, Stratified spaces formed by totally positive varieties, Michigan Math. J. 48 (2000), 253-270., [12]S. Fomin and A. Zelevinsky, Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12 (1999), 335-380., [27]A. Postnikov, Quantum Bruhat graph and Schubert polynomials, Proc. Amer. Math. Soc. 133 (2005), no. 3, 699-709 (electronic)., y conjuntos parcialmente ordenados [32]M. Skandera, A characterization of (3 + 1)-free posets, J. Combin. Theory Ser. A 93 (2001), no. 2, 231-241., [36]M. Skandera and B. Reed, Total nonnegativity and (3 + 1)-free posets, J. Combin. Theory Ser. A 103 (2003), 237-256.. Estas matrices aparecen también en economía [19]S. Karlin, Mathematical methods and theory in games, programming, and economics, Addison-Wesley, Reading, MA, 1959., ingeniería eléctrica [8]E. Curtis, D. V. Ingerman, and J. Morrow, Circular planar graphs and resistor networks, Linear Algebra Appl. 283 (1998), 115-150. y química [30]H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1984), no. 1, 89-99..

En los artículos de Karlin y McGregor [20]S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141-1164. y Lindström [22]B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90., estas matrices surgieron en conexión con ciertos grafos denominados redes planas. Una red plana de orden \(n\) es un grafo dirigido acíclico que se puede dibujar en el plano sin que las aristas se corten en puntos diferente de los vértices, tal que hay \(2n\) vértices distinguidos: \(n\) fuentes (a las cuales no llega ninguna arista) y \(n\) destinos (de los cuales no sale ninguna arista).

La Figura 1 muestra una red plana de orden \(4\). En nuestras figuras, siempre ubicaremos a las fuentes y a los destinos en los extremos izquierdo y derecho del grafo, respectivamente, y les daremos las etiquetas \(s_1,\dotsc,s_n, t_n,\dotsc,t_1\) de arriba hacia abajo. También daremos por supuesto que cada arista está orientada hacia la derecha (a menos que indiquemos otra orientación).

Dada una red plana, definimos la matriz de caminos $A = [a_{ij}]$ de $G$ como \begin{equation*} a_{ij} = \# \text{ caminos desde $s_i$ hasta $t_j$ en $G$.} \end{equation*} La matriz de caminos de la red plana en la Figura 1 se muestra en \eqref{eqmatrizdecaminos}.

Teorema 2.1 (Lema de Lindström).

La matriz de caminos de una red plana es totalmente no negativa. El menor $\Delta_{I,J}$ es igual al número de familias de $n$ caminos disjuntos desde las fuentes $I$ hasta los destinos $J$.

Demostración. Usando inducción, supongamos que para todas las redes planas de orden menor que \(n\), las matrices de caminos correspondientes son totalmente no negativas. (Esto es cierto para \(n=1\).) Sea \(G\) una red plana de orden \(n\) con matriz de caminos \(A\). Dado que cada submatriz de $A$ es la matriz de caminos de una subred de \(G\), es suficiente mostrar simplemente que el determinante de \(A\) es igual al número de familias \(\pi = (\pi_1,\dotsc, \pi_n)\) de \(n\) caminos en \(G\) en las cuales \(\pi_i\) es un camino desde \(s_i\) hasta \(t_i\), por \(i=1,\dotsc,n\), y en las cuales no hay ningún vértice que pertenece a dos caminos.

Veamos el producto \(a_{1,\sigma(1)} \cdots a_{n,\sigma(n)}\), que aparece en el determinante de \(A\), \begin{equation*} \det A = \sum_{\sigma \in S_n} \text{sgn}(\sigma)a_{1,\sigma(1)} \cdots a_{n,\sigma(n)}. \end{equation*} Este producto es igual al número de familias de \(n\) caminos en \(G\) en las cuales el camino \(i\) va desde \(s_i\) hasta \(t_{\sigma(i)}\), donde se permiten intersecciones. Sea \( \pi = (\pi_1,\dotsc,\pi_n)\) una familia en la cual hay por lo menos una intersección; sea $j$ el menor índice tal que los caminos $\pi_j$ y $\pi_{j+1}$ se intersectan, y consideremos su primera intersección. El conjunto de aristas utilizadas por $\pi$ es el mismo conjunto de aristas utilizadas por la familia \begin{equation*} \pi^* = (\pi_1,\dotsc,\pi_{j-1}, \pi_j', \pi_{j+1}',\pi_{j+2},\dotsc,\pi_n) \end{equation*} que se construye intercambiando a los caminos $\pi_j$ y $\pi_{j+1}$ a partir de su primera intersección. (Vea la Figura 2.)

La familia $\pi^*$ es contada por $a_{1,\sigma(1)} \cdots a_{j-1,\sigma(j-1)} a_{j,\sigma(j+1)} a_{j+1,\sigma(j)} a_{j+2,\sigma(j+2)} \cdots a_{n,\sigma(n)}$, y aparece en $\det A$ con el signo contrario al de $\pi$, ya que las dos permutaciones difieren en una transposición. Tenemos entonces que la contribución total de estas dos familias al determinante es cero. Observemos además que $(\pi^*)^*=\pi$.

Por lo tanto, en la expresión del determinante, las familias $\pi$ que se intersectan están emparejadas de manera que la contribución total de cada pareja es $0$. Entre tanto, las familias $\pi$ que no se intersectan tienen que unir a $s_i$ con $t_i$ para cada $i$; por lo tanto, en la expresión del determinante, todas aparecen con signo positivo. El resultado se sigue.

\(\square \)

El Lema de Lindström nos da una demostración fácil de que ciertas matrices son totalmente no negativas. Por ejemplo las matrices \begin{equation}\label{eq:singledouble} A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}, \qquad B = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & 2 & 1 & 0 \\ 4 & 3 & 2 & 1 \end{bmatrix} \end{equation} son totalmente no negativas porque son las matrices de caminos de las redes planas de la Figura 3, donde las aristas tienen orientación hacia la derecha y hacia arriba.

Lindström [22]B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90. (y Karlin y McGregor [20]S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141-1164.) demostraron el Teorema 2.1 de forma más general. Dado una red plana $G$ cuyas aristas tienen pesos positivos y reales, definimos el peso de un camino como el producto de los pesos de sus aristas y definimos la matriz de pesos $A = [a_{ij}]$ de $G$ como \begin{equation*} a_{ij} = \text{suma de pesos de caminos desde $s_i$ hasta $t_j$ en $G$.} \end{equation*} La matriz de pesos también es totalmente no negativa y sus menores se pueden interpretar de manera similar:

Teorema 2.2.

La matriz de pesos de una red plana es totalmente no negativa. El menor $\Delta_{I,J}$ es igual a la suma de los pesos de las familias de caminos disjuntos desde las fuentes $I$ hasta los destinos $J$.

Observe que el Teorema 2.1 es el caso especial del Teorema 2.2 que corresponde a darle peso $1$ a cada arista. La demostración del Teorema 2.2 es muy similar a la del Teorema 2.1.

La Figura 3 ilustra una propiedad interesante de las matrices totalmente no negativas. Las matrices en (\ref{eq:singledouble}) satisfacen la ecuación $A^2 = B$, y se puede construir una red plana que corresponde a $B$ utilizando dos copias de la red que corresponde a $A$. En general, concatenar redes planas corresponde a multiplicar matrices totalmente no negativas. Este hecho se sigue directamente de la definición de multiplicación de matrices.

La correspondencia entre multiplicación de matrices y concatenación de redes tiene una consecuencia extraordinaria. A. Whitney [41]A. Whitney, A reduction theorem for totally positive matrices, J. Anal. Math. 2 (1952), 88-92. y Loewner [23]C. Loewner, On totally positive matrices, Math. Z. 63 (1955), 338-340. demostraron que cada matriz totalmente no negativa e invertible se puede factorizar como un producto de matrices totalmente no negativas \begin{equation}\label{eq:factortnn} L_1 \cdots L_m D U_1 \cdots U_m, \end{equation} tal que $D$ es una matriz diagonal, $L_i$ tiene la forma $I + cE_{j+1,j}$ y $U_i$ tiene la forma $I + cE_{j,j+1}$, donde $E_{k,\ell}$ es la matriz que tiene un $1$ en la posición $k,\ell$ y ceros en todas las demás posiciones. Cryer [7]C. W. Cryer, Some properties of totally positive matrices, Linear Algebra Appl. 15 (1976), 1-25. extendió este resultado a cualquier matriz totalmente no negativa. Está claro que los factores que aparecen en (\ref{eq:factortnn}) son matrices de pesos de redes planas [6]F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A 71 (1995), no. 2, 175-218.; la Figura 4 muestra las redes planas cuyas matrices de pesos son \begin{equation*} \begin{bmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & d \end{bmatrix}, \qquad \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & e & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \qquad \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & f \\ 0 & 0 & 0 & 1 \end{bmatrix}. \end{equation*} Vemos entonces que las matrices de pesos no son solamente una clase importante de matrices totalmente no negativas; las contiene a todas.

   

Teorema 2.3.

Cada matriz $n \times n$ que es totalmente no negativa es la matriz de pesos de una red plana de orden $n$.

Aunque no existe una única red plana que corresponda a una fija matriz totalmente no negativa, si la matriz es invertible, podemos elegir una red plana que tenga la forma mostrada en la Figura 5 [13]S. Fomin and A. Zelevinsky, Total positivity: Tests and parametrizations, Math. Intelligencer 22 (2000), no. 1, 23-33.. Entonces podemos calcular de manera única los pesos indicados por $*$. Estos pesos son funciones racionales de las entradas de la matriz. Entonces si la matriz tiene entradas enteras, los pesos serán números racionales.

Observación 2.4.

Para cada matriz $A$ totalmente no negativa con entradas enteras, existe un entero $k$ tal que $kA$ es la matriz de caminos de una red plana sin pesos.

Como es de esperarse, el hecho de que una matriz sea totalmente no negativa nos da información sobre sus valores propios.

Teorema 2.5.

Todos los valores propios de una matriz totalmente no negativa son números reales.

Demostración. Una demostración sencilla utiliza álgebra exterior. (Vea [2, pp.167-172]T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219..) Dada una matriz $A$ de $n \times n$, la potencia exterior $k$ de $A$, escrita $\wedge^k A$, se puede definir como la matriz $\binom{n}{k} \times \binom{n}{k}$ cuyas filas y columnas son los subconjuntos de $[n]$ con $k$ elementos y cuya entrada $I,J$ es $\Delta_{I,J}$, el menor $(I,J)$ de $A$. Los valores propios de $\wedge^k A$ son todos los $\binom{n}{k}$ productos de $k$ valores propios de $A$ (contando multiplicidades).

Veamos primero el caso de una matriz totalmente positiva. Sea $A$ una matriz totalmente positiva cuyos valores propios son $\lambda_1,\dotsc,\lambda_n$, con \begin{equation*} |\lambda_1| \geq \cdots \geq |\lambda_n|. \end{equation*} Las entradas de $A$, al ser los menores de $1 \times 1$, son positivas. Entonces el Teorema de Perron-Frobenius (Vea [24, p. 189]D. Luenberger, Introduction to dynamic systems, Wiley, 1979..) nos dice que $\lambda_1$ es el único valor propio de máximo valor absoluto y que $\lambda_1$ es positivo. Aplicando el Teorema de Perron-Frobenius a $\wedge^2 A, \wedge^3 A,\dotsc, \wedge^n A$ vemos que cada matriz tiene un único valor propio de valor absoluto máximo. Estos valores propios son $\lambda_1\lambda_2, \lambda_1\lambda_2\lambda_3, \dotsc, \lambda_1\cdots\lambda_n$, respectivamente. Dado que cada valor propio es positivo, vemos entonces que los números $\lambda_1,\dotsc,\lambda_n$ también son positivos.

Ahora supongamos que $A$ es totalmente no negativa. Un resultado conocido dice que $A$ es el límite de una sucesión de matrices totalmente positivas. (Vea [2, Tm. 2.7]T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219. o [13, Tm.11]S. Fomin and A. Zelevinsky, Total positivity: Tests and parametrizations, Math. Intelligencer 22 (2000), no. 1, 23-33..) Dado que los valores propios de estas matrices convergen a los valores propios de $A$, éstos tienen que ser reales y no negativos.

$\square$

Veremos en la Sección 3 que existen matrices infinitas importantes que son totalmente no negativas. Aunque no está claro que podamos generalizar el Teorema 2.3 al caso infinito, podemos generalizar el Teorema 2.2. Por ejemplo la matriz $D = [d_{ij}]$ definida como $$ d_{ij} = \left\{ \begin{array}{cl} \binom{i}{j} &\text{si } j \leq i,\\ 0 & \text{si no} \end{array}\right. $$ es totalmente no negativa y es la matriz de caminos de la red plana infinita de la Figura 6 [17]I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58 (1985), no. 3, 300-321.. (Las aristas tienen orientación hacia la derecha y hacia arriba.)

3. Funciones simétricas

En varias situaciones donde se usan matrices totalmente no negativas también se usan funciones simétricas. Un polinomio $f(x) = f(x_1,\dotsc,x_n)$ recibe el nombre de función simétrica si satisface que \begin{equation*} f(x_1,\dotsc,x_{i-1},x_{i+1},x_i,x_{i+2},\dotsc,x_n) = f(x) \end{equation*} para $i=1,\dotsc,n-1$. Equivalentemente, el polinomio $f(x)$ es una función simétrica si cualquier reordenamiento de las variables deja el polinomio invariante. (Para mayor información, vea [26, Cap.1]I.G. Macdonald, Symmetric Fuctions and Hall Polynomials, Oxford University Press, Oxford, 1979., [31, Cap. 4]B. Sagan, The symmetric group, Springer, New York, 2001., [39, Cap. 7]R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999..) Note que nuestra terminología es un poco engañosa: una expresión como $\sqrt{x_1x_2}$, que es simétrica pero no es polinomial, no recibe el nombre de función simétrica aunque sea una función con la propiedad de simetría.

Unos ejemplos sencillos de funciones simétricas son las funciones elementales, \begin{align*} &e_1(x) = x_1 + x_2 + \cdots = \sum_{i=1}^n x_i,\\ &e_2(x) = x_1x_2 + x_1x_3 + x_2x_3 + \cdots = \sum_{i=1}^{n-1}\sum_{j=i+1}^n x_ix_j,\\ &\vdots \\ &e_n(x) = x_1\cdots x_n,\\ &e_{n+1}(x) = 0,\\ &\vdots \end{align*} las funciones homogéneas (completas), \begin{align*} h_1(x) &= x_1 + x_2 + \cdots = \sum_{i=1}^n x_i,\\ h_2(x) &= x_1^2 + x_1x_2 + x_2^2 + x_1x_3 + x_2x_3 + x_3^2 + \cdots = \sum_{i=1}^n\sum_{j=i}^n x_ix_j,\\ &\vdots \\ h_m(x) &= \sum_{1 \leq i_1 \leq \cdots i_m \leq n} x_{i_1} \cdots x_{i_m},\\ &\vdots \end{align*} y las funciones de sumas de potencias, \begin{align*} p_1(x) &= x_1 + x_2 + \cdots = \sum_{i=1}^n x_i,\\ p_2(x) &= x_1^2 + x_2^2 + x_3^2 + \cdots = \sum_{i=1}^n x_i^2,\\ &\vdots \\ p_m(x) &= \sum_{i=1}^n x_i^m.\\ &\vdots \end{align*} Note que el nombre función homogénea también es un poco engañoso: todas las funciones arriba son polinomios homogéneos. A veces conviene utilizar un vector infinito $x= (x_1, x_2,\dotsc)$ de variables; es claro como definir las funciones anteriores en este caso. Así tenemos que $e_m(x)\neq 0$ para todo valor de $m$.

Cualquier función simétrica $f(x)$ se puede expresar como una combinación lineal de productos de funciones elementales, de funciones homogéneas o de funciones de sumas de potencias. En cada caso, esta expresión siempre es única. (Equivalentemente, estas clases de funciones forman tres bases para el anillo de funciones simétricas). Si $f$ tiene coeficientes enteros, entonces cuando escribimos $f$ como una combinación lineal de productos de funciones elementales o de funciones homogéneas, los coeficientes que obtenemos son números enteros. Por otra parte, si escribimos $f$ como una combinación lineal de productos de sumas de potencias, los coeficientes que obtenemos son números racionales. Por ejemplo tenemos que \begin{align*} e_4 &= -h_4 + 2h_3h_1 + h_2^2 -3 h_2h_1^2 + h_1^4, \\ &= -\frac14 p_4 +\frac13 p_3p_1 +\frac18 p_2^2 -\frac14 p_2p_1^2 +\frac1{24} p_1^4, \end{align*} \begin{align*} h_4 &= -e_4 + 2e_3e_1 + e_2^2 -3 e_2e_1^2 + e_1^4, \\ &= \frac14 p_4 +\frac13 p_3p_1 +\frac18 p_2^2 + \frac14 p_2p_1^2 +\frac1{24} p_1^4,\\ p_4 &= -4e_4 + 4e_3e_1 + 2e_2^2 - 4e_2e_1^2 + e_1^4, \\ &= 4h_4 - 4h_3h_1 - 2h_2^2 + 4h_2h_1^2 - h_1^4. \end{align*}

Cada una de estas tres clases de funciones tiene asociada una matriz totalmente no negativa. A la clase de las funciones elementales le asociamos la matriz de Toeplitz infinita \begin{equation}\label{eq:etnn} E = \begin{bmatrix} 1 & e_1 & e_2 & e_3 & e_4 & \ldots \\ 0 & 1 & e_1 & e_2 & e_3 & \ldots \\ 0 & 0 & 1 & e_1 & e_2 & \ldots \\ 0 & 0 & 0 & 1 & e_1 & \ldots \\ 0 & 0 & 0 & 0 & 1 & \ldots \\ \vdots & & & & \ddots & \ddots \end{bmatrix}. \end{equation} (Una matriz $A = [a_{ij}]$ recibe el nombre de Toeplitz si satisface $a_{i,j} = a_{i+k,j+k}$ para cada $k \geq 1$.) Esta matriz es totalmente no negativa en el sentido de que cada menor es una función simétrica con coeficientes positivos. Una tal función es denominada monomio-positiva. Si el vector de variables $x = (x_1,\dotsc,x_n)$ es finito, entonces la evaluación de $E$ en $n$ números no negativos resulta ser una matriz totalmente no negativa en el sentido corriente. La matriz $E$ es la matriz de pesos de la red plana de la Figura 7.

A la clase de las funciones homogéneas, le asociamos la matriz de Toeplitz \begin{equation}\label{eq:htnn} H = \begin{bmatrix} 1 & h_1 & h_2 & h_3 & h_4 & \ldots \\ 0 & 1 & h_1 & h_2 & h_3 & \ldots \\ 0 & 0 & 1 & h_1 & h_2 & \ldots \\ 0 & 0 & 0 & 1 & h_1 & \ldots \\ 0 & 0 & 0 & 0 & 1 & \ldots \\ \vdots & & & & \ddots & \ddots \end{bmatrix}. \end{equation} Esta matriz también es totalmente no negativa, ya que es la matriz de pesos de la red plana de la Figura 8, donde las aristas están dirigidas hacia la derecha y hacia abajo.

Para asociar una matriz totalmente no negativa a las funciones de sumas de potencias, necesitamos que el vector de variables $x = (x_1,\dotsc,x_n)$ sea finito. La matriz de Hankel \begin{equation}\label{eq:hankel} P = \begin{bmatrix} n & p_1 & p_2 & \ldots & p_{n-1} \\ p_1 & p_2 & p_3 & \ldots & p_n \\ p_2 & p_3 & p_4 & \ldots & p_{n+1} \\ \vdots & \vdots & \vdots & & \vdots \\ p_{n-1}& p_n & p_{n+1}& \ldots & p_{2n-2} \end{bmatrix} \end{equation} es totalmente no negativa para cualquier conjunto de valores no negativos $x_1,\dotsc,x_n$. (Una matriz $A = [a_{ij}]$ recibe el nombre de Hankel si satisface $a_{i,j} = a_{i+k,j-k}$ para $k = 1,\dotsc,j-1$. Vea [14, Cap. 10]F. R. Gantmacher, The Theory of Matrices, vol. 1, Chelsea, New York, 1959..) La matriz $P$ es igual al producto de una matriz de Vandermonde con su transpuesta, $P = VV^T$, donde \begin{equation}\label{eq:vandermonde} V = \begin{bmatrix} 1 & 1 & \ldots & 1 \\ x_1 & x_2 & \ldots & x_n \\ x_1^2 & x_2^2 & \ldots & x_n^2 \\ \vdots & \vdots & & \vdots \\ x_1^{n-1} & x_2^{n-1} & \ldots & x_n^{n-1} \end{bmatrix}. \end{equation} Si reemplazamos los variables por números reales que satisfacen \begin{equation}\label{eq:increasingpvars} 0 \leq x_1 \leq \cdots \leq x_n, \end{equation} se puede mostrar por inducción que $V$ es totalmente no negativa. (Vea por ejemplo [15,p. 99]F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959..) Concluimos entonces que la matriz $P$ también es totalmente no negativa.

Cuando las desigualdades (\ref{eq:increasingpvars}) son estrictas, la inducción anterior muestra que $V$ y $P$ son totalmente positivas. En este caso es fácil factorizar $V$ para construir una red plana. Ilustraremos esta construcción en el caso $n=4$. Tenemos que \begin{equation*} V = L_1L_2L_3 D U_3 U_2 U_1, \end{equation*} donde \begin{equation*} L_1L_2L_3 = \begin{bmatrix} 1 & 0 & 0 & 0 \\[0.34em] 1 & 1 & 0 & 0 \\[0.34em] 1 & 1 & 1 & 0 \\[0.34em] 1 & 1 & 1 & 1 \end{bmatrix} \ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & \tfrac{x_3-x_2}{x_2-x_1} & 1 & 0 \\ 0 & \tfrac{x_4-x_3}{x_2-x_1} & \tfrac{x_4-x_3}{x_3-x_2} & 1 \end{bmatrix} \ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\[0.3em] 0 & 0 & \tfrac{(x_4-x_3)(x_4-x_2)}{(x_3-x_2)(x_3-x_1)} & 1 \end{bmatrix}\, , \end{equation*} \begin{equation*} D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & x_2-x_1 & 0 & 0 \\ 0 & 0 & (x_3-x_2)(x_3-x_1) & 0 \\ 0 & 0 & 0 & (x_4-x_3)(x_4-x_2)(x_4-x_1) \end{bmatrix}\, , \end{equation*} \begin{equation*} U_3U_2U_1 = \begin{bmatrix} 1 & 0 & 0 & 0 \\[0.22em] 0 & 1 & 0 & 0 \\[0.22em] 0 & 0 & 1 & x_3 \\[0.22em] 0 & 0 & 0 & 1 \end{bmatrix} \ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & x_2 & x_2^2 \\ 0 & 0 & 1 & x_2 \\[0.27em] 0 & 0 & 0 & 1 \end{bmatrix} \ \begin{bmatrix} 1 & x_1 & x_1^2 & x_1^3 \\ 0 & 1 & x_1 & x_1^2 \\ 0 & 0 & 1 & x_1 \\ 0 & 0 & 0 & 1 \end{bmatrix}. \end{equation*} Concatenando las redes planas correspondientes, construimos la red plana de la Figura 9.

Las tres matrices totalmente no negativas (\ref{eq:etnn}), (\ref{eq:htnn}), (\ref{eq:hankel}) tienen aplicaciones en el problema de localizar las raíces de un polinomio. (El número $\alpha$ es denominado una raíz o un cero del polinomio $a(z)$ si tenemos que $a(\alpha) = 0$.)

En los teoremas siguientes, factorizaremos un polinomio real $a(z) = 1 + a_1 z + \cdots + a_nz^n$ como \begin{equation}\label{eq:myfactor} a(z) = \prod_{i=1}^n ( 1 + \beta_i z). \end{equation} Los números complejos $\beta_1,\dotsc,\beta_n$ son los inversos aditivos de los recíprocos de las raíces de $a(z)$. Por lo tanto, ellos son reales si y solamente si los ceros de $a(z)$ son reales.

El resultado siguiente es un caso especial de un teorema de Aissen, Schoenberg y Whitney [1]M. Aissen, I. J. Schoenberg, and A. Whitney, On generating functions of totally positive sequences, J. Anal. Math. 2 (1952), 93-103.

Teorema 3.1.

Sea $a(z) = 1 + a_1 z + \cdots + a_nz^n$ un polinomio con coeficientes positivos. Los ceros de $a(z)$ son reales si y solamente si la matriz de Toeplitz \begin{equation*} A = \begin{bmatrix} 1 & a_1 & a_2 & a_3 & a_4 & \ldots \\ 0 & 1 & a_1 & a_2 & a_3 & \ldots \\ 0 & 0 & 1 & a_1 & a_2 & \ldots \\ 0 & 0 & 0 & 1 & a_1 & \ldots \\ 0 & 0 & 0 & 0 & 1 & \ldots \\ \vdots & & & & \ddots & \ddots \end{bmatrix} \end{equation*} es totalmente no negativa, donde definimos $a_k=0$ para $k>n$.

Es inmediato que se puede reemplazar a la matriz $A$ por su transpuesta en el teorema anterior.

Note que cada coeficiente $a_i$ es igual a la función elemental $e_i(\beta_1,\dotsc,\beta_n)$. Por lo tanto la Figura 7 (donde cambiamos cada peso $x_i$ por $\beta_i$) nos da una red plana cuya matriz de pesos es $A$. Por otra parte, esta red plana no nos sirve para mostrar que los ceros de $a(z)$ son reales, ya que necesitamos saber cuáles son los ceros para poder dibujar la red.

Afortunadamente en algunos casos podemos construir una red plana para la matriz $A$ sin saber cuáles son los ceros de $a(z)$. Por ejemplo, la Figura 10 muestra una red plana sin pesos que demuestra que el polinomio $1 + 6z + 5z^2 + z^3$ tiene todos los ceros reales (sin usar los valores de ellos).

La dificultad con este método es que tenemos que adivinar la forma de la red plana. Además, no se sabe si existe una tal red plana sin pesos, ni siquiera en el caso en que el polinomio tenga todos sus coeficientes enteros.

Pregunta 3.1.

Sea $a(z)$ un polinomio en $\mathbb{N}[z]$ con todos los ceros reales. ¿Cuándo y cómo es posible construir una red plana sin pesos para mostrar que $a(z)$ tiene todos los ceros reales?

No está claro que sea suficiente multiplicar el polinomio $a(z)$ por un entero $k$ para poder responder a la Pregunta 3.1 afirmativamente, como sugiere la Observación 2.4. Equivalentemente, no se sabe si existe una red plana con pesos racionales para mostrar que $a(z)$ tiene todos los ceros reales. El único teorema de factorización de matrices infinitas de Toeplitz que son totalmente no negativas emplea números reales [1]M. Aissen, I. J. Schoenberg, and A. Whitney, On generating functions of totally positive sequences, J. Anal. Math. 2 (1952), 93-103.

Pregunta 3.2.

Sea $a(z)$ un polinomio en $\mathbb{N}[z]$ con todos los ceros reales. ¿Cuándo y cómo es posible construir una red plana con pesos racionales para mostrar que $a(z)$ tiene todos los ceros reales?

De manera similar al Teorema 3.1, el siguiente teorema emplea a las funciones de sumas de potencias para demostrar que un polinomio tiene todos sus ceros reales. Este teorema es una consecuencia de un resultado de Gantmacher [15, Cor. de Tm. 6, p. 203]F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959., en combinación con la positividad total de la matriz de Vandermonde (\ref{eq:vandermonde}). (Vea también [33, Tm. 6.5]M. Skandera, Interpretaciones del h-vector, Bol. Asoc. Mat. Venez. 2 (2001), 141-174..)

Teorema 3.2.

Sea $a(z) = 1 + a_1 z + \cdots + a_nz^n$ un polinomio con coeficientes positivos. Todos los ceros de $a(z)$ son reales y distintos si y solamente si la matriz de Hankel $P$ de (\ref{eq:hankel}) es totalmente positiva, donde $p_i$ es la suma de potencias $\beta_1^i + \cdots + \beta_n^i$, y $\beta_1,\dotsc,\beta_n$ son los números que aparecen en la factorización (\ref{eq:myfactor}).

Sin saber cuáles son los valores de $\beta_1,\dotsc,\beta_n$, es posible calcular la sumas de potencias en términos de los coeficientes $a_1,\dotsc,a_n$, que como ya hemos observado son las funciones simétricas elementales evaluadas en $\beta_1,\dotsc,\beta_n$. Otra vez es concebible que podamos construir una red plana sin pesos para mostrar que $a(z)$ tiene todos los ceros reales. Desa\-fortunadamente no se conoce un método general para realizar esta construcción, aun cuando la matriz $P$ tiene entradas enteras y la forma especial de Hankel.

Pregunta 3.3.

Sea $A$ una matriz totalmente no negativa con entradas enteras. ¿Cuándo y cómo es posible realizar $A$ como la matriz de caminos de una red plana sin pesos? ¿Cómo se puede encontrar el menor entero $k$ de modo que $kA$ sea realizable así? ¿Es más fácil el caso especial de matrices de Hankel?

El resultado de Gantmacher [15, Cor. de Tm. 6, p. 203]F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959. se puede modificar para aplicarse a los polinomios con ceros repetidos [15, Cap. 15, Sec. 11]F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959.. Sería interesante modificar el Teorema 3.2 también.

Pregunta 3.4.

Sea $a(z) = 1 + a_1 z + \cdots + a_nz^n$ un polinomio con coeficientes positivos. ¿Es cierto que todos los ceros de $a(z)$ son reales (y no necesariamente distintos) si y solamente si la matriz de Hankel $P$ (\ref{eq:hankel}) es totalmente no negativa?

4. Polinomios totalmente no negativos

Podemos considerar al determinante de una matriz $n \times n$ como un polinomio en $n^2$ variables $x = ( x_{11}, \dotsc, x_{nn})$ \begin{equation*} \det(x) = \sum_{\sigma \in S_n} \text{sgn}( \sigma ) x_{1,\sigma(1)} \cdots x_{n,\sigma(n)} \end{equation*} que se puede evaluar en una matriz $A = [a_{ij}]$ usando la sustitución $x_{ij} = a_{ij}$. Según la definición de las matrices totalmente no negativas, la evaluación de este polinomio en una matriz totalmente no negativa resulta siempre en un número no negativo. Un polinomio con esta propiedad se denomina totalmente no negativo. Los polinomios totalmente no negativos aparecen en la investigación de Lusztig [25]G. Lusztig, Total positivity in reductive groups, Lie Theory and Geometry: in Honor of Bertram Kostant, Progress in Mathematics, vol. 123, Birkhäuser, Boston, 1994, pp. 531-568., quien mostró que todos los elementos de la base canónica del anillo de coordenadas de $GL_n$ son polinomios totalmente no negativos. Para comprender mejor esta base, que todavía no tiene una descripción sencilla, quizás uno podría esperar caracterizar todos los polinomios totalmente no negativos, o por lo menos un subconjunto de ellos.

Fallat y sus colaboradores descubrieron un subconjunto de los polinomios totalmente no negativos que se puede describir en términos de menores principales. Un ejemplo es el polinomio \begin{equation}\label{eq:1324diff} \Delta_{\{1,3\}\{1,3\}} \Delta_{\{2\}\{2\}} - \Delta_{\{1\}\{1\}} \Delta_{\{2,3\}\{2,3\}}. \end{equation} Equivalentemente todas las matrices totalmente no negativas de tamaño por lo menos $3 \times 3$ satisfacen la desigualdad \begin{equation}\label{eq:13,24} \Delta_{\{1\}\{1\}} \Delta_{\{2,3\}\{2,3\}} \leq \Delta_{\{1,3\}\{1,3\}} \Delta_{\{2\}\{2\}}. \end{equation} Esta desigualdad y cuatro parecidas se muestran en la Figura 11 en la forma de un conjunto parcialmente ordenado. (Interpretamos el menor vacío $\Delta_{\emptyset,\emptyset}$ como $1$.)

Los Teoremas 1 y 3 proveen métodos para demostrar que los productos \begin{equation}\label{eq:products} \Delta_{13,13}\Delta_{2,2},\quad \Delta_{12,12}\Delta_{3,3},\quad \Delta_{1,1}\Delta_{23,23},\quad \Delta_{123,123}\Delta_{\emptyset, \emptyset} \end{equation} de menores de matrices totalmente no negativas están relacionados como indica la Figura 11. Para demostrarlo, observemos primero que estos teoremas implican el siguiente corolario.

Corolario 4.1.

Sea $A$ una matriz $n \times n$ totalmente no negativa, y sea $G$ una red plana cuya matriz de caminos es $A$. Sea $I$ un subconjunto de $[n]$ y sea ${\overline{I}} = [n] \smallsetminus I$ su complemento en $[n]$. Entonces el producto $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$ de menores de $A$ es igual a la suma de pesos de familias $\pi = (\pi_1,\dotsc,\pi_n)$ de caminos en $G$ con las siguientes características.

1. En cada camino, el índice de la fuente es igual al índice del destino.
2. Los caminos con índices en $I$ no se intersectan entre ellos, y los caminos con índices en ${\overline{I}}$ no se intersectan entre ellos.

Imaginando que las fuentes y los destinos con índices $I$ son de un color y que las fuentes y los destinos con índices ${\overline{I}}$ son de otro color, podemos interpretar el producto $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$ como el número de familias de caminos en las cuales cada camino tiene uno de dos colores y dos caminos del mismo color no se pueden intersectar.

Ahora consideremos los conjuntos de aristas que son contados por un producto $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$ pero no por otro. La Figura 12(a) muestra un conjunto de aristas que define una familia de caminos sin intersección. Este conjunto de aristas es contado por todos los cuatro productos (\ref{eq:products}), como se ve facilmente en las Figuras 12(a), 12(b), 12(c), y 12(d).

Figura 12. Coloraciones de una familia de tres caminos.

Por otra parte, el conjunto de aristas en la Figura 13(a) no es contado por todos los cuatro productos (\ref{eq:products}). Para que este conjunto de aristas determine una familia $2$-coloreable de caminos, las aristas $(s_1,u)$ y $(s_2,u)$ necesitan tener colores distintos, porque se intersectan en $u$. Entonces $s_1$ y $s_2$ tienen colores distintos. Por la misma razón $t_2$ y $t_3$ tienen colores distintos. Mirando las demás aristas, vemos que las aristas en la sucesión \begin{equation*} (s_3,v), (u,v), (u,y), (x,y), (x,z), (y,z), (z,t_1) \end{equation*} necesitan alternar de color. Por lo tanto $s_3$ y $t_1$ deben tener el mismo color. La Figura 13(b) muestra esta igualdad y las dos desigualdades.

Figura 13. Familias de caminos.

No es difícil mostrar que, al llevar a cabo este análisis para cualquier grafo que corresponde a una familia $2$-coloreable de tres caminos, el resultado pertenece siempre a una de las cinco categorías siguientes [34, Sec. 2] M. Skandera, Inequalities in products of minors of totally nonnegative matrices, J. Algebraic Combin. 20 (2004), no. 2, 195-211.:

$\quad$ $\quad$ $\quad$ $\quad$

Estos cinco diagramas señalan parejas de fuentes o de destinos que necesitan tener distintos colores, y parejas de una fuente y un destino que necesitan tener el mismo color.

(Vale la pena anotar que los cinco diagramas son una base del álgebra de Temperley-Lieb $T_3$, si definimos el producto de dos diagramas como su concatenación. En general formamos el álgebra de Temperley-Lieb $T_n$ con los $\tfrac{1}{n+1}\tbinom{2n}{n}$ diagramas análogos en $2n$ vértices. Llamamos a estos diagramas la base estándar de $T_n$. El número de Catalán $\tfrac{1}{n+1}\tbinom{2n}{n}$ aparece con gran frecuencia en la combinatoria algebraica. Vea por ejemplo [39, pp. 219-231]R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999..)

Entonces, para comparar productos de la forma $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$ en matrices totalmente no negativas $3 \times 3$, podemos usar subconjuntos de la base estándar del álgebra de Temperley-Lieb $T_3$. Para cada producto $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$, hacemos lo siguiente.

1. Dibujamos dos columnas de $n$ vértices. Llamamos a los vértices a la izquierda fuentes y a los vértices a la derecha destinos. (Los denotamos $s_1,\dotsc,s_n$ y $t_1,\dotsc,t_n$ como siempre.)
2. Para $i=1,\dotsc,n$, coloreamos $s_i$ y $t_i$ de rojo si $i \in I$, y de azul si $i \in {\overline{I}}$.
3. Apuntamos los elementos del álgebra de Temperley-Lieb $T_n$ que conectan solamente las parejas siguentes.
   1. dos fuentes de colores distintos.
   2. dos destinos de colores distintos.
   3. una fuente y un destino del mismo color.

Así, para cada producto $\Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}}$ obtenemos un subconjunto de la base estándar de $T_n$. Ordenando estos subconjuntos por inclusión, obtenemos todas las desigualdades de la forma \begin{equation}\label{eq:tnnineq} \Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}} \leq \Delta_{J,J}\Delta_{{\overline{J}},{\overline{J}}}. \end{equation} que son válidas para toda matriz totalmente no negativa. La Figura 14 muestra otra vez el poset de la Figura 11, ahora con productos de menores reemplazados por subconjuntos de la base estándar de $T_3$.

Hay un criterio más sencillo para comparar productos de menores de matrices totalmente no negativas [29]B. Rhoades and M. Skandera, Temperley-Lieb immanants, Ann. Comb. 9 (2005), no. 4, 451-494..

1. Dibujamos un camino de $n$ pasos de longitud uno, de modo que el paso $i$ tiene pendiente $1$ si $i \in I$ y pendiente $-1$ si $i \in {\overline{I}}$.
2. Definimos una partición del conjunto $[n]$ de modo que cada bloque consista de todos los pasos que estén a la misma altura.

Ordenando estas particiones de $[n]$ por refinamiento, obtenemos otra vez todas las desigualdades de la forma (\ref{eq:tnnineq}). La Figura 15 muestra otra vez el poset de la Figura 11, ahora con productos de menores reemplazados por caminos.

Hasta ahora hemos caracterizado todos los polinomios totalmente no negativos de la forma \begin{equation*} \Delta_{J,J}\Delta_{{\overline{J}},{\overline{J}}} - \Delta_{I,I}\Delta_{{\overline{I}},{\overline{I}}} \end{equation*} y estos resultados se pueden generalizar para obtener una caracterizacion [9]S. M. Fallat, M. I. Gekhtman, and C. R. Johnson, Multiplicative principal-minor inequalities for totally nonnegative matrices, Adv. Appl. Math. 30 (2003), no. 3, 442-470., [34]M. Skandera, Inequalities in products of minors of totally nonnegative matrices, J. Algebraic Combin. 20 (2004), no. 2, 195-211. de todos los polinomios totalmente no negativos de la forma \begin{equation*} \Delta_{J,J'}\Delta_{L,L'} - \Delta_{I,I'}\Delta_{K,K'}. \end{equation*}

Sería interesante tener una caracterización de polinomios totalmente no negativos más generales.

Pregunta 4.1.

¿Cómo podemos describir combinatoriamente el poset de productos de tres o más menores de matrices totalmente no negativas?

Pregunta 4.2.

¿Existe una caracterización sencilla de todos los polinomios totalmente no negativos?

5. Funciones de Schur

En la Sección 3 hemos considerado la matriz totalmente no negativa \begin{equation*} H = \begin{bmatrix} 1 & h_1 & h_2 & h_3 & h_4 & \ldots \\ 0 & 1 & h_1 & h_2 & h_3 & \ldots \\ 0 & 0 & 1 & h_1 & h_2 & \ldots \\ 0 & 0 & 0 & 1 & h_1 & \ldots \\ 0 & 0 & 0 & 0 & 1 & \ldots \\ \vdots & & & & \ddots & \ddots \end{bmatrix}. \end{equation*} Esta matriz, sus submatrices y sus menores son importantes en la teoría de las representaciones y en la geometría algebraica. La matriz $H$ se conoce como la matriz infinita de Jacobi-Trudi, y sus submatrices también se llaman matrices de Jacobi-Trudi. Cada menor de $H$ es una función simétrica, ya que el conjunto de funciones simétricas es un anillo. Los menores de $H$ que corresponden a conjuntos consecutivos de columnas se denominan funciones de Schur. En la segunda parte de esta serie de artículos [4]F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 2. Representaciones del grupo simétrico, universo.math, por aparecer. tendremos más que decir sobre ellas.

Note que una función de Schur no tiene un nombre único según nuestra notación $\Delta_{I,I'}$. Por ejemplo tenemos que \begin{equation*} \det\ \begin{bmatrix} h_2 & h_3 & h_4 \\ h_1 & h_2 & h_3 \\ 0 & 1 & h_1 \end{bmatrix} = \Delta_{124,345} = \Delta_{235,456} = \Delta_{346,567} = \cdots \end{equation*}

Por costumbre, denotamos a cada función de Schur usando los índices en la diagonal de la submatriz correspondiente de $H$. Por ejemplo, la función de Schur del ejemplo anterior es $s_{221}$. Para cada pareja $I,I'$ tal que $s_{221}=\Delta_{I,I'}$ tenemos que $I'-I = (2,2,1)$ si tratamos a $I$ e $I'$ como vectores. Los índices de una función de Schur siempre forman una sucesión decreciente (no necesariamente estrictamente), que también se llama una partición. Una partición se suele escribir como \begin{equation*} \lambda = (\lambda_1,\dotsc,\lambda_r). \end{equation*} Los números $\lambda_1,\dotsc,\lambda_r$ se llaman las partes de $\lambda$. Decimos que $\lambda$ es una partición de $n$ si tenemos que \begin{equation*} \lambda_1 + \cdots + \lambda_r = n. \end{equation*} En este caso también escribimos $\lambda \vdash n$, o $|\lambda| = n$.

Recordando que $H$ es la matriz de pesos de la red plana en la Figura 8, podemos interpretar cada función de Schur como una suma de pesos de caminos en ese grafo. Entonces está claro que la expansión de una función de Schur en términos de las variables $x_1,\dotsc$ no tiene resta.

Observación 5.1.

Cada función de Schur es monomio-positiva.

La Figura 16 muestra una familia de caminos que contribuye con un peso de $x_2^2x_4x_5x_6$ a la función $s_{221}$.

En analogía con las funciones elementales, homogéneas, y de sumas de potencias, las funciones de Schur forman una base del anillo de funciones simétricas, visto como un espacio vectorial. Es decir, cualquier función simétrica $f(x)$ se puede expresar de manera única como una combinación lineal de funciones de Schur. De hecho, si $f$ tiene coeficientes enteros, la combinación lineal también tendrá coeficientes enteros. Por ejemplo tenemos que \begin{equation}\label{eq:tos} \begin{split} e_4 &= s_{1111}, \\ h_4 &= s_4, \\ p_4 &= s_4 - s_{31} + s_{22} - s_{211}. \end{split} \end{equation} Notemos que aunque la función $p_4$ es monomio-positiva, no es Schur-positiva. Es decir, su expansión en términos de funciones de Schur no tiene coeficientes positivos.

Una propiedad interesante de las funciones de Schur es que el producto de dos de ellas siempre es Schur-positivo. La expansión (única) de un producto tal en términos de funciones de Schur es una combinación lineal no negativa de ellas. Dadas dos particiones $\lambda$, $\mu$, podemos escribir \begin{equation}\label{eq:lr} s_\lambda s_\mu = \sum_{\nu \vdash |\lambda| + |\mu|} c_{\lambda\mu}^\nu s_\nu. \end{equation} Los coeficientes $c_{\lambda\mu}^\nu$ se llaman los coeficientes de Littlewood-Richardson. Por ejemplo tenemos que \begin{equation}\label{eq:s31s21} s_{31}s_{21} = s_{52} + s_{511} + s_{43} + 2s_{421} + s_{4111} + s_{331} + s_{322} + s_{3211}. \end{equation} Para obtener esta expresión, podríamos en principio calcular los determinantes $s_{31}, s_{21}$, multiplicarlos, y reconocer la expresión que resulta como una combinación lineal de varios otros determinantes. Afortunadamente, existen métodos menos fastidiosos y más efectivos de calcular la expansión de un producto $s_\lambda s_\mu$ en términos de funciones de Schur. Todos estos métodos suelen llamarse el método de Littlewood-Richardson, aunque sean diferentes.

En la presentación de un método de Littlewood-Richardson, vamos a representar a $\lambda$ y $\mu$ como diagramas de cuadrados que se llaman diagramas de Young. Rellenamos los cuadrados del diagrama de $\mu$ con números, creando una tabla que se llama un tableau de Young. Un tableau de Young se llama semiestándar si los números crecen (no necesariamente estrictamente) en las filas y crecen estrictamente en las columnas. Un tableau semiestándar de Young de forma $\mu$ se llama estándar si los números usados son $1,\dotsc,|\mu|$.

Definimos el contenido de un tableau de Young $T$ como el vector \begin{equation*} c(T) = ( \# \text{ de } 1\text{s} \text{ en $T$}, \# \text{ de } 2\text{s} \text{ en $T$},\dotsc) \end{equation*}

Por ejemplo, un tableau semiestándar de Young de forma $(4,3,1,1)$ y contenido $(2,2,3,1,1)$ es el siguiente,

\begin{equation}\label{eq:ssyt} \end{equation}

Si $T$ es un tableau de Young de forma $\mu$, escribiremos $T_{j}$ para denotar el tableau que consiste solamente de las columnas $j$ hasta $\mu_1$ de $T$. Entonces si $T$ es el tableau semiestándar de Young en (\ref{eq:ssyt}), tenemos que \begin{align*} c(T_1) &= (2,2,3,1,1),\\ c(T_2) &= (1,1,3,0,0),\\ c(T_3) &= (0,1,2,0,0),\\ c(T_4) &= (0,0,1,0,0). \end{align*}

Uno de los métodos de Littlewood-Richardson para multiplicar $s_\lambda s_\mu$ es el siguiente.

1. Dibujamos $\lambda$ y $\mu$ como diagramas de Young.
2. Escribimos todos los tableaux semiestándar de Young $T$ de forma $\mu$ tales que para $j=1,\dotsc,\mu_1$, se cumpla que $\lambda + c(T_j)$ es una partición.
3. Sumamos $s_{\lambda + c(T)}$ sobre todos los tableaux $T$ en la lista.

Veamos por ejemplo la multiplicación de $s_{31} s_{21}$. Se puede verificar que los tableaux semiestándar de Young de la forma $(2,1)$ para los cuales $(3,1) + c(T)$ y $(3,1) + c(T_2)$ son particiones son los siguientes:

Entonces las particiones $(3,1) + c(T)$ son \begin{gather*} (5,2) \quad (5,1,1) \quad (4,3) \quad (4,2,1) \quad (4,2,1) \\ (4,1,1,1) \quad (3,3,1) \quad (3,2,2) \quad (3,2,1,1). \end{gather*} Así obtenemos la expresión de la Ecuación (\ref{eq:s31s21}).

Una generalización de las funciones de Schur son los menores de la matriz $H$ que corresponden a conjuntos de columnas no necesariamente consecutivas. Estas funciones se llaman funciones sesgadas de Schur y se describen usando una pareja de particiones: $s_{\lambda/\mu}$. La primera partición determina un menor $k \times k$ de columnas consecutivas, y la segunda partición mueve la primera columna $\mu_1$ posiciones a la izquierda, la segunda columna $\mu_2$ posiciones a la izquierda, etc. Por ejemplo podemos ver en la submatriz \begin{equation*} \begin{bmatrix} h_2 & h_3 & h_4 & h_5 & h_6 \\ h_1 & h_2 & h_3 & h_4 & h_5 \\ 0 & 0 & 0 & 1 & h_1 \end{bmatrix}, \end{equation*} que las funciones $s_{441}$ y $s_{441/21}$ son \begin{equation*} s_{441} = \det\ \begin{bmatrix} h_4 & h_5 & h_6 \\ h_3 & h_4 & h_5 \\ 0 & 1 & h_1 \end{bmatrix},\qquad s_{441/21} = \det\ \begin{bmatrix} h_2 & h_4 & h_6 \\ h_1 & h_3 & h_5 \\ 0 & 0 & h_1 \end{bmatrix}. \end{equation*}

La Figura 17 muestra una familia de caminos que contribuye con un peso de $x_1x_2^4x_6$ a la función sesgada de Schur $s_{441/21}$.

Entonces está claro que la expansión de una función sesgada de Schur en términos de las variables $x_1,\dotsc$ no tiene resta.

Observación 5.2.

Cada función sesgada de Schur es monomio-positiva.

Una función sesgada de Schur no es solamente monomio-positiva, sino también Schur-positiva. Además, los coeficientes positivos que aparecen en la expansión de Schur de una función sesgada de Schur son los mismos coeficientes de Littlewood-Richardson que obtenemos en la multiplicación de funciones corrientes de Schur (\ref{eq:lr}): \begin{equation}\label{eq:jdt} s_{\nu/\mu} = \sum_{\lambda \vdash |\nu| - |\mu|}c_{\lambda\mu}^\nu s_\lambda. \end{equation}

Análogo al método de Littlewood-Richardson para multiplicar funciones de Schur, es el juego de taquín que construye la expresión (\ref{eq:jdt}) dadas dos particiones $\mu$, $\nu$. Jugamos el juego de taquín en un tableau estándar de Young de la forma $\nu/\mu$. Para obtener tal tableau, dibujamos el diagrama de Young para $\nu$, borramos las cajas que corresponden a $\mu$, y rellenamos los cuadrados que quedan con los números $1,\dotsc,|\nu|-|\mu|$ de modo que crezcan en la filas y en las columnas.

En el juego de taquín, queremos trasformar un tableau $T$ de forma sesgada $\nu/\mu$ en un tableau corriente de $|\nu| - |\mu|$ cajas. Puede que la mejor manera de explicar este juego sea con un ejemplo. La Figura 18 muestra el juego de taquín en el tableau

de la forma sesgada $(4,3,2)/(2,1)$.

En el juego de taquín, movemos las cajas de $T$ hacia arriba y a la izquierda según las reglas siguientes.

Mientras la forma del tableau esté sesgada,

1. Elegimos cualquier cuadrado en la frontera sudeste de la forma vacía. (En la Figura 18 lo hemos indicado con un punto.)
2. Movemos a esta posición la caja que se encuentra debajo o a su derecha; de estas dos, escogemos la que tenga el menor número.
3. Mientras el tableau no tenga forma ni corriente ni sesgada, movemos a la posición más recientemente desocupada la caja que se encuentra debajo o a su derecha; de estas dos, escogemos la que tenga el menor número.

Llamamos el tableau que resulta $jdt(T)$. Sorprendentemente, este tableau no depende de los cuadrados elegidos sucesivamente en la regla (1). En la expansión de Schur de $s_{\nu/\mu}$ (\ref{eq:jdt}), el coeficiente de Littlewood-Richardson $c_{\lambda\mu}^\nu$ es igual al número de tableaux estándar de Young $T$ cuya forma es $\nu/\mu$ tales que $jdt(T)$ tiene la forma $\lambda$ y contiene los números $1,\dotsc,|\lambda|$ en ese orden, al leerlos en el orden de lectura (de arriba a abajo y de izquierda a derecha).

Por ejemplo en el cálculo de la expansión de Schur de $s_{321/21}$, jugamos el juego de taquín en cada uno de los seis tableaux estándar de Young de la forma $(3,2,1)/(2,1)$, \begin{gather*} jdt\ \begin{pmatrix} \;\;\;\;\;1\; \\ \;\;2\;\;\; \\ 3\;\;\;\;\; \end{pmatrix} = \begin{matrix} 1 \\ 2 \\ 3 \\ \end{matrix}, \quad jdt\ \begin{pmatrix} \;\;\;\;\; 1 \\ \;\;3\;\; \\ 2\;\;\;\; \end{pmatrix} = \begin{matrix} 13 \\ 2\;\;\; \end{matrix}, \quad jdt\ \begin{pmatrix} \;\;\;\;2\; \\ \;\;1\;\;\; \\ 3\;\;\;\;\; \end{pmatrix} = \begin{matrix} 12 \\ 3\;\;\; \end{matrix}, \\ jdt\ \begin{pmatrix} \;\;\;\;2 \\ \;3\;\; \\ 1\;\;\;\;\; \end{pmatrix} = \begin{matrix} 12 \\ 3\;\;\; \end{matrix}, \quad jdt\ \begin{pmatrix} \;\;\;3\; \\ \;1\;\; \\ 2\;\;\;\; \end{pmatrix} = \begin{matrix} 13 \\ 2\;\;\; \end{matrix}, \quad jdt\ \begin{pmatrix} \;\;\;3\; \\ \;2\;\;\; \\ 1\;\;\;\;\; \end{pmatrix} = \begin{matrix} 123 \end{matrix}. \end{gather*} Ignorando el segundo y el quinto tableaux, que no contienen los números $1,2,3$ en el orden de lectura, tenemos que \begin{equation*} s_{321/21} = s_{111} + 2s_{21} + s_3. \end{equation*}

Como ya hemos notado (\ref{eq:tos}), no todas las funciones monomio-positivas son Schur-positivas. Las funciones Schur-positivas son interesantes porque corresponden a representaciones de $S_n$. (Vea por ejemplo la segunda parte de esta serie [4]F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 2. Representaciones del grupo simétrico, universo.math, por aparecer..) Hay una gran cantidad de resultados y conjeturas que dicen que ciertas funciones simétricas son Schur-positivas. (Vea, por ejemplo [38]R. Stanley, Graph colorings And Related Symmetric functions: Ideas and Applications, Discrete Math. 193 (1998), 267-286., [40]R. Stanley, Positivity problems and conjectures, Mathematics: Frontiers and Perspectives (V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds.), American Mathematical Society, Providence, RI, 2000, pp. 295-319..)

Los resultados de la Sección 4 se pueden aplicar a las matrices de Jacobi-Trudi para definir funciones que son monomio-positivas. Por ejemplo, el polinomio totalmente no negativo $\Delta_{13,13}\Delta_{2,2} - \Delta_{12,12}\Delta_{3,3}$ nos da una clase infinita de diferencias de productos de funciones de Schur. Curiosamente, estos polinomios parecen ser siempre Schur-positivos. Por ejemplo, tenemos que \begin{equation}\label{eq:schurpos} \begin{split} s_{41/1}s_2 - s_{32}s_1 &= s_6 + 2 s_{51} + s_{42} + s_{411}, \\ s_{52/1}s_3 - s_{43}s_2 &= s_{81} + 2s_{72} + s_{711} + s_{63} + 2s_{621} + s_{54} + s_{531} + s_{522}, \\ s_{63/1}s_4 - s_{54}s_3 &= s_{10,2} + 2s_{93} + s_{921} + s_{84} + s_{831} + s_{822} + s_{75} + s_{741} + 2s_{732} \\ & \quad+ s_{66} + s_{651} + s_{642} + s_{633},\\ &\vdots \end{split} \end{equation}

Varios casos especiales se han demostrado ya. Por ejemplo, podemos mostrar que todos las funciones simétricas de (\ref{eq:schurpos}) son Schur-positivas.

Proposición 5.3.

Sea $i$ un entero no negativo. Entonces la función simétrica \begin{equation}\label{eq:sdiff} s_{i+3,i/1}s_{i+1} - s_{i+2,i+1}s_i \end{equation} es Schur-positiva.

Demostración. Usando el juego de taquín y dos interpretaciones de los coeficientes de Littlewood-Richardson (\ref{eq:lr}), (\ref{eq:jdt}), se puede mostrar que tenemos que \begin{equation*} s_{i+3,i/1} = s_{i+2,i} + s_{i+3,i-1}. \end{equation*} Entonces nuestra función simétrica (\ref{eq:sdiff}) se puede escribir como \begin{equation}\label{eq:sdiff2} s_{i+2,i}s_{i+1} + s_{i+3,i-1}s_{i+1} - s_{i+2,i+1}s_i. \end{equation} Ahora tenemos que mostrar que cualquier función de Schur que aparece en la expansión de Schur de $s_{i+2,i+1}s_i$ también aparece en la expansión de Schur de $s_{i+2,i}s_{i+1}$ o de $s_{i+3,i-1}s_{i+1}$. Supongamos que aplicamos nuestro primer método de Littlewood-Richardson al producto $s_{i+2,i+1}s_i$ y consideramos una manera de rellenar el tableau de la forma $i$ y añadir su contenido a la partición $(i+2,i+1)$. Sea $\nu$ la partición que resulta. Aplicando ahora el método de Littlewood-Richardson al producto $s_{i+2,i}s_{i+1}$, rellenamos un tableau de la forma $i+1$ con los mismos números que hemos usado para rellenar el tableau de la forma $i$, más un $2$ adicional. Añadiendo el contenido de este tableau a la partición $(i+2,i)$, obtenemos otra vez la partición $\nu$.

Ya que $s_\nu$ aparece en la expansión de Schur de $s_{i+2,i}s_{i+1}$ con multiplicidad mayor que o igual a su multiplicidad en la expansión de Schur de $s_{i+2,i+1}s_i$, sabemos que la función \begin{equation*} s_{i+2,i}s_{i+1} - s_{i+2,i+1}s_i. \end{equation*} es Schur-positiva. Entonces la función (\ref{eq:sdiff2}) también es Schur-positiva.

$\square$

La generalización de la Proposición 5.3 también es cierta [28]B. Rhoades and M. Skandera, Kazhdan-Lusztig immanants and products of matrix minors, J. Algebra 304 (2006), no. 2, 793-811..

Teorema 5.4.

Sea $f = \Delta_{J,J'}\Delta_{L,L'} - \Delta_{I,I'}\Delta_{K,K'}$ un polinomio totalmente no negativo y sea $A$ una matriz de Jacobi-Trudi. Entonces $f(A)$ es una función Schur-positiva.

Es natural preguntarse si la no negatividad total de un polinomio $f$ implica que $f(A)$ es una función Schur-positiva por cada matriz $A$ de Jacobi-Trudi. El cuarto autor y Andrei Zelevinsky han mostrado que esto no es cierto [35]M. Skandera, On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations, J. Pure Appl. Algebra 212 (2008), 1086-1104.. Así tenemos la pregunta siguiente.

Pregunta 5.1.

¿Existe una caracterización sencilla de todos los polinomios $f$ con la propiedad de que para cada matriz $A$ de Jacobi-Trudi, $f(A)$ es una función Schur-positiva?

El Teorema 5.4 se mostró en [28]B. Rhoades and M. Skandera, Kazhdan-Lusztig immanants and products of matrix minors, J. Algebra 304 (2006), no. 2, 793-811., utilizando resultados de Kazhdan-Lusztig [21]D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165-184. y de Haiman [18]M. Haiman, Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc. 6 (1993), no. 3, 569-595. sobre las representaciones del grupo simétrico y sus caracteres. Ya veremos más de este tema en la segunda parte de nuestra serie de artículos [4]F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 2. Representaciones del grupo simétrico, universo.math, por aparecer..

6. Agradecimientos

Los autores quiren agradecer a Carlos Montenegro por su ayuda en la organizacion del Primer Encuentro Colombiano de Combinatoria, y a Jason Asher, Brian Drake, Sergey Fomin, Richard Stanley, y John Stembridge por varias discusiones matemáticas que nos fueron de gran utilidad.

Referencias

[1] M. Aissen, I. J. Schoenberg, and A. Whitney, On generating functions of totally positive sequences, J. Anal. Math. 2 (1952), 93-103.

[2] T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219.

[3] F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 1. Matrices totalmente no negativas y funciones simétricas, universo.math, julio 2013.

[4] F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 2. Representaciones del grupo simetrico, universo.math, por aparecer.

[5] F. Ardila, E. León, M. Rosas, and M. Skandera, Tres lecciones en combinatoria algebraica. 3. Aspectos combinatorios de los arreglos de hiperplanos, universo.math, por aparecer.

[6] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A 71 (1995), no. 2, 175-218.

[7] C. W. Cryer, Some properties of totally positive matrices, Linear Algebra Appl. 15 (1976), 1-25.

[8] E. Curtis, D. V. Ingerman, and J. Morrow, Circular planar graphs and resistor networks, Linear Algebra Appl. 283 (1998), 115-150.

[9] S. M. Fallat, M. I. Gekhtman, and C. R. Johnson, Multiplicative principal-minor inequalities for totally nonnegative matrices, Adv. Appl. Math. 30 (2003), no. 3, 442-470.

[10] S. Fomin, Loop-erased walks and total positivity, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3563-3583.

[11] S. Fomin and M. Shapiro, Stratified spaces formed by totally positive varieties, Michigan Math. J. 48 (2000), 253-270.

[12] S. Fomin and A. Zelevinsky, Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12 (1999), 335-380.

[13] S. Fomin and A. Zelevinsky, Total positivity: Tests and parametrizations, Math. Intelligencer 22 (2000), no. 1, 23-33.

[14] F. R. Gantmacher, The Theory of Matrices, vol. 1, Chelsea, New York, 1959.

[15] F. R. Gantmacher, The Theory of Matrices, vol. 2, Chelsea, New York, 1959.

[16] F. R. Gantmacher and M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, AMS Chelsea Publishing, Providence, 2002, Edited by A.Eremenko. Translation based on the 1941 Russian original.

[17] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58 (1985), no. 3, 300-321.

[18] M. Haiman, Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc. 6 (1993), no. 3, 569-595.

[19] S. Karlin, Mathematical methods and theory in games, programming, and economics, Addison-Wesley, Reading, MA, 1959.

[20] S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141-1164.

[21] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165-184.

[22] B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90.

[23] C. Loewner, On totally positive matrices, Math. Z. 63 (1955), 338-340.

[24] D. Luenberger, Introduction to dynamic systems, Wiley, 1979.

[25] G. Lusztig, Total positivity in reductive groups, Lie Theory and Geometry: in Honor of Bertram Kostant, Progress in Mathematics, vol. 123, Birkhäuser, Boston, 1994, pp. 531-568.

[26] I.G. Macdonald, Symmetric Fuctions and Hall Polynomials, Oxford University Press, Oxford, 1979.

[27] A. Postnikov, Quantum Bruhat graph and Schubert polynomials, Proc. Amer. Math. Soc. 133 (2005), no. 3, 699-709 (electronic).

[28] B. Rhoades and M. Skandera, Kazhdan-Lusztig immanants and products of matrix minors, J. Algebra 304 (2006), no. 2, 793-811.

[29] B. Rhoades and M. Skandera, Temperley-Lieb immanants, Ann. Comb. 9 (2005), no. 4, 451-494.

[30] H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1984), no. 1, 89-99.

[31] B. Sagan, The symmetric group, Springer, New York, 2001.

[32] M. Skandera, A characterization of (3 + 1)-free posets, J. Combin. Theory Ser. A 93 (2001), no. 2, 231-241.

[33] M. Skandera, Interpretaciones del h-vector, Bol. Asoc. Mat. Venez. 2 (2001), 141-174.

[34] M. Skandera, Inequalities in products of minors of totally nonnegative matrices, J. Algebraic Combin. 20 (2004), no. 2, 195-211.

[35] M. Skandera, On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations, J. Pure Appl. Algebra 212 (2008), 1086-1104.

[36] M. Skandera and B. Reed, Total nonnegativity and (3 + 1)-free posets, J. Combin. Theory Ser. A 103 (2003), 237-256.

[37] R. Stanley, Enumerative Combinatorics, vol. 1, Cambridge University Press, Cambridge, 1997.

[38] R. Stanley, Graph colorings And Related Symmetric functions: Ideas and Applications, Discrete Math. 193 (1998), 267-286.

[39] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.

[40] R. Stanley, Positivity problems and conjectures, Mathematics: Frontiers and Perspectives (V. Arnold, M. Atiyah, P. Lax, and B. Mazur, eds.), American Mathematical Society, Providence, RI, 2000, pp. 295-319.

[41] A. Whitney, A reduction theorem for totally positive matrices, J. Anal. Math. 2 (1952), 88-92.