## Invariants on matrices

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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)

Is there a good way to determine whether two such matrices are equal?

Are there any good invariants (polynomials ,etc.)?

The obvious invariant is that the sum of the 1's on the rows and on the columns does not change.

-

Helpful?: mathkb.com/Uwe/Forum.aspx/research/2601/…  – Alex R. Mar 29 2011 at 17:30

## 2 Answers

This is the graph isomorphism problem.

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.

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.

-

I was just about to write that! – Per Alexandersson Mar 29 2011 at 17:31
thanx! that's the right answer – asterios gantzounis Mar 29 2011 at 17:35

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

The determinant would be invariant under the permutations you outlined.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 4, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9015047550201416, "perplexity_flag": "middle"}