Permanents and determinants of (0,1) matrices

[Jaap Spies]

Gordon Royle wrote:
>>n=6: Computing the determinants of all 2^36 6X6 (0,1) matrices took
>>~6 days CPU on a 500 MHz Digital Alphastation (using Gauss elimination).
>>I'll not try the permanents ... maybe someone else in this group with
>>more powerful resources could attack this problem?
> 
> 
> 
> Actually,  I think that large computer power is not needed..
> 
> Any nxn 0/1 matrix is the bipartite adjacency matrix of a bipartite graph
> with two parts of size n.
> 
> Each different labelling of this graph that preserves the two parts (ie does
> not interchange them) will give a different 0/1 matrix with the same
> permanent as the original matrix.
> 
> However the number of different labellings of such a graph is
> 
>     n! x n! / g
> 
> where g is the size of the automorphism group of the *bicoloured* graph (ie.
> only count automorphisms that do not exchange the two parts).
> 
> The advantage of this is that one graph with a trivial group will account
> for over half a million matrices in one hit, and of course we expect most of
> the graphs to have trivial group....
> 
> So, calculate the bicoloured graphs on 6+6 vertices - this takes about 1
> second to compute using Brendan McKay's "genbg" program, as there are only
> 251610 bicoloured graphs.
> 
> Find their groups (not permitting the parts to exchange): about 3 seconds to
> compute.
> 
> Find their permanents: about 20 seconds using a 10-line naive C program that
> simply goes through all possible permutations to find the permanent.
> 
> Each graph with group of size g will yield
> 
>     6! x 6! / g
> 
> matrices, all with the same permanent.
> 
> Add it all up and in less than 30 seconds cpu time we get the values
> below......
> 
> Permanents of 6x6 0/1 matrices
> (both singular and non-singular)
> --------------------------------
[...]

This is impressive, but unfortunately only part of the story.
The production of a list like Hugo's needs more power, next to elegance,
I suppose.

Jaap