Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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? –  Felix Goldberg Nov 6 '12 at 12:12
    
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. –  David Ketcheson Nov 9 '12 at 12:10
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks very much for the helpful comments. I wonder if there's anything even better? –  equest Nov 8 '12 at 16:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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