Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|cite|improve this answer
Thanks! This paper seems to line up very well with some ideas I've been having, although I wish it were LaTeX'd. –  Qiaochu Yuan Oct 16 '09 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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