most recent 30 from http://mathoverflow.net 2013-06-19T20:38:48Z http://mathoverflow.net/feeds/question/59991 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59991/invariants-on-matrices asterios gantzounis 2011-03-29T17:16:56Z 2011-03-29T17:30:37Z

<p>Take all the $n\times n$ matrices of 0's and 1's and define an equivallence relation as follows: Two matrices are equal if there is a way to pass from the one to another by alternating the columns and the rows.(acting by $S_n$ on the columns and on the rows)</p> <blockquote> <p>Is there a good way to determine whether two such matrices are equal?</p> <p>Are there any good invariants (polynomials ,etc.)?</p> </blockquote> <p>The obvious invariant is that the sum of the 1's on the rows and on the columns does not change.</p>

http://mathoverflow.net/questions/59991/invariants-on-matrices/59993#59993 Alex Becker 2011-03-29T17:22:53Z 2011-03-29T17:22:53Z

<p>The determinant would be invariant under the permutations you outlined.</p>

http://mathoverflow.net/questions/59991/invariants-on-matrices/59995#59995 David Speyer 2011-03-29T17:30:37Z 2011-03-29T17:30:37Z

<p>This is the <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow">graph isomorphism problem</a>. </p> <p>More precisely, if you have to permute the rows and the columns by the same permutation, then this is graph isomorphism (use $1$ to code "edge present" and $0$ to code "edge absent".) If you are allowed to use different permutations on rows and columns, then this is bipartie graph isomorphism, which is equivalent to graph isomorphism.</p> <p>In practice, algorithms for Graph Isomorphism are pretty fast; however, it is not known whether there is a polynomial time method to test whether two graphs are isomorphic or, equivalently, whether two matrices are equal under your operations.</p>