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

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

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


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.