Linear Algebra – Symmetric Matrix is Positive Semidefinite

eigenvalues-eigenvectorslinear algebranumerical linear algebrapositive-semidefiniteupper-lower-bounds

Let $A=(a_{ij}) \in M_n(\mathbb R)$ be a symmetric matrix such that:

  1. $a_{ij} \in \mathbb Q, \quad \forall i,j=1,…,n$
  2. $a_{ii} = 1$,
  3. $0 \leq a_{ij} \leq \frac{n-1}{n}, \quad i \neq j$.

I want to prove that such a matrix is positive semidefinite. It is well known that since $A$ is symmetric, this amounts to show that all eigenvalues of $A$ are non-negative. For that, one has to find a lower bound for the eigenvalues of $A$ that is greater or equal to zero. I tried using Gershgorin theorem, but the bound is not strong enough, the same happens with the one on this paper: https://www.math.uwaterloo.ca/~hwolkowi/henry/reports/bndseigs80.pdf

Does anyone one know stronger bounds on eigenvalues of matrices of this kind? Or to prove directly that this matrix is positive semidefinite?

Thanks in advance!

Best Answer

This is not true. Random counterexample: $$ A=\pmatrix{1&\frac34&0&\frac12\\ \frac34&1&\frac34&0\\ 0&\frac34&1&\frac12\\ \frac12&0&\frac12&1}. $$ $A$ isn’t positive semidefinite because $\det(A)=-\frac58<0$.

Related Question