1
$\begingroup$

There is a well-known criterion to check whether a matrix is positive definite which asks to check that a matrix $A$ is

a) hermitian

b) has only positive diagonal entries and

c) is diagonally dominant.

This is a sufficient condition to ensure that $A$ is hermitian.

A classical counterexample where this criterion fails is the matrix

$$\left(\begin{matrix} 0.1 & 0.2 \\ 0.2 & 10 \end{matrix} \right).$$

This matrix is positive definite but does not satisfy the diagonal dominance.

I think this matrix illustrates well the issue with the diagonal dominance: It does not take into account if you have a rapidly growing diagonal elements that overshadow the failure of the diagonal dominance in each row.

I am therefore looking for a criterion to ensure that a matrix is positive definite that asks for a matrix $A$ to be

a) hermitian

b) has only positive diagonal entries and

c) its diagonal grows sufficiently fast compared to all off-diagonal elements. We might want to assume some sparsity as well on our matrix. So ideally instead of investigating a single row, this improved criterion I would have in mind checks let's say an individual row but instead of comparing the row sum with its single diagonal entry, also takes other diagonal elements into account.

PS: Of course you might say that Sylvester's criterion takes care of this, but this criterion is far too cumbersome for sufficiently sparse matrices, I find. Just like the diagonal dominance is really apparent.

EDIT: I found the so-called Brauer's ovals of Cassini which seem to generalize the notion of Gershgorin circles used to prove the diagonally dominance criterion. This allows me already to take into account pairs of two diagonal entries. Can this be generalized to arbitrarily many entries?

See for background.

Please let me know if you have questions.

$\endgroup$
1
  • $\begingroup$ This is very much loosely related to your question (in that it doesn't require the Hermitian part ... or the strict diagonal dominance ... actually it is not that related), but the underlying idea in the Hawkins-Simon condition might be somewhat helpful to some specific problems you might consider. See en.wikipedia.org/wiki/Hawkins%E2%80%93Simon_condition. $\endgroup$ – JCM Jan 13 '20 at 18:49
5
$\begingroup$

If you have a matrix with a rapidly growing diagonal, you can check alternatively if $DAD$ is diagonally dominant with a positive diagonal, where $D= \operatorname{diag}(1,\rho, \rho^2, \dots, \rho^{n-1})$, for a suitably chosen $\rho$. If that is the case, then $DAD$ is positive definite, and since positive definiteness is preserved by congruence, so $A$ (note that $D^T=D$). In your case, for instance $\rho=1/\sqrt{10}$ works.

$\endgroup$
1
  • $\begingroup$ that's a nice idea, thank you. $\endgroup$ – Xin Wang Jan 13 '20 at 11:28

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.