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

  • 2
    $\begingroup$ I don't really understand why you are doing whatever you are doing. The beginning of the question has nothing random, and then suddenly we have a random matrix. Are the graphs random? If so, what model? If you don't tell us the model, the answer to both questions is NO. $\endgroup$ – Igor Rivin Jan 22 '18 at 1:46
  • $\begingroup$ Thanks for being first to respond! Let me first address where randomness comes from: I begin with deterministic case (where A' is known) for exposition, since I know how to solve for y' there. My problem is in transitioning to probabilistic setting, because A' and P are unknown. To summarize: A is known, but A' and P are unknown. Since A is known, I can solve for y. However, my object of interest is distribution of (y' - y). $\endgroup$ – haz Jan 22 '18 at 2:51
  • $\begingroup$ To address the second question, what model, I do not have one. A, the graph I 'start' with, is some deterministic graph. I then perturb the graph using the matrix P to get A'. You can think of P as 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, P comes from applying a Bernoulli trial on each edge in the complement graph of A. $\endgroup$ – haz Jan 22 '18 at 2:56

It sounds like the OP has a random perturbation of a fixed graph, which is not considered very frequently, but when they have, it seems to be by A. Flaxman (see, e.g.:

Expansion and lack thereof in randomly perturbed graphs AD Flaxman - Internet Mathematics, 2007 - Taylor & Francis


Eigenvectors are less-well understood. For a comparison of both sorts of questions in a number of models (sadly, none the perturbation model of a fixed graph), see:

Rivin, Igor, Spectral experiments+, Exp. Math. 25, No. 4, 379-388 (2016). ZBL1375.60025.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.