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?

  • 2
    $\begingroup$ Gerschgorin's theorem could actually help you here. Do you want to post a numerical example so that we can try various things against it? $\endgroup$ – Felix Goldberg Nov 6 '12 at 12:12
  • $\begingroup$ In the literature, such matrices (without the sparseness requirement) are referred to as $L$-matrices. If they are diagonally dominant, they are referred to as $M$-matrices. Many things are known about such matrices, so those keywords may help. $\endgroup$ – David Ketcheson Nov 9 '12 at 12:10

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks very much for the helpful comments. I wonder if there's anything even better? $\endgroup$ – equest Nov 8 '12 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.