9
$\begingroup$

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.

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

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
1
  • $\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$
    – user91684
    Jan 9, 2018 at 23:04

You must log in to answer this question.

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