Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Setup: Consider a Laplacian (or Kirchoff) matrix $L = L^T \in \mathbb{R}^{n \times n}$ corresponding to a weighted, undirected and connected graph. That is, a matrix with $L_{ij} \leq 0$ for $i\neq j$ and $L_{ii} = -\sum_{j=1}^n L_{ij} > 0$. So $L$ has zero row sum, and is positive semidefinite with a simple eigenvalue at $0$.

It's well known that if you add a small positive (resp. negative) amount to any diagonal element of $L$, the zero eigenvalue is pushed into the right (resp. left) half plane.

Question: Consider a diagonal but indefinite matrix $B = \mathrm{diag}(b_{11},\ldots,b_{nn})$. What are sufficient conditions on $B$ such that $L + B$ is positive definite?

What I know: Obviously if $B$ was positive semi-definite the result would follow. I've found cases where a small negative $b_{ii}$ cannot be compensated for by a sufficiently large $b_{jj}$, so a condition of the form $Trace(B) >\!\!> 0$ won't work.

A Guess: Any negative element added at node $i$ must be corrected for with a positive addition at a (or several) nodes which are "sufficiently connected" in the graph to node i.

Thoughts appreciated! -John

share|cite|improve this question

Some remarks, too long for a comment. The set of matrices $B$ such that $L+B$ is positive semidefinite is a closed convex set (if $L+B_1$ and $L+B_2$ are positive semidefinite, then so is $L+aB_1+(1-a)B_2$ for $0\le a\le1$).

Also if $B$ is diagonal and $\mathrm{tr}(B)\ge0$ then, if my understanding of perturbation theory is correct, for sufficiently small but positive values of $\epsilon$ the matrices $L+\epsilon B$ are positive semidefinite. What matters here is that 0 is a simple eigenvalue and the corresponding eigenspace consists of the constant vectors, the fact that the off-diagonal entries of $L$ are non-positive is not needed.

My feeling (for what it's worth) is that it will be very difficult to turn your "guess" into a precise statement.

share|cite|improve this answer
Thanks for the reply Chris. My guess is just a guess -- I'm of course very open to any other answers :). I think a perturbation type answer could be a good starting place. Stewart and Sun is the classic reference I believe. Another possible idea for sufficient conditions: some smart Lyapunov argument? – John Dec 31 '12 at 18:42
@John: I just got Stewart and SUn from the library; it is not what you need. Your best bet would be Chapter 11 of Lancaster and Tismenetsky. After that you're off to Kato :-( – Chris Godsil Jan 8 '13 at 19:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.