First eigenvalue of Laplacian Matrix greater than zero

Question

Can I make the first eigenvalue of a weighted Laplacian matrix $L$ greater than zero by adding a matrix $E=\operatorname{diag}[1,0 \dots 0]$?

I mean, how can I prove that

$$\lambda_0(L+E)>0\text{ ?}$$

By simulation, it seems to be true.

Thanks.

Answer 1

If the associated graph is not connected, there are easy counterexamples (take $4$ vertices, the first and second connected by a single edge, the third and fourth connected by another; then $v = (0,0,1,1)^T$ is in the kernel of both $L$ and $L + E$). So let's assume the graph is connected.

If $0$ is an eigenvalue of $L + E$, that means there is a vector $v\neq 0$ such that

$$(L + E)v = Lv + (v_1,0,\dots,0)^T = 0$$

so $Lv = (-v_1,0,\dots,0)^T$.

Now, we have $(\textrm{Im}T)^\perp = \textrm{Ker}T^*$ for every linear operator $T$. Since $L = L^*$, we have $(\textrm{Im}L)^\perp = \textrm{Ker}L$. We know $\textrm{Ker}L = \textrm{span}(1,1,\dots,1)^T$ (this is where we use connectedness), this tells us that $\textrm{Im}L$ consists of vectors whose entries sum to zero. Thus in writing $Lv = (-v_1,0,\dots,0)^T$ above, we must have $v_1 = 0$, and so actually $Lv = 0$. But as we have just noted $\textrm{Ker}L = \textrm{span}(1,1,\dots,1)^T$, so $v = 0$ and we have a contradiction.

There's probably a cleaner way to observe all this, but that should get you started. To show that this eigenvalue must be positive, note that

$$ v^T(L + E)v = v^TLv + v^TEv = v^TLv + v_1^2 \geq v^TLv \geq 0 $$

so $L + E$ is positive semi-definite (and since you know $\lambda = 0$ is not an eigenvalue, you can conclude it is actually positive definite).