4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 9, 2016 at 17:40

1 Answer 1

5
$\begingroup$

What I'm about to say applies to the eigenvalues (at least). Here's what comes to my mind - it sprung from memory of some results of Batson, Spielman and Srivastava, mostly the paper "Twice Ramanujan sparsifiers" (http://arxiv.org/pdf/0808.0163.pdf).

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$$

(I could find a proof here http://orion.math.iastate.edu/lhogben/research/LaplacianTalkHall.pdf). The Batson-Spielman-Srivastava paper goes on to make this relationship more quantitative, by providing expressions for the new eigenvalues and intuition for their positions between the old ones via a physical model. I think section 3 of their paper would be of interest to you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.