Permanents and determinants of (0,1) matrices

[Gordon Royle]

> many thanks for your enlightening analysis and the results for n=6.
> Do you think there is any chance to circumvent the brute force
> approach, when we are dealing with the combination of conditions
> from the determinants (singular / non-singular) and the permanents,
> which can be considerably simplified with your graph based approach?

Yes, all of them can be done in a broadly similar way...

Singularity is preserved by independent row/column permutations and so
either all the matrices in a single graph isomorphism class are singular, or
none of them are.

Hence we can simply eliminate (or count, or whatever)  these right at the
beginning just by reference to the graphs themselves...

Determinant is a bit more subtle.. a permutation of the rows and columns may
either leave the determinant unchanged or negate it... this depends on
whether the permutation is an even or odd permutation respectively.

This means that each "isomorphism class" of matrices either
    - has all matrices with the same determinant, or
    - has half with determinant d, and half with determinant -d for some d

I haven't worked this through fully and checked it by implementing it, but
it seems clear to me (at the moment) that if the automorphism group of the
graph contains only EVEN permutations, then the second case will hold and
the matrices will split up into two halves of opposite sign, while if the
automorphism group of the graph contains half even/half odd permutations,
then they will all be of the same sign. (Of course if d=0, we don't care
which case holds...)

In either case though, it is only necessary to calculate the determinant of
one matrix per class, thus saving a factor of up to n! x n! (actually, it is
about n! x n! / 2 it seems in the n=5,6 range)...

All the best

gordon