Diagonal elements of a symmetric matrix and positive definiteness

Let $A = (a_{ij}) \in \mathbb{R}^{n \times n}$ be a symmetric matrix with $$a_{ii}>\sum\limits_{j\neq i} |a_{ij}|$$ for $i=1,\dots,n$. Show that $A$ is positive definite.

I tried to work this out algebraically starting from the definition of a real matrix being positive definite $x^{T}Ax > 0$ for every $x \in \mathbb{K}^{n}$ but this got me stuck in the sense that I couldn't really utilize the given precondition. I would appreciate some hints.

As mentioned, if a matrix is strictly diagonally dominant, then it is invertible: see here.

Lemma.

Let $A = (a_{ij}) \in \mathbb{R}^{n\times n}$ be a symmetric diagonally dominant matrix with $a_{ii} \ge 0$ for all $i = 1, \ldots, n$.

Then $\det A \ge 0$.

Proof.

Let $D = \operatorname{diag}(a_{11}, \ldots, a_{nn})$. For $t\in [0,1]$ consider the path $M(t) = (1-t)(D+I) + tA$.

Note that $M(t)$ is strictly diagonally dominant for $t < 1$:

$$\sum_{j\ne i} t|a_{ij}| \le ta_{ii} < a_{ii} + (1-t) = (1-t)a_{ii} + ta_{ii}$$

In particular, $\det M(t) \ne 0$ for all $t \in[0,1\rangle$. Since $\det (D + I) = \prod_{i=1}^n(a_{ii}+1) > 0$, by continuity of the determinant it must be $\det A = \det M(1) \ge 0$.

Now with your assumptions, notice that every principal minor of your matrix $A$ is a symmetric diagonally dominant matrix with nonnegative diagonal entries, so by the lemma it has determinant $\ge 0$. Sylvester's criterion implies that $A$ is positive semidefinite.

Furthermore, $A$ is strictly diagonally dominant so it is also invertible.

Positive semidefinite matrix which is invertible is in fact positive definite:

To see this, let $A^{1/2}$ be the unique positive semidefinite square root of $A$. If $A$ is invertible, then so is $A^{1/2}$ because $\det A = (\det A^{1/2})^2$.

We have $\langle Ax,x\rangle = \langle A^{1/2}x, A^{1/2}x\rangle = \|A^{1/2}x\|^2$.

Thus if $\langle Ax,x\rangle = 0$ then $A^{1/2}x = 0$ so $x = 0$. Therefore, $A$ is positive definite.

• I appreciate your efforts and gave you a thumb up. However this is a homework question and we didn't even introduce defintions like symmetric diagonally dominant, Sylvesters criterion and some other terms you used. However I managed to solve it with ideas from the Greshorgin circle theorem wiki-page that was suggested in the comments. Thanks alot for taking the time though:-) – Christian Singer Jun 2 '18 at 14:11
• @ChristianSinger Diagonally dominant just means $\left|a_{ii}\right|\ge \sum\limits_{j\neq i} |a_{ij}|$ for all $i = 1, \ldots, n$. Strictly diagonally dominant means $\left|a_{ii}\right|>\sum\limits_{j\neq i} |a_{ij}|$ for all $i = 1, \ldots, n$. But yes, Sylvester's criterion isn't really elementary though. – mechanodroid Jun 2 '18 at 14:19

HINT:

Add all the inequalities; $$|a_{ij}| x_{i}^2 + |a_{ij}| x_{j}^2+ 2 a_{ij} x_i x_j\ge 0$$ for all $i< j$, and get $$\sum_{i=1}^n s_i x^2_i + \sum_{i<j} 2 a_{ij} x_i x_j\ge 0$$ where $$s_i = \sum_{j\ne i} |a_{ij}|$$ Now use $a_{ii}> s_i$ for all $i$.

• The particular case $n=2$ is the one that gets everything – Orest Bucicovschi Jun 2 '18 at 14:55