Permanents and determinants of (0,1) matrices

[Gordon Royle]

> 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)
--------------------------------

Perm #matrices

0 13906734081
1 2722682160
2 4513642920
3 3177532800
4 4466769300
5 2396826720
6 3710999520
7 2065521600
8 3253760550
9 1468314000
10 2641593600
11 1350475200
12 2210277600
13 1034061120
14 1980428400
15 829699200
16 1507653000
17 769932000
18 1405153800
19 535852800
20 1181471400
21 569548800
22 917352000
23 375148800
24 932753250
25 440951040
26 668314800
27 260461440
28 641881800
29 288792000
30 526312800
31 262915200
32 519110100
33 174020400
34 370202400
35 176947200
36 391171800
37 134460000
38 293695200
39 156556800
40 285573600
41 100029600
42 263107800
43 97329600
44 203684760
45 86184000
46 180273600
47 74649600
48 171406575
49 64562400
50 150660000
51 56592000
52 130744800
53 66722400
54 112680000
55 42249600
56 112514400
57 35553600
58 81043200
59 32400000
60 85420800
61 34171200
62 61052400
63 31492800
64 81939600
65 21513600
66 52732800
67 25660800
68 54572400
69 18144000
70 48168000
71 20822400
72 45721800
73 11059200
74 28674000
75 18835200
76 29872800
77 11836800
78 34444800
79 9072000
80 25478550
81 12247200
82 26532000
83 11404800
84 27806400
85 8812800
86 18964800
87 5184000
88 18489600
89 8424000
90 14752800
91 4665600
92 17949600
93 5313600
94 7128000
95 3853440
96 15123600
97 5961600
98 9234000
99 4665600
100 12798000
101 2592000
102 7617600
103 4665600
104 9282600
105 1555200
106 8834400
107 3628800
108 8924640
109 2462400
110 8640000
111 2073600
112 4509000
113 518400
114 4546800
115 2160000
116 3917700
117 2332800
118 2462400
120 5115168
121 2073600
122 2851200
123 1036800
124 4568400
125 1814400
126 1965600
127 1036800
128 5886000
129 1036800
130 2181600
131 1814400
132 3112200
134 1252800
135 1036800
136 2527200
137 532800
138 1540800
139 259200
140 1263600
141 648000
142 2160000
144 791700
145 518400
146 1166400
148 1182600
149 1036800
150 1288800
152 1084050
153 1036800
154 518400
156 1778400
158 259200
159 604800
160 1668600
161 518400
162 518400
164 583200
166 518400
167 518400
168 828000
170 626400
172 129600
173 129600
174 763200
176 8100
178 540000
180 295200
181 259200
182 129600
184 421200
186 72000
188 712800
190 259200
192 603900
195 259200
198 518400
199 259200
200 194400
203 86400
204 45600
206 388800
208 64800
210 86400
212 21600
214 21600
216 175200
220 145800
222 28800
224 129600
228 165600
230 64800
234 158400
238 259200
240 46980
245 86400
248 97200
252 46800
256 21600
258 14400
264 10800
265 720
270 57600
276 43200
284 64800
288 57825
298 43200
309 4320
312 7200
330 14400
336 6300
348 21600
360 240
362 5400
384 900
408 3600
426 2400
480 180
504 450
600 36
720 1