Is there a similar theory as for symmetric polynomials, that deals with polynomials on the entries of matrices that are symmetric in both dimensions?

I am looking at a polynomial of the entries of a matrix, and this polynomial is invariant under permutation of the rows or columns of the matrix. Is there a similar characterization as in the case of symmetric polynomials of this family? I.e. some simple bases.

Any references welcome!

You have touched a vast subject called invariant theory. The direct product $G=S_n\times S_n$ of two copies of the symmetric group $S_n$ on $n$ letters naturally acts on polynomials in variables $X_{ij}$, for $1\leq i,j\leq n$: if $(\gamma,\mu)\in G$ then $(\gamma,\mu)$ sends $X_{ij}$ to $X_{\gamma(i),\mu(j)}$. A nice characterisation of the ring of invariants of this action seems unlikely, as this would mean that one can in particular use it to compute full lists of invariants of bipartite graphs on $2n$ vertices, with parts of size $n$, something that is out of reach, on all accounts.

A similar setup, although for non-bipartite graphs, is discussed in the book "Computational Invariant Theory" by Derksen and Kemper.

• In particular, the Chevalley-Shephard-Todd theorem (en.wikipedia.org/wiki/…) rules out the possibility that the ring of invariants is a polynomial ring. – Qiaochu Yuan Nov 11 '15 at 21:26
• @Dima: what you said about bipartite graphs sounded very interesting, but did not have enough details for me to understand it well. What specific problem from the theory of bipartite graphs could one solve if one had a good enough description of the invariant ring that the OP is asking about? References would be appreciated. – Abdelmalek Abdesselam Nov 12 '15 at 23:32
• @AbdelmalekAbdesselam : having a "good" set of generators for such a ring (or only a system of parameters for such a ring) would allow one to solve the isomorphism problem for bipartite graphs (which is as hard as for general graphs -- cf. e.g. en.wikipedia.org/wiki/…). How a similar idea works for general graphs, is explained in the book I cited in the answer. – Dima Pasechnik Nov 12 '15 at 23:59
• @Dima: thanks but when I checked my copy of Dersken-Kemper what they say about the connection graph isomorphism pbm<->invariant rings does not sound good. Pouzet's conjecture to this effect was shown to be false by Thiery. So is there still a precise viable connection in the literature? – Abdelmalek Abdesselam Nov 19 '15 at 15:21
• @AbdelmalekAbdesselam : the general setup is that if you have a system of parameters $P$ (or some other well-defined set of generators of a (sub)ring - I'd have to check Derksen-Kemper to see exactly which one) of the corresponding invariant ring, and evaluate your graph (as a vector of 0s and 1s) on this system, you will get a unique fingerprint, distinguishing nonisomorphic graphs. Pouzet's conjecture was that certain set $P'$ is generating the same ring as $P$, but this turned out to be false. – Dima Pasechnik Nov 19 '15 at 23:26

I think one can at least give a First Fundamental Theorem in the spirit of really classical invariant theory. For the group $$S_n$$, I think you can build all invariants of vectors $$(X_i)_{1\le i\le n}$$ under the action by permutation matrices using tensor contractions with the following fundamental tensors $$T^{(1)},\ldots,T^{(n)}$$ given by: $$(T^{(k)})_{i_1,\ldots,i_k}=\prod_{1\le \alpha<\beta\le k} \delta_{i_{\alpha},i_{\beta}}\ .$$ For instance, using Einstein's convention for summation over repeated indices, $$p_k=(T^{(k)})_{i_1,\ldots,i_k} X_{i_1}\ldots X_{i_k}$$ give the power sums. I think one can prove this following the very general recipe in this MO answer.

Now to go to a product $$S_n\times S_n$$ you can follow the procedure in this other MO answer. Basically you need a duplicate collection of fundamental tensors, say $$S^{(1)},\ldots,S^{(n)}$$ given by the same formulas. Now if you have a product of $$X_{ij}$$ the rule is the $$T$$'s only contract to $$i$$-type row indices, whereas the $$S$$'s only contract to the $$j$$-type column indices. Of course you need to contract everything in sight. This will give an infinite linearly generating set for the ring of invariants you are looking for indexed by bipartite graphs. The degree of an invariant is the number of edges. Now finding a finite subset of such graphs which will give a system of ring generators, that's the big problem I think Dima is referring to.

Some references which discuss the invariant theory for $$S_n$$ with the $$T^{(k)}$$ tensors are:

• it's known how to search for generators for invariant rings of permutation groups, of which we have an example here (e.g. take orbit sums of monomials, up to certain degree). The problem is that such a set will be huge, and will have huge degrees. – Dima Pasechnik Nov 13 '15 at 0:04