13
$\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

$\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$ Mar 22 '15 at 0:45
  • $\begingroup$ Is it true that $f(n)=2^{\frac{n^2}{2}+o(n^2)}$? $\endgroup$ Mar 22 '15 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$ Mar 22 '15 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$ Mar 22 '15 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
    Apr 5 '15 at 11:10
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

$\endgroup$
2
  • 1
    $\begingroup$ ADV = ?$\mbox{}$ $\endgroup$ Mar 24 '15 at 0:58
  • $\begingroup$ ADV is absolute determinant value. $\endgroup$ Mar 24 '15 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.