Suppose $n \ge 2$ and we have an $n \times n$ Hermitian, positive semidefinite matrix with $1$ down the main diagonal, and all off-diagonal entries have modulus strictly less than $\frac{1}{n-1}$. Can we conclude that this matrix is invertible? Moreover, can this upper bound of $\frac{1}{n-1}$ be improved?
This is a question inspired by this question. I have a suspicion that this can be done with Gram matrices, but I don't have the skill with these matrices to figure it out.
Yes, this is true as a consequence of the Gershgorin circle theorem. Another approach that gives us the same result: we can note that if $\|\cdot\|_\infty$ denotes the induced $\infty$-norm, then $\|M - I\|_\infty < 1$ (since the matrices are Hermitian, it's also equivalent to use the induced $1$-norm)
A stronger sufficient condition is that (assuming the diagonal entries are still all $1$) the non-diagonal entries of each row must have absolute values with sum strictly less than $1$.