Timeline for Enumeration of $0-1$ matrices with determinant $1$
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2015 at 11:58 | comment | added | Gil Kalai | Regarding det (A) behaving uniformly below the value $n^{n/2}$ there is a heuristic which slightly corrects it (but it looks that it will not make a difference regarding the $2^{n^2-O(n\log n)}$ estimate. The heuristic is that mod a prime the determinant of A behaves like that of a random matrix modulo p. This gives some guess regarding ,e.g., $prob (det (A)=2) /Prob (det (A)=1). | |
| Apr 5, 2015 at 11:10 | comment | added | Gil Kalai | There are several heuristic arguments for the asymptotic of f(n) which unfortunately gives different answers. Probably I would vote against the idea that upper unitriangular matrices gives most contribution. There are pretty good results and even better conjectures for the number of matrices with determinant 0. This occurse (conjecturaly) mainly if a row (column) is zero or two rows (columns) agree which gives 2^n^2 / n^2 2^n. This suggests that f(n) is also at most 2^n^2/c^n. It is reasonable to believe that det (A) is pretty close to being uniform below n^n/2 which justifies Noam's guess. | |
| Mar 24, 2015 at 11:22 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Typo.
|
| Mar 24, 2015 at 1:03 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Added image.
|
| Mar 23, 2015 at 17:59 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Mar 22, 2015 at 2:35 | comment | added | The Masked Avenger | For small n, over the integers, there is arXiv.org/abs/math.CO/0511636 , but you have to divide the count by 2 as classes by absolute determinant values are enumerated. | |
| Mar 22, 2015 at 1:54 | comment | added | Richard Stanley | I am guessing that most of the contribution comes from upper unitriangular matrices (though maybe this is nonsense). Why should the determinant distribution be approximately uniform in the range $[-n^{n/2},n^{n/2}]$? On the other hand, the mean of $\mathrm{det}(A)^2$ is $4^{-n}(n+1)!$. | |
| Mar 22, 2015 at 1:24 | comment | added | Noam D. Elkies | Why is that a reasonable guess? There are $2^{n^2}$ zero-one matrices, each with $|{\rm disc}| < n^{n/2}$, so I'd expect $2^{n^2 - O(n\log n)}$. | |
| Mar 22, 2015 at 1:09 | comment | added | Richard Stanley | Is it true that $f(n)=2^{\frac{n^2}{2}+o(n^2)}$? | |
| Mar 22, 2015 at 1:04 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
OEIS reference.
|
| Mar 22, 2015 at 0:45 | comment | added | Geoff Robinson | A good place to start might be with the upper triangular unipotent matrices $U$ with only $0$s and $1$s above the diagonal, then look at $\sigma u \tau$ for $u \in U$ and $\sigma$ and $\tau$ permutation matrices where the associated permutations have the same sign. | |
| Mar 22, 2015 at 0:37 | history | asked | Joseph O'Rourke | CC BY-SA 3.0 |