4
$\begingroup$

Setup: Let $D = D^T > 0$ be a positive definite and diagonal $n\times n$ matrix, and let $A = A^T \in \mathbb{R}^{n\times n}$ be nonnegative with zero diagonals. That is, $a_{ij} \geq 0$ for $i\neq j$ and $a_{ii} = 0$. In my particular case, $A$ is an adjacency matrix of an undirected graph.

Question: Give necessary and sufficient conditions under which $D - A$ positive definite. Failing that, what's a necessary condition so I can understand the possible gap between necessity and sufficiency.

Partial Answer: A sufficient, but I believe not necessary, condition is that $\min_i D_{ii} > \rho(A) = \lambda_{\rm max}(A)$, where the last equality follows from the Perron theorem.

From the Disc Theorem, another sufficient condition is that $D_{ii} \geq \sum_{j=1}^n a_{ij}$ with strict inequality in at least one row.

Happy Thinking, -John

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps the answer is just that $D-A$ must be an $M$-Matrix? $\endgroup$
    – John
    Jul 16, 2014 at 3:01

1 Answer 1

0
$\begingroup$

Your guess is correct. A Z-matrix (matrix with non-positive off-diagonal elements) is an M-matrix, e.g., iff all its real eigenvalues are positive (see, e.g., Theorem 2.5.3 (2.5.3.3) in the book by Horn and Johnson). Since your $D-A$ is a symmetric Z-matrix (and has all eigenvalues are real), this is equivalent to the condition that $D-A$ is positive definite.

Therefore, to characterise the positive definiteness of $D-A$, you can choose any condition from the whole ZOO of equivalent conditions for M-matrices (adapted possibly for the symmetric case); see, e.g., the same theorem in the above linked book.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .