Easy way to re-diagonalize a matrix after a minor addition?

Question

Let's say I have a real, symmetric positive semi-definite matrix $L$ that I have diagonalized. Let's say I have a very simple additional matrix $\Delta(i,j)$ which is $-1$ at entries $i,j$ and $j,i$ and 0 everywhere else.

EDIT: Also, \Delta(i,j) is $1$ at entries $i,i$ and $j,j$.

Is there a simple way to re-compute the eigenvalues of $L + \Delta(i,j)$ for a given $i,j$ assuming that $L_{ij} = 0$?

(Context: $L$ is the Laplacian matrix of a graph. I have computed the eigenvalues and spectrum of $L$, now I'm adding an edge to the graph and want to (reasonably efficiently) recompute the Laplacian spectrum).

Answer 1

Let me give some initial thoughts.

Let's say $V$ is the orthogonal matrix whose columns are the eigenvectors of $L$, then $L = VDV^T$ for some diagonal matrix $D$.

Now let's wlog consider $i = 1, j = 2$.

We have $L' = L + \Delta_{1,2}$. Now, cool enough, we can do some math by hand to realize that $V \Delta_{1,2} V^T = \Delta_{1,2}$, so we can just put it into the decomposition:

$L' = V(D + \Delta_{1,2})V^T$

So matrix inside the parentheses is block-diagonal, with the upper left block a $2\times 2$ matrix, which is symmetric. Obviously then we can re-diagonalize $D + \Delta_{1,2}$, and the resulting orthogonal matrix will have a $2\times 2$ orthogonal block in the upper left, and the rest will be just the identity. (Note: Kinda reminds me of them rotations you use for iterative eigenvalue computation).

Huh, so I think I solved that?

EDIT: Note, this answer was for the previous, unedited version of the question. Will look into changed version later...

EDIT 2: Well, nothing really changes, it still holds that $\Delta_{1,2}$ is invariant under the orthogonal transformation.

Oops, got the matrix transposes wrong. $\Delta$ is in fact not invariant under orthogonal transformation. However, $\Delta$ can be written has $uu^T$ for $u = (1, -1, 0, \dots)$, and thus it's a rank 1 update. This has been studied in the literature quite extensively, but the method isn't "trivial". Searching on this site here regarding rank 1 updates will provide some useful results...