Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
The question in the first line is perhaps too general. The permanent of a matrix remains invariant under arbitrary permutations of its rows and columns. –  Dietrich Burde Jul 13 '13 at 18:53
    
I agree, that I should have ruled out "trivial" invariants like functions acting on elements within a row or within a column or on the set of all elements; the permanent of a matrix is however interesting, despite its restriction to square matrices. –  Manfred Weis Jul 13 '13 at 19:43
    
Any matrix is the 'adjacency matrix' of a weighted bipartite graph, and two matrices are equivalent iff their graphs are isomorphic. So you are asking for invariants of weighted bipartite graphs. –  Erik Aas Jul 14 '13 at 8:12
    
@erik I can't follow your comment; could you please provide me more details or pointers to articles where that is described? –  Manfred Weis Jul 14 '13 at 9:56
    
@erik: I guess your claim is wrong: not every is the adjacency matrix of a bipartite graph; what you have in mind is that the matrix encodes the edge-weights of a bipartite graph, who's nodes correspond either to the columns of the matrix or to the rows of the matrix, but then the matrix isn't what is normally understood as an adjacency matrix; then it is an assignment matrix, to which e.g. the Kuhn-Munkres algorithm can be applied. –  Manfred Weis Aug 3 '13 at 13:14

2 Answers 2

up vote 5 down vote accepted

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.).

share|improve this answer

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
  • ...
share|improve this answer
    
@V Delecroix: am I right that "not a complete invariant" should be "not the only invariant"? –  Manfred Weis Jul 13 '13 at 19:50
    
No that it is not what I meant. By "complete invariant", I meant an invariant which would classify all equivalence classes. –  V. Delecroix Jul 13 '13 at 20:49
1  
A complete invariant is likely not to be easily computable, since it would, for example, determine graph isomorphism. –  Igor Rivin Jul 13 '13 at 21:21
    
@IgorRivin It will not because here we do not act by conjugation by S_n but by action of S_n x S_n on both left and right. This is much different from graph relabeling. I am pretty sure that we can design some complete invariants. –  V. Delecroix Jul 13 '13 at 21:48
    
@V. Delecroix, I think Igor Rivin is correct (consider the vertex-edge incidence matrix of a graph). –  Dustin G. Mixon Jul 13 '13 at 23:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.