In the January 1963 (p. 94) issue of the American Mathematical Monthly, D.C.B. Marsh proved that for a $3 \times 3$ determinant formed from a random distribution of the integers $1, 2, \ldots, 9,$ the probability that it is odd is $4/7.$ His proof was based on the expansion of the determinant into six terms of three products each and counting all possible ways the determinant could be odd. However, even with the $4 \times 4$ determinant, the expansion consists of $24$ terms of $4$ products each and it is not clear to me how to apply his method. If one looks at the $4 \times 4$ determinant itself and decides to construct it row by row, which must all be linearly independent, the first row can be anything except all even numbers. Thus the number of possible first rows is 16x15x14x13 minus to number of all possible even first rows which is $7\times6\times5\times4.$ But the number of second rows is $121 \times 11 \times 10 \times 9$ minus the number of even rows, which alas is now indeterminate. Perhaps one can obtain a recursion formula for determinants of order $n$ from those of order $n-1$ but I am unable to find one.
-
12$\begingroup$ I have not seen this problem before but my first instinct would be to reduce everything mod 2, and then the problem can be reformulated as filling an n-by-n array with a certain number of 0s and 1s (the precise number depending on the parity of n) and then calculating the determinant mod 2. $\endgroup$– Yemon ChoiCommented Apr 10, 2023 at 0:38
-
1$\begingroup$ In the 4x4 case, there are 12,870 matrices to check mod 2. Of these, 4752 have odd determinant. Thus over the integers, $7725337804800 = 4752\times 8! \times 8!$ have odd determinant. $\endgroup$– Steven LandsburgCommented Apr 10, 2023 at 3:04
-
2$\begingroup$ Shouldn't the number of possible all even first rows be $8 \times 7 \times 6 \times 5$? $\endgroup$– MalkounCommented Apr 10, 2023 at 3:25
-
1$\begingroup$ For the $5 \times 5$ case, $1849200$ of the $5200300$ matrices mod $2$ have odd determinant. The number of nonsingular $n \times n$ matrices over $GF(2)$ with $k$ ones is OEIS sequence A309244. Unfortunately the data don't go past $n=5$. $\endgroup$– Robert IsraelCommented Apr 10, 2023 at 4:02
-
5$\begingroup$ I would imagine that the probability should be close to $\prod_{k=1}^n (1 - 2^{-k})$, which is the probability that a random $n \times n$ matrix with coefficients in ${\bf F}_2$ is non-singular (see e.g., math.stackexchange.com/questions/71288/…). In particular, the probability should converge to $\prod_{k=1}^\infty (1-2^{-k}) = 0.2887\dots$ in the limit. $\endgroup$– Terry TaoCommented Apr 13, 2023 at 4:24
2 Answers
(Partial answer)
In GF(2), row and column permutations preserve the determinant. The equivalence classes under those operations are non-isomorphic bipartite graphs with $n$ vertices on each side and $\lceil n^2/2\rceil$ edges.
Each graph corresponds to $(n!)^2/a$ matrices, where $a$ is the order of the colour-preserving automorphism group.
The number of graphs for $n=3,\ldots,8$ is 7, 55, 755, 30310, 3576980, 1415871516. It would take less than half an hour to process them.
Order 9 gives about $2\times 10^{12}$ graphs, which would be a plausible but quite long computation.
Here are the counts of $n\times n$ binary matrices with $\lceil n^2/2\rceil$ ones, nonsingular over GF(2).
| n | nonsingular graphs | nonsingular matrices |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 3 | 72 |
| 4 | 10 | 4752 |
| 5 | 161 | 1849200 |
| 6 | 5992 | 2811499200 |
| 7 | 804614 | 19379998310400 |
| 8 | 340481465 | 541683750188689920 |
That took around 10 minutes. I estimate $n=9$ would take about 1 month and the number of matrices will be something like $3\times 10^{22}$.
Dave raises the issue of factorizations. Note that the count must be divisible by $(n!)^2/A$, where $A$ is the least common multiple of the automorphism group sizes. For $n=2,\ldots,8$, the lcm is 2, 4, 24, 24, 144, 2880. With these guaranteed factors removed, $n=7$ is the only one with more than one small factor remaining.
-
$\begingroup$ These data suggest that the 3 by 3 case with 4/7 of the determinants odd is an outlier: approximations of the ratios are 1., 0.333333, 0.571429, 0.369231, 0.355595, 0.309802, 0.30662, 0.295578. So far, the probability of an odd determinant is less than 1/2 except for $n=1, 3$. $\endgroup$ Commented Apr 12, 2023 at 15:44
-
1$\begingroup$ I find it odd that the largest square factors are $1^2$, $6^2$ $12^2$, $20^2$, $120^2$, $40320^2$, $336^2$ while the largest prime factors are $2$, $3$, $11$, $67$, $431$, $131$, $24209483$. Somehow the $n=8$ factorisation feels quite different from the others. $\endgroup$ Commented Apr 12, 2023 at 18:51
Just a comment, which is too long to be a comment per se. For the $n = 3$ case, the number of favorable cases, which is the number of non-singular $3 \times 3$ matrices with coefficients in $GF(2)$, having exactly $5$ ones (and thus $4$ zeros) mod $2$, can be calculated as follows:
- 113: 6
- 131: 6
- 311: 6
- 122: 18
- 212: 18
- 221: 18
What I mean by, say $113$ is that the number of ones in the first row is $1$, that of the second row is $1$ and that of the third row is $3$, and so on, and on the RHS is the corresponding number of favorable cases. I am assuming you first choose the numbers in the first row, then you choose those of the second row and finally you choose the numbers of the last row. So the total number of favorable cases is thus $72$.
On the other hand, the total number of $3 \times 3$ matrices with coefficients in $GF(2)$ having precisely $5$ ones mod $2$ is: $\binom{9}{5} = 126$.
Hence the probability of having an odd determinant in the original $3 \times 3$ problem is: $72 / 126 = 4/7$, indeed.
I guess I like to see things my way, just for the fun of it. Thank you @Robert Israel for pointing out a mistake in a previous line of reasoning of mine.
Edit 1: I did the calculations for $n = 4$. It is indeed much more complicated. Using the same notation as above, we have:
- 4211 (up to permutation): $1 \times 6 \times 4 \times 2 = 48$ ($12$ such terms)
- 3311 (up to permutation): $4 \times 3 \times (2 \times 3 + 2 \times 2) = 120$ ($6$ such terms)
- 3221 (up to permutation): $4 \times [3 \times (2 \times 1 + 2 \times 3 + 1 \times 2) + 3 \times (2 \times 3 + 2 \times 3 + 1 \times 2)] = 288$ ($12$ such terms)
So the total number of non-singular $4 \times 4$ matrices with coefficients in $GF(2)$ having exactly $8$ ones mod $2$ is: $$ 48 \times 12 + 120 \times 6 + 288 \times 12 = 4752, $$ as claimed in the comments. Moreover, I could turn this idea into an algorithm too.
Finally, the total number of $4 \times 4$ matrices with coefficients in $GF(2)$ having exactly $8$ ones is $$ \binom{16}{8} = 12870. $$
Let me explain a little how I got these numbers.
First, I listed all partitions of $8$ (the total number of ones) having length $4$ (since $n = 4$), with each of the numbers not exceeding $4$ (or $n$, for the general case) and without using $0$, since a row contain $0$ ones must be all zero and so the matrix is then singular.
Then, for each such partition, say $8 = 4 + 2 + 1 + 1$, which I am writing simply as $4221$, I first consider the first number, namely $4$ in this example. How many $4$-dimensional rows contain exactly $4$ ones? There is only $1$ such row, namely $(1, 1, 1, 1)$. Then I compute the span of the existing rows. We only have 1 row for the time being and the span is
$$ \{ (0, 0, 0, 0), (1, 1, 1, 1) \}. $$
I then consider the second number, which $2$ in this case. There are in total $6$ rows having exactly 2 ones, which are not in the span of the existing rows. I look for patterns and see which cases are alike. In this case, it is enough to consider say the second row to be
$$ (1, 1, 0, 0) $$
and then multiply the number of matrices by $6$ (since the other 5 cases for the second row are all similar to this one). We then compute the span of the existing rows. In addition to the previous span, we also add the second row to the previous span, obtaining the following additional vectors:
$$ \{ (1, 1, 0, 0), (0, 0, 1, 1) \}. $$
And so on. In the end, the number of non-singular matrices we get for the partition $4221$ is:
$$ 1 \times 6 \times 4 \times 2 = 48. $$
The number of times for example $4211$, up to permutation, appears, is the multinomial coefficient
$$ \frac{4!}{1! 1! 2!} = 12. $$
This is how you get these "multiplicities", so to speak. It can be checked that the case $2222$ does not correspond to any non-singular matrix of the required type. Indeed, the $e_i + e_j$ for $1 \leq i < j \leq 4$ span a proper subspace of $GF(2)^4$, namely the subspace $$ x_1 + x_2 + x_3 + x_4 = 0. $$
Edit 2: by writing a naive algorithmic implementation of the above method (which doesn't take advantage of the fact that there are cases that are alike), I can confirm that the number of $5 \times 5$ non-singular matrices with coefficients in $GF(2)$ having $13$ ones is indeed $1849200$, as obtained for example by @Brendan McKay. But already for $n = 6$, it has been $10$ minutes and the algorithm hasn't stopped executing (while the $n = 4$ and $n = 5$ cases ran very fast). So Brendan McKay's algorithm is much more efficient.
-
$\begingroup$ Was trying to use this method for $n=4$; the only thing I'm certain of is that it's significantly harder than your nice $n=3$ treatment. $\endgroup$ Commented Apr 12, 2023 at 15:34