# Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra edge (changing a single 0 in the matrix into a 1)? or the opposite (change a single 1 to a 0)? I am looking for a bound on the change to the eigenvectors and eigenvalues in the general case, but any answer which is restricted only to symmetric matrices (bidirectional graph) would be also great. In this case the change made to the matrix can be symmetric (e.g if I changed element $A_{ij}$ from 1 to 0 I will also change element $A_{ji}$ from 1 to 0).

The only information I found so far involved perturbation theory, but I'm not sure if any of that is applicable in my case because from what I understand it is relevant only for very small perturbations (orders of magnitude smaller than the values in the matrix) and in my case I'm making quite a big change to the matrix.

EDIT:

I am also interested to know if there is an algorithm for accounting for small changes in the matrix by changing only a subset of eigenvectors: Say I have $n$ independent eigenvectors of a matrix $A$, and I make a small change in $A$ as explained above. I want to hold $k$ eigenvectors fixed, and to account for the change only with changing the $n-k$ other eigenvectors.

So if I denote the change matrix (in the example above it's a matrix with 1 in the element I'm going to change in A and zeros everywhere else) by $\epsilon$ , and the original eigendecomposition of $A$ as $A=Q\lambda Q^{-1}$ where $\lambda$ is a diagonal matrix with the eigenvalues on the diagonal and $Q$ a matrix with the corresponding eigenvectors as columns, can I express (or approximate) $A + \epsilon$ in terms of $Q*$ and $\lambda*$ where the latter two are matrices with $k$ columns which are the same as as $Q$ and $\lambda$ respectively and $n-k$ columns that have changed (maybe it's possible to express the change in terms of $\epsilon$? that would be awesome).

• If you interpret your graph as representing a topological Markov shift, I once investigated what happens if one deletes one long word (using a higher block presentation of the shift), which I viewed as a "perturbation": Perturbations of Shifts of Finite Type, SIAM J. Disc. Math. 2 (1989), 350-365. There are several interesting things one can say, in particular how the largest eigenvalue (or, equivalently, entropy) and characteristic polynomial (or zeta function) change. This does not directly address your question, but you may want to have a look. – Douglas Lind May 9 '16 at 17:40

In this paper they try to construct a sparse weighted graph that spectrally approximates a given weighted graph. They do it by greedily choosing the next edge to add. A key observation is that if you pass to the Laplacian matrix $L$ of a graph, the effect of adding an edge $e=(x,y)$ on the Laplacian is that $$L_{new} = L_{old} + vv^T$$ where $v$ is a column vector with say $1$ in the $x$-th position and $-1$ in the $y$-th. From Cauchy's interlacing theorem, it follows that the eigenvalues of $L_{new}$ are interlaced by the eigenvalues of $L_{old}$, meaning that if $\lambda_1\geq\ldots\geq \lambda_n$ are the eigenvalues of $L_{old}$ and $\lambda_1'\geq\ldots\geq\lambda_n'$ are the eigenvalues of $L_{new}$, we have
$$\lambda_1'\geq \lambda_1\geq\lambda_2'\geq\lambda_2\geq\ldots\geq \lambda_n'\geq\lambda_n$$