# Proof that a strictly diagonally dominant matrix is invertible

Let $$A$$ be a strictly diagonally dominant matrix of dimensions $$n \times n$$. ("Strictly diagonally dominant" means that $$\left|a_{i,i}\right| > \sum\limits_{j \neq i} \left|a_{i,j}\right|$$ for all $$i \in \left\{1,2,\ldots,n\right\}$$, where $$a_{u,v}$$ denotes the $$\left(u,v\right)$$-th entry of $$A$$.)

Prove that $$A$$ is invertible.

My attempt builds on the proof of Gershgorin's circle theorem, given in the Wikipedia article https://en.wikipedia.org/wiki/Gershgorin_circle_theorem

Let $$\lambda$$ be an eigenvalue of $$A$$, and scale its corresponding eigenvector $$x$$ so that $$x_{i} = 1$$ and $$|x_{j}| \leq 1$$ for $$j \neq i$$

Then $$Ax = \lambda x$$, and in particular $$\sum_{i\neq j}a_{i,j}x_{j} = \lambda - a_{ii}$$ (1)

Now because $$A$$ is strictly diagonally dominant it holds for every $$i$$ that,

$$\sum_{j \neq i}|a_{i,j}| < |a_{i,i}|$$ and since $$|x_{i}| \leq 1$$ the following should hold:

$$\sum_{i\neq j}|a_{i,j}x_{j}| \leq \sum_{j \neq i}|a_{i,j}| < |a_{i,i}|$$

But here I get stuck, feel like I want to use (1) in some way to complete the proof and put $$\lambda = 0$$ to get a contradiction, thus proving that if $$A$$ is strictly diagonally dominant, it has non-zero eigenvalues which should imply invertibility.. Am I in the right direction?

• Note that you have proved that $$|\lambda-a_{i,i}|\leq \sum_{j\not =i}|a_{i,j}|<|a_{i,i}|$$ – Kelenner Sep 8 '17 at 12:30
• The approach is fine (not sure about the details). The mentioned theorem and the triangle inequality should lead to the desired proof. – Peter Sep 8 '17 at 13:48

For an elementary proof, assume there exists a vector $$x \ne 0$$ such that $$Ax = 0$$. This implies $$\sum_{j=1}^n a_{ij}x_j = 0, \forall i \in \{1, \ldots, n\}$$. Let $$x_k = \|x\|_\infty \ne 0$$, i.e. $$x_k$$ is the the largest entry of $$x$$ by absolute value.

We have:

$$0 = \sum_{j=1}^n a_{kj}x_j \implies a_{kk}x_k = -\sum_{j\ne k} a_{kj}x_j \implies a_{kk} = -\sum_{j\ne k} a_{kj}\frac{x_j}{x_k}$$

By taking the absolute value we get:

$$|a_{kk}| = \left|\sum_{j\ne k} a_{kj}\frac{x_j}{x_k}\right| \leq \sum_{j\ne k} |a_{kj}|\underbrace{\left|\frac{x_j}{x_k}\right|}_{\leq 1} \leq \sum_{j\ne k} |a_{kj}|$$

This is a contradiction since $$A$$ is strictly diagonally dominant.

This means that $$0\notin \sigma(A)$$, hence $$A$$ is invertible.