2
$\begingroup$

I have been given the following exercise

Use the Gerschgorin cirlce theorem to find an upper bound for the spectral condition of a matrix $A$ which is real, symmetric and diagonally dominant.

I guess we can also assume, that $A$ is invertible, because we defined the spectral condition only for invertible matrices.

I tried the following: $$ \kappa_2(A) \overset{\text{def.}}{=} \Vert A \Vert_2 \Vert A^{-1} \Vert_2 = \varrho(A)\varrho(A^{-1}) $$ where $\varrho(M)$ is the spectral radius of $M$.

There is an easy way to bound $\varrho(A)$: Using Gerschgorin and the diagonal dominance we get $$ \vert \lambda - a_{jj} \vert \leq \sum_{l \neq j} a_{jl} \leq \vert a_{jj} \vert\\ \Rightarrow \vert \lambda - a_{jj} \vert + \vert a_{jj} \vert \leq 2\vert a_{jj} \vert $$ and by the triangle inequality $$ \vert \lambda \vert \leq \vert \lambda - a_{jj} \vert + \vert a_{jj} \vert \leq 2\vert a_{jj} \vert $$ then we choose $\vert a_{jj} \vert$ maximal and so got $\varrho(A)$ bounded.

But bounding $\varrho(A^{-1})$ is rather difficult: I wanted to use $\varrho(A^{-1}) = 1/\min( \vert \text{eig}(A) \vert)$, but I have not found a way to lower bound $\min( \vert \text{eig}(A) \vert)$, which also seems intuitively impossible to me; Just imagine the circles we get by using the inequality which we derived by using the diagonal dominance $$ \vert \lambda - a_{jj} \vert \leq \vert a_{jj} \vert $$ all of thous circles include the origin. I guess you see my problem.

I could lower bound $\min( \vert \text{eig}(A) \vert$ by not using the diagonal dominance, but I guess this would just ruin the whole point of this exercise.

Maybe I am overlooking something, or maybe there is an entirely different method.

Thanks for your help!

$\endgroup$
9
  • $\begingroup$ I used the triangle inequality correctly (at least as far as I can tell), I use some precision by that step, but I honestly do not care that much. My problem is mostly to find any bound for $\varrho(A^{-1})$. $\endgroup$
    – Dominik
    Jan 23, 2020 at 18:22
  • $\begingroup$ Sorry, you are right. But this "use of some precision" loses you the non-zero lower bound. There are generalizations of the circle theorem that give stricter bounds, but with non-linear inequalities. For practical purposes one would reduce the matrix to tridiagonal form first or even apply some rounds of the QR algorithm to get smaller radii around the diagonal entries. $\endgroup$ Jan 23, 2020 at 19:24
  • $\begingroup$ @LutzLehmann sorry, the "use of some precision" is a typo and should be "loose of some precision" $\endgroup$
    – Dominik
    Jan 23, 2020 at 19:30
  • $\begingroup$ It does not change the meaning, in the lower bound this loss of precision is exactly the distance to zero, you need the strictness of the diagonal dominance to bound the eigenvalues away from zero. $\endgroup$ Jan 23, 2020 at 19:35
  • 1
    $\begingroup$ See the denominator in the last formula of the answer. With your kind of simplification the denominator becomes zero. $\endgroup$ Jan 23, 2020 at 20:14

1 Answer 1

2
$\begingroup$

By Gerschgorin disc theorem, every eigenvalue of $A$ lies inside the union of the open Gerschgorin discs $\cup_{i=1}^n B(a_{ii},\sum_{j\ne i}|a_{ij}|)$. Since the $A$ in question is symmetric and diagonally dominant (I suppose the question means that $A$ is strictly diagonally dominant, otherwise the condition number of $A$ may not exist, such as when $A=0$), we have either $$ 0<a_{ii}-\sum_{j\ne i}|a_{ij}|\le\lambda\le a_{ii}+\sum_{j\ne i}|a_{ij}| $$ or $$ a_{ii}-\sum_{j\ne i}|a_{ij}|\le\lambda\le a_{ii}+\sum_{j\ne i}|a_{ij}|<0 $$ for every eigenvalue $\lambda$ of $A$ in the disc (say, the $i$-th one) it belongs to. It follows that $$ 0<|a_{ii}|-\sum_{j\ne i}|a_{ij}|\le|\lambda|\le |a_{ii}|+\sum_{j\ne i}|a_{ij}| $$ in the disc that $\lambda$ belongs to. Consequently, $$ \kappa_2(A)=\frac{|\lambda|_\max(A)}{|\lambda|_\min(A)}\le\frac{ \max_i\left\{|a_{ii}|+\sum_{j\ne i}|a_{ij}|\right\}, }{ \min_i\left\{|a_{ii}|-\sum_{j\ne i}|a_{ij}|\right\} }. $$

$\endgroup$
2
  • $\begingroup$ @user1551 you divide by $\lambda_\max (A)$, should it not be $\min(\vert \lambda \vert)$? The smallest eigenvalue does not have to be the absolut smallest eigenvalue. $\endgroup$
    – Dominik
    Jan 23, 2020 at 19:47
  • $\begingroup$ @Dominik You are right. It's fixed now. $\endgroup$
    – user1551
    Jan 23, 2020 at 20:04

You must log in to answer this question.

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