7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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, 2012 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, 2012 at 12:10

1 Answer 1

Reset to default
6
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .