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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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