Consider two simple, undirected graphs with adjacency matrices ${\bf A}$ and ${\bf A'}$. Let ${\bf P} = {\bf A'} - {\bf A}$. Thus, ${\bf P}$ is symmetric and always 0 along the diagonal.

Let $f({\bf X})$ be a (undisclosed) linear transformation of a matrix $X$. Let ${\bf y}$ and ${\bf y'}$ be vectors, and ${\bf 1}$ denote the vector of all ones.

I'm using the matrix inversion lemma (Woodbury formula) to rewrite $${\bf y'} = f({\bf A'})^{-1}f({\bf A}){\bf y}$$ as $${\bf y'} = {\bf y} - f({\bf A})^{-1}{\bf Q}\left[{\bf \Lambda^{-1}} + {\bf Q}f({\bf A})^{-1}{\bf Q}\right]^{-1}{\bf Q}^{-1}{\bf y}$$ where I use the eigendecomposition $${\bf P = Q^{-1}\Lambda Q}.$$

Unfortunately, ${\bf A'}$ is unknown, so ${\bf P}$ is a random symmetric matrix that is constrained away from being pure Bernoulli. (Even if it were Bernoulli, it appears most of the random matrix literature focuses on the case of p=0.5, whereas I'm most interested in the case of p << 0.5.)

Is it possible to determine the probability distribution of ${\bf Q}$ and ${\bf \Lambda}$ at this point in the random matrix literature? (I am an outsider in an applied field.)

A, the graph I 'start' with, is some deterministic graph. I then perturb the graph using the matrixPto getA'. You can think ofPas thus being the random graph of interest. While I'm interested in a combination of cases (edge addition and removal), I'd place priority on the case of edge addition. In this case,Pcomes from applying a Bernoulli trial on each edge in the complement graph ofA. $\endgroup$ – haz Jan 22 '18 at 2:56