checking if two matrices are permutation similar

[Keivan Monfared]

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.

[Volker Braun]

Its not clear what you mean by "permutation", row? column? both? In any case, sorting is faster than trying all permutations.

[Christophe Bal]

Hello.

Can you give a small example of your matrices ?

Christophe.

--
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...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/groups/opt_out.

[Keivan Monfared]

I mean, in A and B are two matrices in my list, and there are permutation matrices P and Q such that A=PBQ, I want to keep only A, or B, and not both.

[Keivan Monfared]

Yes, Here is an example:

I have A= [[0,1,1],[1,1,1],[1,0,1]], B=[[1,1,1],[1,0,1],[0,1,1]] and C=[[1,1,1],[1,1,0],[1,0,1]] in my list, but I only need to keep one of them, since B is obtained from 1 by permuting the rows with (2,1,3). Also, C is obtained from A by permuting the rows by (1,2) and permuting columns by (3,1).

[Tom Boothby]

Keivan,

I'm not sure if this is the best way to do this (e.g. if there's a
naive approach we teach in undergrad linear algebra, it escapes me at
the moment), but I'm a graph theorist so it's the approach that
readily comes to mind, and easy to implement. Treat your graphs as
incidence matrices of bipartite graphs. We could check if two
matrices were isomorphic in this way, but the better approach for "do
I have a new object" is generally to compute canonical labels.

The following computes the number of inequivalent matrices.

for n in range(1,6):
uniquematrices = {}
for M in MatrixSpace(GF(2),n,n):
a,b = M.dimensions()
G = Graph([(i+1,-j-1) for i in range(a) for j in range(b) if M[i,j]])
L = G.canonical_label(partition = [[v for v in G if v>0],[v
for v in G if v<0]])
key = L.graph6_string()
uniquematrices[key] = M
print len(uniquematrices)

It's dog slow, but the first 3 numbers come up pretty quick: 2,7,37.
That's enough to find it in Sloane's:
http://oeis.org/search?q=2%2C7%2C36 and the first hit has a huge
number of terms of the sequence. That sequence has a couple of
references that might help, if this is too slow.

[David Joyner]

On Thu, Feb 27, 2014 at 2:25 PM, Keivan Monfared <k1mon...@gmail.com> 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?

I don't know how fast it is but GAP (included with Sage) has a command
TransformingPermutations which might help:
http://www.gap-system.org/Manuals/doc/ref/chap71.html#X7D721E3D7AA319F5

>
> If it helps, all my matrices are 0-1 matrices.
>

[Andrew]

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

For 0-1 matrices, however, I wouldn't be surprised if the sets of row and column sums determine the orbit uniquely.

Andrew

[Jori Mantysalo]

On Thu, 27 Feb 2014, Keivan Monfared wrote:

> I want to check to see if a matrix that I find is permutation of another
> matrix which is already in the list.

You should define some order for matrices. Then you only need to compare
about log N (where N=number of matrices already in list) matrices to see
if you already have matrix in question at list, and if not, where to place
it.

* * *

If you just ask generally "how to see if A =~ B?", where =~ means "is
similar to some respect", then I'll ask about propabilities. If you mostly
have NOT A =~ B, then try to find some fast way to check if A and B are
not similar.

To give extremely simple example: to see if finite groups A and B are
isomorphic, see if they have same number of elements.

--
Jori Mäntysalo

[Dima Pasechnik]

On 2014-02-28, Andrew <andrew...@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.