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?

$\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$ 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$ Nov 9, 2012 at 12:10

1 Answer 1

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.

$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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