6
$\begingroup$

Suppose we have a matrix $A \in \{0,1\}^{n \times n}$ where

$$A_{ij} = \begin{cases} 1 & \text{with probability} \quad p\\ 0 &\text{with probability} \quad 1-p\end{cases}$$

I would like to know the probability

$$\mathbb P( \det (A) =0) \ \text{ for large }n,$$

i.e., the asymptotic probability of the determinant being zero as $n$ becomes large.

I know that the probability

$$\lim_{n \rightarrow \infty} \mathbb P \left( \det (A) =0 \right) = 0$$ if $p \neq 0,1$ but could not find results for finite $n$/the asymptotic behavior.

Edit: I changed the symbol $\mathbb{E}$ to $\mathbb{P}$ since I meant the probability and not the expectation value as some comments assumed correctly.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ For p far from 1/2, you can estimate or at least bound the probability by assuming a (near-) uniform draw from the pool of vectors with exactly floor(pn) ones. It then becomes a birthday problem. Gerhard "What Is Your Birthday Vector?" Paseman, 2018.06.01. $\endgroup$
    – Gerhard Paseman
    Commented Jun 1, 2018 at 16:17
  • $\begingroup$ The values of the $A_{ij}$ are independently chosen, aren't they? $\endgroup$
    – Pietro Majer
    Commented Jun 1, 2018 at 17:19
  • $\begingroup$ @Pietro Majer Yes, they are independently identically distributed $\endgroup$
    – Hipstpaka
    Commented Jun 1, 2018 at 17:34
  • 7
    $\begingroup$ $\mathbb{E}$ or $P$? $\endgroup$
    – Mahdi - Free Palestine
    Commented Jun 1, 2018 at 19:18
  • $\begingroup$ The answer to this question mathoverflow.net/questions/292795/… may be helpful. $\endgroup$
    – Benjamin Steinberg
    Commented Jun 1, 2018 at 20:05

2 Answers 2

Reset to default
4
$\begingroup$

A nice survey is given by Voigt and Ziegler (but they only address the $p=\frac12$ case explicitly).

Voigt, Thomas; Ziegler, Günter M., Singular 0/1-matrices, and the hyperplanes spanned by random 0/1-vectors, Comb. Probab. Comput. 15, No. 3, 463-471 (2006). ZBL1165.15018.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The natural generalization to $p\neq \frac{1}{2}$ would be that the probability is basically the probability of two columns being equal, i.e. $n^2(p^2+(1-p)^2)^n(1+o(1))$ $\endgroup$
    – user100927
    Commented Jun 4, 2018 at 10:38
  • $\begingroup$ @user100927 Yes, that's probably correct. $\endgroup$
    – Igor Rivin
    Commented Jun 4, 2018 at 20:07
2
$\begingroup$

NOTE: This answer was posted in response to an earlier version of the question that was about the expected value and not the probability. So it has now become irrelevant. I decided not to delete it because in a comment there is some useful general result provided. If moderators think the answer should be deleted, no problem.

It appears I am missing something here, but as long as I cannot find what I am missing:

"$\det$" is an operator on all the elements of a matrix that results in an expression that combines them by using addition, subtraction and multiplication. Then, due to the linearity of the expected value we have

$$\mathbb E[A_{ij} + A_{k\ell}] = \mathbb E[A_{ij}] + \mathbb E[A_{k\ell}] \tag{1}$$

Moreover, in the OP's case as explained in a comment, the elements of the matrix are i.i.d. random variables. Due to the statistical independence assumption we have

$$\mathbb E[A_{ij} A_{k\ell}] = \mathbb E[A_{ij}] \mathbb E[A_{k\ell}] \tag{2}$$

But in such a case we have

$$\mathbb E[\det(A)] = \det(\mathbb E[A]) \tag{3}$$

$\mathbb E(A)$ is a matrix with all elements identical and equal to $p$ (due to the "identically distributed" assumption).

Then $\det(\mathbb E[A]) = 0 = \mathbb E[\det(A)]$ for all $n$, and so

$$\Pr\{\mathbb E[\det(A)]=0\} = 1, n\geq 2$$

Improve this answer
$\endgroup$
4
  • 6
    $\begingroup$ The OP doesn't really want the expectation (despite the symbol in the question) but the probability that the determinant is zero. As a more concrete (and general) way to see the expectation is zero: given a matrix M, let M' be obtained by swapping the first and second columns. This implicit map is a bijection which (trivially) preserves measure in this model (and this is still true in more relaxed models) but swaps the sign of the determinant, so the expectation has to be zero. $\endgroup$
    – user36212
    Commented Jun 2, 2018 at 13:58
  • $\begingroup$ @user36212 Thanks for the clarification. So my answer is irrelevant. I will leave it though, since your comment contains some more input. $\endgroup$
    – Alecos Papadopoulos
    Commented Jun 2, 2018 at 16:12
  • $\begingroup$ Well .. this answer the question as it is stated.. I think the OP should modify his/her question $\endgroup$
    – lcv
    Commented Jun 2, 2018 at 21:51
  • $\begingroup$ I modified the question correspondingly. $\endgroup$
    – Hipstpaka
    Commented Jun 3, 2018 at 10:40

You must log in to answer this question.

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