Timeline for Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 25, 2018 at 2:01 | comment | added | Brendan McKay | @FlorianLehner There is a minor correction needed. If the graph is disconnected, the colours in one component can be flipped without flipping colours in the other components. This is an operation not allowed for the matrices. To make the correspondence complete there are ways to first convert the graph to a connected bipartite graph in an isomorphism-invariant way. | |
| Jan 25, 2018 at 1:31 | answer | added | Jan Kyncl | timeline score: 7 | |
| Jan 24, 2018 at 20:48 | comment | added | Wolfgang | ...and for the record: indeed $M_1$ and $M_2$ define the same bipartite graph! | |
| Jan 24, 2018 at 15:19 | comment | added | Wolfgang | @FlorianLehner oh thank you, I see! | |
| Jan 24, 2018 at 14:44 | comment | added | Florian Lehner | I agree with Chris Godsil's comment. Let me explain: You can define a bijection between matrices and labelled bipartite graphs with bipartition $A \cup B$, where $|A|=|B|=n$, $A$ has labels $1, \dots, n$, and $B$ has labels $1', \dots, n'$. Simply draw an edge from $i$ to $j'$ if $M_{ij} = 1$. Now swapping rows means swapping labels in $A$, swapping columns means swapping labels in $B$, and reflection means exchanging the roles of $A$ and $B$. In particular, two matrices are equivalent if and only if their corresponding bipartite graphs are isomorphic (after removing labels). | |
| Jan 24, 2018 at 7:53 | comment | added | Wolfgang | @GerhardPaseman it is not necessarily about a subclass of graphs. I introduced the notion of graphs only because the symmetric matrices of this kind are adjacency matrices of simple graphs - but this being said, those may have loops. :( That is why I've said that probably graph theory won't be of much help. | |
| Jan 24, 2018 at 7:50 | comment | added | Wolfgang | @ChrisGodsil Could you elaborate please? There is a trivial 1-1 correspondence with directed graphs (with loops allowed) but I don't see how to go from there to bipartite graphs. | |
| Jan 24, 2018 at 1:46 | comment | added | Gerhard Paseman | @Igor, there is some connection to GI. However, I think Wolfgang actually wants a version restricted to a subclass of graphs, namely those that correspond to something like a maximal determinant. Even among maximal determinant configurations there will be some challenges, but he might be able to compute info for small orders. Gerhard "Might Compute Small Order Info" Paseman, 2018.01.23. | |
| Jan 24, 2018 at 1:32 | comment | added | Chris Godsil | It’s basically isomorphism of bipartite graphs. | |
| Jan 24, 2018 at 0:44 | comment | added | Igor Rivin | Isn't this a version of the graph isomorphism problem, for which there is no provably efficient algorithm? | |
| Jan 23, 2018 at 23:47 | comment | added | Gerhard Paseman | I don't think so. Miodrag Zivkovic in his 2005 classification paper (see ArXiv) spent a lot of computer cycles counting equivalence classes of various types. I think his work can be extended to one or two higher orders now, but I do not know who has done it. I did some enumeration by computer back in the 90's, and doing orders up to 6 by hand (for full rank) was quite manageable. You might for example prove that 1 does not occur in a signature of interest. Gerhard "Fun With Combinatorial Matrix Theory" Paseman, 2018.01.23. | |
| Jan 23, 2018 at 21:11 | history | asked | Wolfgang | CC BY-SA 3.0 |