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

Question

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!

Answer 1

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.

Answer 2

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:

• "Traffic distributions and independence: permutation invariant random matrices and the three notions of independence" by Camille Malle. I think he calls the graphical representations of invariants "traffics".
• "La Catégorie des Représentations du Groupe Symétrique $S_t$, lorsque $t$ n’est pas un Entier Naturel" by Pierre Deligne.