Invariants of Matrix Reordering are there any invariants of matrices, that are not affected by row- and/or column permutations?
To me it seems that the sequence of singular values could be such an invariant; am I right, resp. are there other invariants?
My guess for the sequence of singular values comes from the observation that a row permutation $P^T$ and a column permutation $Q$ only act on $U$ or $V$ when a matrix $M$ is expressed as its singular value decomposition $U^T\Sigma V$, because $P^T M Q = P^T U^T \Sigma V Q  = (UP)^T\Sigma (VQ)$, so $\Sigma$ remains unpermuted when exchanging rows or columns.
Motivation for the question is the fact that many combinatorial problems can be interpreted as matrix reordering problems and, having invariants might yield some insight.
E.g. the TSP can be interpreted as the task to permute corresponding rows and columns of the cost matrix simultaneously in way that makes the sum of elements adjacent to the principal diagonal minimal (and of course plus the elements in the upper right and lower left corner); the attractive property of that approach being that one doesn't have to be concerned with topological constraints.
 A: As said in the comment, the permanent of a square matrix is such an invariant.
It is interesting for many topics in combinatorics.
For $A=(a_{ij})$ it is defined as $\Sigma_{\sigma \in S_n}\prod_{i=1}^na_{i,\sigma(i)}$. 
For $n=3$, as an example,
$Perm(A)=a_{11}a_{22}a_{33} + a_{11}a_{23}a_{32} + a_{12}a_{21}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} + a_{13}a_{22}a_{31}.$ 
Other invariants of matrices with respect to row and column permutations are given in the book
"Combinatorial Matrix Classes" by R. A. Brualdi (such as width and depth of matrices etc.).
A: Singular values are definitely an invariant (because permutation matrices are orthogonal) but not a complete invariant! If you modify only the rows and columns order you do not modify the list of entries of your matrix. And there are many (=uncountably many) matrices with the same singular values.
Some other invariants:


*

*the entries of your matrix (hence the maximum, minimum, etc)

*the (unordered) list of sum of columns

*the (unordered) list of sum of rows

*the (unordered) list of maximum of each column

*...

