¿Una manera fácil de volver a diagonalizar una matriz después de una adición menor?

Question

Digamos que tengo un real, simétrica positiva semi-definida la matriz de $L$ que tengo diagonalized. Digamos que tengo una muy simple adicionales de la matriz $\Delta(i,j)$ $-1$ en las entradas de $i,j$ $j,i$ y 0 en todos los demás.

EDIT: También, \Delta(i,j) es $1$ en las entradas de $i,i$$j,j$.

Hay una manera sencilla de volver a calcular los autovalores de a $L + \Delta(i,j)$ para un determinado $i,j$ suponiendo que $L_{ij} = 0$?

(Contexto: $L$ es el Laplaciano de la matriz de un grafo. He calculado los valores propios y el espectro de la $L$, ahora voy a agregar un borde a la gráfica de y desea (razonablemente eficiente) calcular el Laplaciano de espectro).

Answer 1

Permítanme darles algunas ideas iniciales.

Vamos a decir $V$ es el ortogonal de la matriz cuyas columnas son los vectores propios de a$L$, $L = VDV^T$ para algunos matriz diagonal $D$.

Ahora vamos a wlog considerar $i = 1, j = 2$.

Tenemos $L' = L + \Delta_{1,2}$. Ahora, se enfríe lo suficiente, podemos hacer algo de matemáticas con la mano para darse cuenta de que $V \Delta_{1,2} V^T = \Delta_{1,2}$, tan sólo tenemos que ponerlo en la descomposición:

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

Así que la matriz dentro de los paréntesis es de bloque-diagonal, con la parte superior del bloque de izquierda a $2\times 2$ matriz, la cual es simétrica. Obviamente, entonces, podemos re-diagonalize $D + \Delta_{1,2}$, y el resultado ortogonal de la matriz tendrá un $2\times 2$ ortogonal bloque en la parte superior izquierda, y el resto será sólo el de la identidad. (Nota: un Poco me recuerda a ellos rotaciones utiliza para iterativo autovalor de cálculo).

Eh, creo que he resuelto que?

EDIT: Nota, esta fue la respuesta de la anterior, la versión sin editar de la pregunta. Se verá en versión modificada más tarde...

EDIT 2: Bueno, en realidad nada cambia, todavía mantiene ese $\Delta_{1,2}$ es invariante bajo la transformación ortogonal.

Uy, obtuvo la matriz de transpone mal. $\Delta$ es, de hecho, no es invariante bajo la transformación ortogonal. Sin embargo, $\Delta$ puede ser escrito ha $uu^T$ $u = (1, -1, 0, \dots)$ , y por lo tanto es un rango de 1 actualización. Esto ha sido estudiado en la literatura de una manera bastante extensa, pero el método no es "trivial". Buscar en este sitio aquí con respecto a la categoría 1 las actualizaciones se proporcionan algunos resultados útiles...