Random matrix is positive

Question

This is a follow up question on my previous question here that was on solved in the deterministic setting by Denis Serre, when the perturbation can be separated. Therefore, I decided to split the deterministic case from the random question initially posed in the very same question. So let me state the random case:

We consider a symmetric matrix $A \in \mathbb R^{n \times n}$ defined by

$$A_{ij}= i \delta_{ij} - X_{ij}\varepsilon \,.$$

Here $\delta_{ij}$ is the Kronecker delta and $X_{ij}$ are iid Bernoulli (but of course $X_{ij}=X_{ji}$ to make it hermitian).

We first note that this matrix is not diagonally dominant if the matrix dimension $n$ is large enough, independent of what $\varepsilon$ is.

This is because $\lim_{n \rightarrow \infty} \sum_{i=1}^{n} \vert A_{i,1}\vert=\infty >\vert A_{1,1} \vert.$

Numerical experiments with matrix size $n=50$ or $n=200$ show that the lowest eigenvalue stays far above $0$, if $\varepsilon>0$ is sufficiently small.

Question: How can one show that $A$ is positive definite independent of the dimension if $\varepsilon$ is sufficiently small but fixed ?

To elaborate on the numerical experiments. We find that the lowest eigenvalue of $A$ in some interval $[0,96,1.08]$ if we choose $\varepsilon=0.1$ and $n=50$(upper plot) and $n=200$(lower plot), as I illustrate in the following plot where I sampled the lowest eigenvalue for 100 realizations:

Please let me know if you have any questions!

Answer 1

Let $u\in \mathbb{R}^n$ as $u_i=i^{-1}$. Then $$ \mathbb{E}\big[\langle u Au\rangle \big]=\sum_{i=1}^n i^{-1}-\frac{\epsilon}{2}\sum_{i,j\leq n}\frac{1}{ij}\approx \log n -\frac{\epsilon}{2}(\log n)² $$ Which is stricly negative for $\log n > 2\epsilon^{-1}$. (Remark : In order to see it numerically one should choose $n$ exponentially large with $\epsilon^{-1}$.)

Answer 2

You can find other counter-examples along the vein of $v\in \mathbb{R}^n$ $v_i=i^a$ for certain $a$, making sure that the sum of the negative terms outweighs that of the positive components of the diagonal elements. Also, a matrix may have all positive eigenvalues yet not be positive definite; see <https://math.stackexchange.com/questions/4336/if-eigenvalues-are-positive-is-the-matrix-positive-definite>.