[Nauty] graph for matrix automorphism
Sterten at aol.com
Sterten at aol.com
Sat Feb 13 06:40:10 AEDT 2016
my old program only works for uncolored graphs, and coloring is one more
thought ...
so that's easier for me.
Now, with that program, for 2xn matrices I get counts
3,8,16,30,50,80,120,175,245,336,448,...
https://oeis.org/A002624
I don't see the connection
and for 3xn : 4,16,58,190,570,1600,
for nxn it's 2,8,190,1302,
as for proofs, they can have errors, holes, ... you aren't 100% sure in
practice
Guenter.
In a message dated 2/12/2016 8:23:23 P.M. Westeuropäische Normalzeit,
Brendan.McKay at anu.edu.au writes:
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
>
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
http://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list