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.



Invariants of Matrix Reordering
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.).


