[Nauty] graph for matrix automorphism

[Brendan McKay]

Say the matrix is A[0..nr-1,0..nc-1]. It doesn't have to be square.

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:
(a) Equivalences are generated by
     swapping rows (i1,i2):  same as permuting (r[i1],r[i2])(r'[i1],r'[i2]).
     swapping columns (j1,j2):  same as permuting 
(c[j1],c[j2])(c'[j1],c'[j2]).
     negating row i: same as swapping (r[i],r'[i]).
     negating column j: same as swapping (c[j],c'[j]).
Therefore, if A, B are equivalent then G(A), G(B) are isomorphic

(b) For the converse, consider this canonical labelling method. First
    apply nauty to the coloured graph G(A).  Now label the type-1 edges
    on the left as R[0]..R[nr-1] in the order that their first vertex 
appears
    in the canonical labelling of G(A).  Similarly C[0]..C[nc-1] on the 
right.
    Relabel the canonical graph so that the first end of R[i] becomes r[i]
    and the second end of R[i] becomes r'[i]; similarly with columns.
    Then we have a graph G(L) for some matrix L equivalent to A.
    This process is completely deterministic starting at the canonical
    form of the graph, so L is a canonical form for A.

Anyone see any problems?

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
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty