Probability that a random binary matrix is positive semi-definite

Let $A$ be a random $n \times n$ matrix such that $A_{ij}\in\{0,1\}$. Assume that each element $A_{ij}$ equals 1 with some probability $p>0$ and that all the draws are independent across elements. What is the probability that the symmetric part of $A$, the matrix $\frac{1}{2}(A+A^T)$, is positive semi-definite?

Any results pertaining to the symmetric part being positive definite would also be welcome.

• Do you mean $(1/2)(A+A^t)$?
– Mark
Jan 2, 2018 at 21:40
• Oops, yeah thanks. Fixed. Jan 2, 2018 at 21:40

1 Answer

Denote the probability that $S$ is positive semidefinite by $q_n$ (e.g. $q_2=\frac7{16}$ when $p=\frac12$). If $S=(A+A^T)/2$ is positive semidefinite, each of its $2\times2$ diagonal sub-blocks must be positive semidefinite too. Therefore, when $n\ge2$, we have $q_n\le q_2^{\lfloor n/2\rfloor}$, which approaches zero when $0<p<1$ and $n\to+\infty$.

The probability that $S$ is positive definite diminishes even quicker. Since all diagonal entries of $A$ must be equal to $1$ and no off-diagonal entries of $S$ can be equal to $1$, the probability is bounded above by $p^n(1-p^2)^{n(n-1)/2}$.

• If $r_n=Prob(S>0)$, then $-\log(r_n)\geq \Omega(n^2)$. What would be interesting is to see if one also have $-\log(q_n)\geq \Omega(n^2)$.
– user91684
Jan 9, 2018 at 23:04