On 2014-02-28, Andrew <andrew.mat...@sydney.edu.au> wrote: > The easiest way is probably to store your matrices in a some sort of > "normal form": permute the rows and columns so that one of the smallest > entries in your matrix is in the (1,1) position and then permute rows 2,3, > ... so that the entries in column one are weakly increasing from top to > bottom. Now permute columns 2,3,... so that the smallest possible entry is > in position (2,2) subject to the constraint that the entries in column one > do not change. Continue in a suitable fashion. Then two matrices will be > permutation equivalent if and only if they have the same normal form. > > For your example matrices below the normal form would be > [[0,1,1],[1,0,1],[1,1,1]].
the problem in question is still the isomorphism problem for bipartite graphs (which is a complete problem in the complexity class dealing with graph isomorphismsi, AFAIK). You most probably can't solve it by a polynomial-time procedure. > > For 0-1 matrices, however, I wouldn't be surprised if the sets of row and > column sums determine the orbit uniquely. > > Andrew > > On Friday, 28 February 2014 06:25:24 UTC+11, Keivan Monfared wrote: >> >> In a problem that I am solving I generate matrices and put them in a list. >> The list gets long as if a matrix is a solution to my problem, all of its >> permutations are, so I want to check to see if a matrix that I find is >> permutation of another matrix which is already in the list. Are there any >> fast ways to do this? Anything faster than checking all permutations of >> that matrix? >> >> If it helps, all my matrices are 0-1 matrices. >> > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
