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!



Is there a similar theory as for symmetric polynomials, that deals with polynomials on the entries of matrices that are symmetric in both dimensions?
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"](http://www.springer.com/us/book/9783662484203) by Derksen and Kemper.


