[Nauty] graph for matrix automorphism
Sterten at aol.com
Sterten at aol.com
Fri Feb 12 19:43:32 AEDT 2016
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