[Nauty] graph for matrix automorphism

[Sterten at aol.com]

Let m=nr,n=nc. Vertex-numbering starts with 1. 
Instead of the 2 colors  I take an extra vertex with number m+m+n+n+1
to which I connect the m+m row  vectors. [only vertex that gives triangles] 
Given matrix X(m,n). By your  description I construct the adjacency matrix 
A(m+m+n+n+1,m+m+n+n+1) this  way:

43 FOR I=1 TO M+M:A(I,M+M+N+N+1)=1:A(M+M+N+N+1,I)=1:NEXT
44 FOR  I=1 TO M:A(I,M+I)=1:A(M+I,I)=1:NEXT
45 FOR J=1 TO  N:A(M+M+J,M+M+N+J)=1:A(M+M+N+J,M+M+J)=1:NEXT
46 FOR I=1 TO M:FOR J=1 TO  N
47 IF X(I,J)=1 THEN  
A(I,M+M+J)=1:A(M+M+J,I)=1:A(M+I,M+M+N+J)=1:A(M+M+N+J,M+I)=1
48 IF X(I,J)=-1  THEN 
A(I,M+M+N+J)=1:A(M+M+N+J,I)=1:A(M+I,M+M+J)=1:A(M+M+J,M+I)=1
50 NEXT  J,I

correct ?
Then we can easily create some thousand random "Xs" and  check the 
correspondent "As" with Nauty ...
Empirical math, no proof needed  ;-)

Guenter

======================================================

Define  a coloured graph G(A) with 2*(nr+nc) vertices:
First colour:  r[0..nr-1], r'[0..nr-1]
Second colour:  c[0..nc-1],  c'[0..nc-1].

Add edges as follows:
(1)  r[i]--r'[i] for  i=0..nr-1;  c[j]--c'[j] for j=0..nc-1.
(2)  r[i]--c[j] and  r'[i]--c'[j] for all A[i,j] = +1
(3)  r[i]--c'[j] and r'[i]--c[j] for  all A[i,j] = -1.
Zeros in A don't cause any edges.

I claim that  matrices A and B are equivalent iff G(A) and G(B) are  
isomorphic,

Proof outline:
...

Brendan.


On  12/02/16 00:58, Pieter Eendebak wrote:
> Hi all,
>
> On the  nauty+traces webpage there are some examples of matrix ismorphism
>  problems formulated as a graph isomorphism problem (which can be solved  
by
> nauty).
>
> I am looking for a correspondence between  matrices and graphs for the
> following isomorphism.
> We have  matrices which have values +1, 0 and -1. Allowed matrix
> transformations  are row permutations, column permutations, negation of 
rows
> and negation  of columns.
> (this is essentialy Hadamard equivalence with the addition  of zeros in 
the
> matrix)
>
> As an alternative a  correspondence between the matrix and a graph 
allowing
> for row  permutations, column permutations, permutation of the symbols in 
a
> row  and permutations of the symbols in a column will work for me. 
(because
>  of the numbers of 0's, +1 and -1's in the matrix I know that 0 cannot be
>  permuted to either +1 or -1).
>
>
> With kind regards,
>  Pieter