14
$\begingroup$

Has the number $f(n)$ of $n \times n$, $0{-}1$ matrices whose determinant is $+1$ been enumerated? E.g., for $n{=}2$, there are $f(2)=3$ such matrices: $$ \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) \;,\; \left( \begin{array}{cc} 1 & 0 \\ 1 & 1 \\ \end{array} \right) \;,\; \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right) \;. $$ For $n{=}3$, I count $f(3)=84$ such matrices, from $$ \left( \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \;, $$ to $$ \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{array} \right) \;. $$

These matrices are a subset of $SL(n,\mathbb{R})$.

Update. Oh, I see $f(n)$ is OEIS A086264: $$ 1, 3, 84, 10020, 4851360, 9240051240. $$ No substantive information is provided in OEIS besides those six computed values.
Addendum. Unrevealing, but just as a curiosity, here is an overlay of the $84$ equal-volume parallelepipeds that result by applying the $n{=}3$ matrices to the $3 \times 2 \times 1$ box with lowerleft corner at the origin:   Parallelepipeds

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Geoff Robinson
    Commented Mar 22, 2015 at 0:45
  • $\begingroup$ Is it true that $f(n)=2^{\frac{n^2}{2}+o(n^2)}$? $\endgroup$
    – Richard Stanley
    Commented Mar 22, 2015 at 1:09
  • 2
    $\begingroup$ 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)}$. $\endgroup$
    – Noam D. Elkies
    Commented Mar 22, 2015 at 1:24
  • 2
    $\begingroup$ 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)!$. $\endgroup$
    – Richard Stanley
    Commented Mar 22, 2015 at 1:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Commented Apr 5, 2015 at 11:10

1 Answer 1

Reset to default
2
$\begingroup$

Will Orrick might have a good guess for this one. As far as I know the answer has only been determined for n up to 8. The number of matrices with odd determinant is known: it is $$\prod_{i=0}^{n-1}(2^n - 2^i)$$, which is about $0.3 * 2^{n^2}$. Noam Elkies has the best guess, but since the number of matrices achieving larger determinants drops off rapidly, I would guess more like $2^{n^2 -cn}$ for a small positive value of $c$.

From the arxiv paper of Zivkovic in a comment above, one has for matrices with absolute determinant value 1 : n=6, 18480102480; n=7,135491563468800; n=8, 3766962568171582080 . It is foolish to conjecture a value for $c$ based on this small amount of data, so I will only guess that $c \in [1/2 , 1]$.

One can use certain methods to guess at a better lower bound. I like the adjunction method of adding a row and column to a matrix of ADV 1. This gives a lower bound for $a_{n+1}$ of roughly $n^2*2^n*a_n$, with $a_n$ being the number of matrices of ADV=1 and order $n$.

Gerhard "It's Nice To Be Referenced" Paseman, 2015.03.23

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ ADV = ?$\mbox{}$ $\endgroup$
    – Joseph O'Rourke
    Commented Mar 24, 2015 at 0:58
  • $\begingroup$ ADV is absolute determinant value. $\endgroup$
    – The Masked Avenger
    Commented Mar 24, 2015 at 1:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .