In this previous question is stated that given a weighted undirected Laplacian corresponding to a connected graph $L$ it's well known that if you add a small positive (resp. negative) amount to any diagonal element of 𝐿, the zero eigenvalue is pushed into the right (resp. left) half plane.
I tried to find the result in the literature and even though I found quite a lot of paper on perturbed Laplacian matrices, I still did not find a way to prove the statement in italic above. The definition of perturbed Laplacian matrices is not related to 'typical perturbation theory' in case this creates any confusion. You can refer here for a definition of perturbed laplacian.
It is the property stated in the question general for any matrices with zero-sum rows? Is the property valid for any singular matrix? How would I in general approach such a problem? Also, does it hold for any positive value or it has to be sufficiently small?
Thank you!
———————- UPDATE ——————-
What happens if instead of $L$, we consider $L+\gamma I$ where $I$ is the identity matrix? How can I quantify the effect of perturbing just one diagonal entry? In case $\gamma=0$ (question above) it is enough to know that we can 'move' the $0$ eigenvalue to the left or to the right with minimal diagonal perturbation. But how we can quantify this effect?
Best Answer
Let us write $\mathbf{L}=\sum_k \lambda_k \mathbf{u}_k \mathbf{u}_k^T$. It follows $\lambda_i = \mathbf{u}_i^T \mathbf{L} \mathbf{u}_i$ and $d\lambda_i = \mathbf{u}_i\mathbf{u}_i^T:d\mathbf{L}$. The colon operator denotes the Fronebius inner product here.
The eigenvector associated to the zero eigenvalue is the vector of ones $\mathbf{e}$, i.e. $\mathbf{Le}=0\cdot \mathbf{e}$
For this particular eigenvalue $d\lambda_0 = \mathbf{J}:d\mathbf{L}$ where $\mathbf{J}=\mathbf{e}\mathbf{e}^T$ is populated with ones.
If you perturb one element of the diagonal of $\mathbf{L}$ by $h$, we can conclude $d\lambda_0 = h$ Thus if $h>0$, the (zero) eigenvalue will increase.