Question

Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them exactly 0 (so sparse)? We have upper bounds on the magnitudes of all nonzero entries. We do not know whether the main diagonal terms are more or less than minus the off-diagonal nonzero terms.

Zhan's "Extremal eigenvalues of real symmetric matrices with entries in an interval" (SIAM J. Matrix Anal. Appl. Vol. 27, No. 3, pp. 851-860) provides an answer for general n*n real symmetric matrices but can we improve/simplify this given the extra conditions?

Answer 1

Probably, the following elementary argument using sparseness will help. Assume that $|A_{i,j}|\le c$. Let $\tau\in[0,1]$ be a proportion of non-zero entries among all entries in matrix, so that there are exactly $\tau n^2$ non-zero entries. Then

$ \max_{k}{|\lambda_k|} \le \sqrt{\mathrm{tr}(A^*A)}= \sqrt{\sum_{i,j=1}^{n}{|A_{i,j}|^2}} \le \sqrt{\tau n^2 c^2} = \sqrt{\tau}n c. $

For $\tau$ small this beats Zhan's estimate, which is roughly $nc$ in this context.

Gershgorin theorem is good for matrices with small off-diagonal elements.