Probabilidad de que una matriz binaria aleatoria sea semidefinida positiva

Question

Dejemos que $A$ sea un azaroso $n \times n$ matriz tal que $A_{ij}\in\{0,1\}$ . Supongamos que cada elemento $A_{ij}$ es igual a 1 con cierta probabilidad $p>0$ y que todas las extracciones son independientes entre los elementos. ¿Cuál es la probabilidad de que la parte simétrica de $A$ la matriz $\frac{1}{2}(A+A^T)$ ¿es semidefinido positivo?

Cualquier resultado relacionado con que la parte simétrica sea definida positiva también sería bienvenido.

Answer 1

Denote la probabilidad de que $S$ es semidefinido positivo por $q_n$ (por ejemplo $q_2=\frac7{16}$ cuando $p=\frac12$ ). Si $S=(A+A^T)/2$ es semidefinido positivo, cada uno de sus $2\times2$ Los sub-bloques diagonales deben ser también semidefinidos positivos. Por lo tanto, cuando $n\ge2$ tenemos $q_n\le q_2^{\lfloor n/2\rfloor}$ que se aproxima a cero cuando $0<p<1$ y $n\to+\infty$ .

La probabilidad de que $S$ es positivo definitivo disminuye aún más rápido. Como todas las entradas diagonales de $A$ debe ser igual a $1$ y ninguna entrada fuera de diagonal de $S$ puede ser igual a $1$ la probabilidad está acotada por encima de $p^n(1-p^2)^{n(n-1)/2}$ .