Sum of Nonnegative Matrix and Diagonal Matrix

Question

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

Answer 1

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.