[Nauty] Matrix isomorphism

Wayne Kelly w.kelly at qut.edu.au
Thu Aug 18 13:42:55 AEST 2016


Thanks Gordon (and Brendan) for your replies.

So I can enumerate non-isomorphic matrices by enumerating bipartite graphs using Nauty. Great.

My subsequent question is: what will be the basic structure of my new algorithm with respect to combining the special property that I require of my matrices and the issue of avoiding isomorphism? 

It seems there are two possible approaches:
1) Use Nauty to enumerate all possible non-isomorphic bipartite graphs of a given size and then check each one to determine if it satisfies the property that I require. I think that approach would be slow since most bipartite graphs will not satisfy the property that I require.

At present I have a recursive algorithm that efficiently enumerates all matrices that have the property that I desire (building the matrices row by row), but it includes isomorphic solutions.
I generate rows in a canonical order, so I avoid isomorphisms due to row permutations, but not due to column permutations.
2) So, what I would prefer is to be able to alter that algorithm, so that when I'm extending my matrices by adding an extra row - it restricts the number of expansions considered by taking into account isomorphisms (due to column permutations). I understand that Nauty basically works in that way, where it builds graphs of size n by expanding graphs of size n-1. So, is it possible to use the Nauty library/API in such a manner?

Cheers, Wayne.

Dr Wayne Kelly | Senior Lecturer
Science and Engineering Faculty | Queensland University of Technology

S Block, Level 10, Room S-1011 (enter via S-1013), Gardens Point Campus 
ph 3138 9336 | email w.kelly at qut.edu.au 
CRICOS No 00213J
________________________________________
From: Gordon Royle <gordon.royle at uwa.edu.au>
Sent: Thursday, 18 August 2016 11:15 AM
To: Wayne Kelly
Cc: nauty at anu.edu.au
Subject: Re: [Nauty] Matrix isomorphism

Any such matrix can be viewed as the bipartite adjacency matrix of a graph - i.e. the rows are the vertices of one colour, and the columns are the vertices of the second colour, and conversely any bipartite graph yields such a matrix (or two matrices if you care about which is rows, which is columns).

Isomorphisms between such graphs that preserve the colours correspond to permuting the rows and the columns of the matrix, but not exchanging them. Isomorphisms that are permitted to swap the colours correspond to matrix isomorphisms swapping the rows and columns.



On 18 Aug 2016, at 8:34 am, Wayne Kelly <w.kelly at qut.edu.au<mailto:w.kelly at qut.edu.au>> wrote:

Hi,

I'm trying to enumerate binary (0-1) matrices of a given size that satisfying a specific matrix property (related to finite projection planes), but want to exclude isomorphic matrices, i.e. I don't care about the row or column order of the matrix.

Can nauty help me with this problem? I realize that nauty is designed to work with Graphs rather than Matrices, but thought the same kinds of techniques may be useful.

Cheers, Wayne.

Dr Wayne Kelly | Senior Lecturer
Science and Engineering Faculty | Queensland University of Technology

S Block, Level 10, Room S-1011 (enter via S-1013), Gardens Point Campus
ph 3138 9336 | email w.kelly at qut.edu.au<mailto:w.kelly at qut.edu.au>
CRICOS No 00213J
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au<mailto:Nauty at anu.edu.au>
http://mailman.anu.edu.au/mailman/listinfo/nauty

Professor Gordon Royle
School of Mathematics and Statistics
University of Western Australia
Gordon.Royle at uwa.edu.au<mailto:Gordon.Royle at uwa.edu.au>
















More information about the Nauty mailing list