3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dietrich Burde
    Commented Jul 13, 2013 at 18:53
  • $\begingroup$ 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. $\endgroup$
    – Manfred Weis
    Commented Jul 13, 2013 at 19:43
  • $\begingroup$ 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. $\endgroup$
    – Erik Aas
    Commented Jul 14, 2013 at 8:12
  • $\begingroup$ @erik I can't follow your comment; could you please provide me more details or pointers to articles where that is described? $\endgroup$
    – Manfred Weis
    Commented Jul 14, 2013 at 9:56
  • $\begingroup$ @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. $\endgroup$
    – Manfred Weis
    Commented Aug 3, 2013 at 13:14

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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
  • ...
Improve this answer
$\endgroup$
8
  • $\begingroup$ @V Delecroix: am I right that "not a complete invariant" should be "not the only invariant"? $\endgroup$
    – Manfred Weis
    Commented Jul 13, 2013 at 19:50
  • $\begingroup$ No that it is not what I meant. By "complete invariant", I meant an invariant which would classify all equivalence classes. $\endgroup$
    – V. Delecroix
    Commented Jul 13, 2013 at 20:49
  • 2
    $\begingroup$ A complete invariant is likely not to be easily computable, since it would, for example, determine graph isomorphism. $\endgroup$
    – Igor Rivin
    Commented Jul 13, 2013 at 21:21
  • $\begingroup$ @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. $\endgroup$
    – V. Delecroix
    Commented Jul 13, 2013 at 21:48
  • $\begingroup$ @V. Delecroix, I think Igor Rivin is correct (consider the vertex-edge incidence matrix of a graph). $\endgroup$
    – Dustin G. Mixon
    Commented Jul 13, 2013 at 23:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .