Consider an $n \times n$ symmetric positive definite matrix that has the following properties
- All of its elements are nonnegative
- It has 1's along its main diagonal
- There is an upperbound $0<r<1$ on all of its off-diagonal elements.
Is there a way to lower bound the minimum eigenvalue of this matrix in terms of $r$?
The obvious thing to try is to "raise" all the off-diagonal elements up to $r$, but I could not prove that the resulting matrix would have a smaller minimum eigenvalue than the original matrix.
Any help would be appreciated.
If $r$ is sufficiently, small, then the following argument can be made using either the Gershgorin circle theorem or the $\infty$-norm. In either case, we obtain the same bound. One argument is as follows:
Let $M = A - I$. We note that $$ \|M\|_\infty = \max_{1 \leq i \leq m} \sum_{j=1}^n |m_{ij}| \leq (n-1)r $$ Thus, if we have $r < n-1$, then we have the bound $$ \lambda_{min}(A) = \lambda_{min}(I + M) = \min\{1 + \lambda_i(M): i = 1,\dots,n\} \geq 1 - \|M\|_\infty = 1 - (n-1)r $$ When $r \geq n-1$, this bound tells us nothing useful.