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.

permanentof a matrix remains invariant under arbitrary permutations of its rows and columns. $\endgroup$ – Dietrich Burde Jul 13 '13 at 18:531more comments