Let A be a non-negative integer square matrix with eigenvalues x1, x2, ... xn. Any symmetric function of these eigenvalues with integer matrices is an integer. I'm aware of the following results regarding the combinatorial interpretation of these integers:

  • If A is the adjacency matrix of a finite directed graph G, the power symmetric functions of the eigenvalues count closed walks on A with a distinguished starting point.

  • Similarly, the complete homogeneous symmetric functions of the eigenvalues count non-negative integer linear combinations of aperiodic closed walks on A.

  • (Gessel-Viennot-Lindstrom) If Aij is the number of paths from source i to sink j on, say, a 2-D lattice where the only permissible moves are to the right and up, then the elementary symmetric functions of the eigenvalues count the number non-intersecting k-tuples of paths from the sources to the sinks. In particular det A is the number of non-intersecting n-tuples of paths.

Do these results generalize to give a nice combinatorial interpretation of the value of the Schur function associated to an arbitrary partition evaluated at x1, x2, ... xn in terms of some combinatorial object attached to A? What conditions need to be placed on A so that the Schur functions are always non-negative?

Feel free to either talk about the GL(n) perspective or to frame your discussion entirely in terms of tableaux.


This is moving far enough afield from my own understanding that I'm not sure how useful it is, but have you looked at the Ph.D. thesis of Andrius Kulikauskas? He seems to be giving some sort of combinatorial interpretation in terms of Lyndon words for the Schur functions.



Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.