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.

$\endgroup$
  • 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 Jun 1 '18 at 16:17
  • $\begingroup$ The values of the $A_{ij}$ are independently chosen, aren't they? $\endgroup$ – Pietro Majer Jun 1 '18 at 17:19
  • $\begingroup$ @Pietro Majer Yes, they are independently identically distributed $\endgroup$ – Hipstpaka Jun 1 '18 at 17:34
  • 7
    $\begingroup$ $\mathbb{E}$ or $P$? $\endgroup$ – Mahdi Jun 1 '18 at 19:18
  • $\begingroup$ The answer to this question mathoverflow.net/questions/292795/… may be helpful. $\endgroup$ – Benjamin Steinberg Jun 1 '18 at 20:05
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.

$\endgroup$
  • 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 Jun 4 '18 at 10:38
  • $\begingroup$ @user100927 Yes, that's probably correct. $\endgroup$ – Igor Rivin Jun 4 '18 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$$

$\endgroup$
  • 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 Jun 2 '18 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 Jun 2 '18 at 16:12
  • $\begingroup$ Well .. this answer the question as it is stated.. I think the OP should modify his/her question $\endgroup$ – lcv Jun 2 '18 at 21:51
  • $\begingroup$ I modified the question correspondingly. $\endgroup$ – Hipstpaka Jun 3 '18 at 10:40

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.