4
$\begingroup$

Consider $n\times n$ matrices with entries in $\{0,1\}$. The determinants of these ranges from $0$ to the Hadamard bound $\frac{(n+1)^{\frac{n+1}2}}{2^n}$. Assume $n$ is large enough.

What does the distribution of the determinants look like? Is it normal or skewed?

What proportion of such $n\times n$ determinants is singular?

$\endgroup$

2 Answers 2

4
$\begingroup$

Much is known about these Hadamard matrices, this talk by William Orrick gives a good overview:

The first few moments of the determinant $\det M$ are known exactly, for large $n$ the distribution of $|\det M|$ is conjectured to be log-normal.

For the number of singular matrices, see OEIS. The large-$n$ limit of the probability that a $n\times n$ matrix is singular is conjectured to be $n^2/2^n$.

$\endgroup$
2
  • 1
    $\begingroup$ The poster is talking about binary matrices, with entries from 0,1. There is a transformation that carries them to matrices with 1,-1, some of which are Hadamard. Also, I would say much is unknown, and that Orrick's talk is close to state of the art at present. Gerhard "Prefers The Phrase 'Binary Matrices'" Paseman, 2017.06.02. $\endgroup$ Commented Jun 2, 2017 at 16:13
  • $\begingroup$ Standard usage is \det M rather than {\rm det}\,M. If you write a\det b or a\det(b) you see $a\det b$ or $a\det(b)$ respectively, and I include both examples so that you can see the context-dependent nature of the spacing. $\endgroup$ Commented Jun 2, 2017 at 20:54
2
$\begingroup$

Let $A_n$ be a random matrix where each entry is either $1$ or $-1$, and $B_n$ be a random matrix where each entry is either $0$ or $1$. The distributions of the determinants of these two matrices are closely related.

Indeed, since the distribution of $A_n$ is symmetric around $0$, we can WLOG assume that the first row and column of our $A_n$ are entirely equal to $1$. Subtract the first row from each other row, and we're left with a lower right $(n-1) \times (n-1)$ matrix where each entry is either $0$ or $-2$. Pulling out a factor of $-2$ from each row (and again using the fact that the distribution is symmetric around $0$), we see that the determinant of $A_n$ has the same distribution as $2^{n-1}$ times the determinant of $B_{n-1}$.

The distribution of the determinant of $A_n$ is log-normal. This was originally stated by Girko in 1997, but Girko's proof is opaque and seems to skirt some technical details. More transparent proofs were later given by Nguyen and Vu, and by Bao, Pan, and Zhou.

$\endgroup$
1
  • $\begingroup$ I appreciate you nice input. $\endgroup$
    – Lewi_Sol
    Commented Jun 2, 2017 at 22:16

You must log in to answer this question.

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