[Nauty] graph for matrix automorphism

[Brendan McKay]

Using vertex colours has the advantage that the canonical labelling is
restricted to permutation of vertices within each colour.  As well as being
often more efficient, it can greatly simplify the task of reconstructing
a canonical object (matrix, in this case) from the canonical graph.

As for "empirical math", I've seen plenty of bugs that showed themselves
in literally one in a billion cases.  So, yes, proofs are needed.

Brendan.


On 12/02/2016 7:43 PM, Sterten at aol.com wrote:
> 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
>