Eigenvalues of the sum of Laplacian matrix and the all ones matrix

Question

Given an undirected graph and its Laplacian is $L$. I need to find the eigenvalues of the sum: $L + \mathbf{11^T}$ (where $\mathbf{1}$ is the all-ones vector, which means that $\mathbf{11^T}$ is a matrix constructed only by ones).

I know that 0 is no more an eigenvalue, and its "replacement" is $n$ (where $L$ is of size $n \times n$. The reason is that the sum of the rows of the new matrix is $n$). Using matlab I found that the other eigenvalues don't change, but I can't find a way to prove it.

Thanks,

JayJay

Answer 1

The $0$ eigenspace of $J$ (the usual name for the matrix of all ones) is orthogonal to the non-zero eigenspace. In particular, every nontrivial eigenvector of $L$ is also an eigenvector of $J.$ So, $(L+J)v = Lv + Jv = Lv,$ so the eigenvalues don't change.