Schur operators and Knuth correspondences (Q1903009): Difference between revisions

The author presents a general combinatorial approach to Schur functions and their modifications, to generalized Cauchy identities and to bijective Knuth-type correspondences between matrices and pairs of tableaux. Let \(V\) be a graded vector space over a field \(K\), with a basis \(P_i\) for each homogeneous component \(V_i\). Typically, \(P= \bigcup_i P_i\) is a ranked poset of shapes (Ferrers diagrams). For each rank (degree) \(i\), one is given two linear operators \(A_i\) and \(B_i\) on \(KP\), the first increasing, the second decreasing the rank of an element by \(i\): in other words, these operators map a ``shape'' \(\lambda\) into a sum of shapes obtained respectively by adding/deleting \(i\) boxes to/from \(\lambda\), according to certain rules. Let \[ A(x)= \sum^\infty_{i= 1} A_i x^i\quad\text{and} \quad B(y)= \sum^\infty_{j= 1} B_j x^j \] be the resulting operator power series in the formal variables \(x\) and \(y\). Alternatively, if \(A_i= \langle A_i \lambda, \mu\rangle_{\lambda, \mu\in P}\) and \(B_i= \langle B_i\lambda, \mu\rangle_{\lambda, \mu\in P}\) are represented in the base \(P\) by nonnegative integer matrices, then one associates to \(A(x)\) and \(B(y)\) two unoriented graphs \(G_1\) and \(G_2\) on the same set of vertices \(P\), where \(\lambda\) and \(\mu\) are connected by an edge of multiplicity \(\langle A_i \lambda, \mu\rangle\) in \(G_1\) (resp. \(\langle B_i \lambda, \mu\rangle\) in \(G_2\)). Notice that vertices in arbitrary levels, not necessarily consecutive ones, can be connected in \(G_1\) and \(G_2\). Suppose that the following commutation relation \((*)\) \(B(y) A(x)= A(x) B(y)f(xy)\) holds, where \(f(xy)\) is a formal power series in \(xy\). Then various combinatorial identities and properties concerning path/tableaux enumeration in \(G_1\) and \(G_2\) can be derived via simple linear algebra arguments based on this commutation relation. The author follows the ideas which appeared in previous papers of the author himself (see [J. Algebr. Comb. 3, No. 4, 357-404 (1994; Zbl 0810.05005)], [J. Algebr. Comb. 4, No. 1, 5-45 (1995; Zbl 0817.05077)], [``Séries formelles et combinatoire algébrique'' (P. Leroux and C. Reutenauer, eds.), LACIM-UQAM, Montréal, 221-236 (1992)]) and in the following papers of R. P. Stanley: [J. Am. Math. Soc. 1, No. 4, 919-961 (1988; Zbl 0658.05006)], [Invariant theory and tableaux, Proc. Workshop, Minneapolis, MN (USA) 1988, IMA Vol. Math. Appl. 19, 145-165 (1990; Zbl 0707.06001)]. In particular, there holds a Cauchy-type identity. The author constructs an analogue of the Knuth correspondence, giving a general algorithmic approach to these constructions. This can be done whenever (1) one has the commutation relation \((*)\); (2) \(A_i\) and \(B_j\) are nonnegative integer matrices; and (3) the formal power series \(f(t)= f_0+ f_1t+ f_2 t^2+\cdots\) has nonnegative integer coefficients \(\{f_i\}_{i\geq 0}\). Let \(G\) be the oriented graph on the set of vertices \(P\) obtained by combining the edges of \(G_1\) and \(G_2\). The commutation relation \((*)\) can be transformed into \(\langle B_l A_k \alpha, \beta\rangle= \sum_i f_i\langle A_{k- i} B_{l- i} \alpha, \beta\rangle\). The left-hand side of the above equality counts the two-edge up-down paths in \(G\) from \(\alpha\) to \(\beta\) which first jump \(k\) levels up, and then \(l\) levels down, while the right-hand side counts, with appropriate weights \(f_i\), certain down-up two-edge paths from \(\alpha\) to \(\beta\). This gives a family of bijections, one for each pair \((\alpha, \beta)\), between (i) up-down paths from \(\alpha\) to \(\beta\) and (ii) down-up paths from \(\alpha\) to \(\beta\), integer \(i\geq 0\), and label \(L\in \{1, \dots, f_i\}\). One can now apply the bijective correspondence (i)\(\leftrightarrow\)(ii) repeatedly to obtain one-to-one correspondences between (generalized) loops and matrices with integer entries.