14
$\begingroup$

I try to find a good proof for invertibility of strictly diagonally dominant matrices (defined by $|m_{ii}|>\sum_{j\ne i}|m_{ij}|$). There is a proof of this in this paper but I'm wondering whether there are are better proof such as using determinant, etc to show that the matrix is non singular.

$\endgroup$
  • 1
    $\begingroup$ Use Gershgorin's theorem. Wiki has the proof. $\endgroup$ – TZakrevskiy Jul 31 '13 at 21:15
  • $\begingroup$ The above can be generalized to the larger class of weakly chained diagonally dominant matrices. For an elementary proof of the nonsingularity, also using Gershgorin's theorem, see arxiv.org/pdf/1510.03928v2.pdf Definition 3.1 and Lemma 3.2 on page 5. Note that nonsingularity is not necessarily true for weakly diagonally dominant matrices (a simple counterexample is $\left(\begin{array}{cc} +1 & -1\\ -1 & +1 \end{array}\right)$) $\endgroup$ – parsiad Sep 2 '16 at 19:42
21
$\begingroup$

The proof in the PDF (Theorem 1.1) is very elementary. The crux of the argument is that if $M$ is strictly diagonally dominant and singular, then there exists a vector $u \neq 0$ with $$Mu = 0.$$

$u$ has some entry $u_i > 0$ of largest magnitude. Then

\begin{align*} \sum_j m_{ij} u_j &= 0\\ m_{ii} u_i &= -\sum_{j\neq i} m_{ij}u_j\\ m_{ii} &= -\sum_{j\neq i} \frac{u_j}{u_i}m_{ij}\\ |m_{ii}| &\leq \sum_{j\neq i} \left|\frac{u_j}{u_i}m_{ij}\right|\\ |m_{ii}| &\leq \sum_{j\neq i} |m_{ij}|, \end{align*} a contradiction.

I'm skeptical you will find a significantly more elementary proof. Incidentally, though, the Gershgorin circle theorem (also described in your PDF) is very beautiful and gives geometric intuition for why no eigenvalue can be zero.

$\endgroup$
2
$\begingroup$

I would probe it a bit tangentially. And not because it will be simpler, but because it gives an excuse to show an application. I would take an iterative method, like Jacobi's, and show that it converges in this case; and that it converges to a unique solution. This, incidentally implies the matrix is non-singular.

How does it work exactly?

For the system $Ax=b$, Jacobi's method consists in writing $A=D+R$, where $D$ is diagonal and $R$ has zeros in the diagonal. Then you define the recurrence

$$x_{n+1}=D^{-1}(b-Rx_{n}).$$

Now we can show that it converges.

We have

\begin{align}||x_m-x_n||&=||\sum_{k=n}^{m}(D^{-1}R)^kb-((D^{-1}R)^{m}-(D^{-1}R)^{n})x_0||\\ &\leq\sum_{k=n}^{m}||D^{-1}R||^k||b||+\left(||D^{-1}R||^m+||D^{-1}R||^n\right)||x_0|| \end{align}

For the norm $||\cdot||:=||\cdot||_{\infty}$, the matrix norm is bounded by the maximum of the sums of the absolute values of its entries in each row. Therefore $$||D^{-1}R||$$ is less than some number less than $1$. For this reason the sum above can be as small as you want for $n,m$ large. This shows the convergence of the sequence.

If it clear too that it has to converge to any solution of the system $Ax=b$. To see this we use the same argument above but placing a solution $x$ in place of $x_m$. We use that $Ax=b$, i.e. $x=D^{-1}(b-Rx)$ and we get it. So $x_n$ converges to any solution. Since it is a convergent sequence it converges to only one thing so there is only one solution to the system.

$\endgroup$
  • 1
    $\begingroup$ Nice reversion of the usual teaching order :-) However, $\|D^{-1}\|$ seems not necessarily $<1$ to me (should not be required anyway), and I do not see the uniqueness from the mere convergence yet. $\endgroup$ – ccorn Jul 31 '13 at 21:31
  • $\begingroup$ Oh, true. Let me correct it. $\endgroup$ – OR. Jul 31 '13 at 21:35
  • 2
    $\begingroup$ The fact that every such sequence converges does not imply that all the sequences have the same limit. However, it would be sufficient to show that given any particular solution $x^*$, starting with any distance from that $x^*$ decreases that distance by a factor strictly less than $1$. $\endgroup$ – ccorn Jul 31 '13 at 22:06
  • 1
    $\begingroup$ Yes, I am, if not saying, trying to say what you just said. When you put that $x^{*}$ instead of $x_m$ in the inequalities above, that is what you prove: That $x_n\rightarrow x^{*}$. Therefore it happens for any solution $x^{*}$ the system may have. Since the sequence converges and the limit is unique then there is a unique $x^{*}$. $\endgroup$ – OR. Jul 31 '13 at 22:08
  • 1
    $\begingroup$ So it could be cleaned up to: $x_{n+1}-x^* = -D^{-1}R(x_n-x^*)$. No $\sum$ required. Then the norm estimate, and you are done. $\endgroup$ – ccorn Jul 31 '13 at 22:21

protected by Zev Chonoles Sep 12 '16 at 18:44

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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