# What are the Schur functions of the eigenvalues of a non-negative integer matrix counting?

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.

-

## 1 Answer

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.

-
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