5
$\begingroup$

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

1 Answers 1

2

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.

  • 0
    @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 :-(2013-01-08