Permanents and determinants of (0,1) matrices
all at abouthugo.de
all at abouthugo.de
Mon Nov 3 01:34:01 CET 2003
Jaap Spies <j.spies at hccnet.nl> schrieb am 02.11.2003, 02:13:11:
> Jaap Spies wrote:
> > Yuval Dekel wrote:
> >> a(n) = number of different values taken by permanents of nonsingular
> >> nxn (0,1) matrices ,
> >> b(n) = number of different values taken by determinants of nxn (0,1)
> >> matrices .
> >>
[...]
> Here are my new results
>
> n=1
> {1, 1}
> n=2
> {1, 6}
> n=3
> {1, 150}, {2, 6}, {3, 18}
> n=4
> {1, 13032}, {2, 1440}, {3, 4992}, {4, 672}, {5, 1440}, {6, 288}, {7, 576}
> {9, 24}, {11, 96}
> n=5
> {1, 3513720}, {2, 693840}, {3, 2626800}, {4, 604200}, {5, 1451400}, {6, 468000}
> {7, 962400}, {8, 252000}, {9, 425400}, {10, 190800}, {11, 379200}, {12, 97200}
> {13, 205440}, {14, 100800}, {15, 132000}, {16, 28800}, {17, 108000}, {18, 28800}
> {19, 44400}, {20, 33600}, {21, 61200}, {22, 9600}, {23, 14400}, {25, 36000}
> {26, 7200}, {29, 14400}, {31, 14400}, {33, 2400}, {39, 7200}, {44, 120}, {53, 600}
>
> So a(1)=1, a(2)=1, a(3)=3, a(4)=9, a(5)=31, ...,
>
> a(6) is hard to get.
>
> Jaap Spies
SeqFans,
independent verification never hurts, so here are my
results, which agree perfectly with those of Jaap (column 4)
I have included also the counts for the permanents
of all (0,1)-matrices (column 3) and for the singular
(0,1) matrices (column 5).
The last column also makes a new sequence:
Different permanents of singular (0,1) matrices (starting at 1)
1 2 4 10 32
I hope this table does not violate Gerard's length limit by an
intolerable amount; sorry.
Value
| Number of (0,1) matrices with det=value
| | Number of matrices with permanent=value
| | | Number of matrices with
| | | det /=0 and permanent=value
| | | | Number of matrices
| | | | with det=0 and
| | | | permanent=value
N: 2
-1 3 0 0 0
0 10 9 0 9
1 3 6 6 0
2 0 1 0 1
N: 3
-2 3 0 0 0
-1 84 0 0 0
0 338 265 0 265
1 84 150 150 0
2 3 69 6 63
3 0 18 18 0
4 0 9 0 9
6 0 1 0 1
N: 4
-3 60 0 0 0
-2 1200 0 0 0
-1 10020 0 0 0
0 42976 27713 0 27713
1 10020 13032 13032 0
2 1200 10800 1440 9360
3 60 4992 4992 0
4 0 4254 672 3582
5 0 1440 1440 0
6 0 1536 288 1248
7 0 576 576 0
8 0 648 0 648
9 0 24 24 0
10 0 288 0 288
11 0 96 96 0
12 0 48 0 48
14 0 72 0 72
18 0 16 0 16
24 0 1 0 1
N: 5
-5 3600 0 0 0
-4 43560 0 0 0
-3 144720 0 0 0
-2 1213920 0 0 0
-1 4851360 0 0 0
0 21040112 10363361 0 10363361
1 4851360 3513720 3513720 0
2 1213920 4339440 693840 3645600
3 144720 2626800 2626800 0
4 43560 3015450 604200 2411250
5 3600 1451400 1451400 0
6 0 1872800 468000 1404800
7 0 962400 962400 0
8 0 1295700 252000 1043700
9 0 425400 425400 0
10 0 873000 190800 682200
11 0 379200 379200 0
12 0 514300 97200 417100
13 0 205440 205440 0
14 0 437400 100800 336600
15 0 132000 132000 0
16 0 206550 28800 177750
17 0 108000 108000 0
18 0 212200 28800 183400
19 0 44400 44400 0
20 0 119550 33600 85950
21 0 61200 61200 0
22 0 69600 9600 60000
23 0 14400 14400 0
24 0 82475 0 82475
25 0 36000 36000 0
26 0 33000 7200 25800
28 0 32400 0 32400
29 0 14400 14400 0
30 0 18400 0 18400
31 0 14400 14400 0
32 0 24300 0 24300
33 0 2400 2400 0
34 0 5400 0 5400
36 0 11300 0 11300
38 0 7200 0 7200
39 0 7200 7200 0
40 0 5400 0 5400
42 0 4400 0 4400
44 0 120 120 0
46 0 3600 0 3600
48 0 1600 0 1600
50 0 3600 0 3600
53 0 600 600 0
54 0 400 0 400
60 0 1200 0 1200
64 0 600 0 600
72 0 100 0 100
78 0 200 0 200
96 0 25 0 25
120 0 1 0 1
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?
Hugo
More information about the SeqFan
mailing list