[Nauty] graph for matrix automorphism

[Pieter Eendebak]

Hi,

Thanks for the suggestions. I will use the approach with vertex colors, as
I need to reconstruct my matrix again from the canonical graph.

With kind regards,
Pieter



On Fri, Feb 12, 2016 at 12:36 PM, Brendan McKay <Brendan.McKay at anu.edu.au>
wrote:

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