Permanents and determinants of (0,1) matrices

[all at abouthugo.de]

Gordon Royle <gordon at csse.uwa.edu.au> schrieb am 03.11.2003, 15:55:03:
> > 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..
>

Gordon,

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?

Seqfans,

besides from that we now have quite a lot of candidates for new
sequences that would nicely fit into the framwork given by the
following existing sequences:

http://www.research.att.com/projects/OEIS?Anum=A046747
1,10,338,42976,21040112,39882864736,292604283435872
n X n rational {0,1}-matrices of determinant 0.

http://www.research.att.com/projects/OEIS?Anum=A086264
1,3,84,10020,4851360,9240051240
Number of real {0,1} n X n matrices having determinant=1.

http://www.research.att.com/projects/OEIS?Anum=A003432
1,1,2,3,5,9,32,56,144,320,1458,3645,9477
Hadamard maximal determinant problem: largest determinant of a
(real) {0,1}-matrix of order n.

http://www.research.att.com/projects/OEIS?Anum=A051752
1,3,3,60,3600,529200,75600
Number of n X n (real) {0,1}-matrices having determinant A003432(n).

http://www.research.att.com/projects/OEIS?Anum=A055165
1,6,174,22560,12514320,28836612000,270345669985440
Number of regular n X n matrices with rational entries equal to 0 or 1.

http://www.research.att.com/projects/OEIS?Anum=A013588
2,2,3,4,6,10,19,41 
Smallest positive integer not the determinant of an n X n 0-1 matrix.
a(8)=41 not independently verified. From my own random simulations
a(8) is correct with high probability, if not then a(8)>42,/=44,/=48.

http://www.research.att.com/projects/OEIS?Anum=A087982
1,0,2,8,24,128
Maximal permanent of a nonsingular n X n (+1,-1)-matrix.

http://www.research.att.com/projects/OEIS?Anum=A088672
0,1,9,265,27713,10363361 (plus new term a(6)=13906734081 from G.Royle)
Number of n X n {0,1} matrices with zero permanent.

http://www.research.att.com/projects/OEIS?Anum=A087983
2,3,6,16,51 (plus one new term a(6)=220 from Gordon Royle's list)
Number of different values taken by permanent of n X n (0,1)-matrix.

New sequences:

Number of different values that can be assumed by the 
determinant of a real (0,1)-matrix of order n. 
Starting at n=1: 
2,3,5,7,11,19,43, next term 89<=a(8)<113 (hard!)

Maximal permanent of a real non-singular (0,1)-matrix of order n:
1 1 3 11 53

Number of real non-singular (0,1)-matrices having maximal permanent=
a(from previous sequence)
1 6 18 96 600


Number of different values that can be assumed by the
permanent of a real non-singular (0,1)-matrix of order n:
1 1 3 9 31 (will Jaap Spies compute a(6)?)

Number of different values that can be assumed by the
permanent of a real singular (0,1)-matrix of order n:
1 2 4 10 32

Smallest positive integer not the permanent of a nXn (0-1) matrix.
2 3 5 13 27 119 (last term from Gordon Royle's list)

Maybe also the finite sequences:

How many times does the determinant (D) or permanent (P) of an m*m
real (0,1)-matrix assume the value n (starting at n=0).
For determinants negative values are assumed with the same counts.

m=2
D: 10,3
P: 9,6,1

m=3
D: 338,84,3
P: 265,150,69,18,9,0,1,

m=4
D: 42976,10020,1200,60
P: 27713,13032,10800,4992,4254,1440,1536,576,648,24,288,96,48,0,72,
   0,0,0,16,0,0,0,0,0,1

m=5
D: 21040112,4851360,1213920,144720,43560,3600
P: 10363361,3513720,4339440,2626800,3015450,1451400,1872800,962400,...

m=6
D: 39882864736,9240051240,3868663680,768723480,418703040,63612360,
   46569600,6438600,5014800,529200
P: 13906734081 2722682160 4513642920 3177532800 4466769300 2396826720 
   3710999520 2065521600 3253760550 1468314000 2641593600 1350475200 
   2210277600 1034061120 1980428400 829699200 1507653000 769932000 
   1405153800 535852800 1181471400  

Please check. Which of these shall I submit?

Hugo