[Nauty] graph for matrix automorphism
Brendan McKay
brendan.mckay at anu.edu.au
Fri Feb 12 15:10:02 AEDT 2016
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
More information about the Nauty
mailing list