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