2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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:-) $\endgroup$ – Christian Singer Jun 2 '18 at 14:11
  • 1
    $\begingroup$ @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. $\endgroup$ – mechanodroid Jun 2 '18 at 14:19
0
$\begingroup$

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$.

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

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.