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.

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

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}$.

  • $\begingroup$ 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)$. $\endgroup$ – loup blanc Jan 9 '18 at 23:04

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.