[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