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).

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. $\endgroup$ – Douglas Lind May 9 '16 at 17:40