9
$\begingroup$

Hello!

There are two definitions of graph spectrum:
1) Eigenvalues of adjacency matrix $A$.
2) Eigenvalues of Laplacian of adjacency matrix ($L$).
Different sources offer different properties based on this two definitions. Of course it's painful to compute two different spectrums if adjacency matrix is big. So, the question is:

Is there a method to connect one vector of eigenvalues ($\Lambda(A)$) with another ($\Lambda(L)$)?

It is obvious that
$L = T^{-1/2}(T-A)T^{-1/2} = E - T^{-1/2}AT^{-1}T^{+1/2}$, where
$T$ is the diagonal matrix with $t_{v,v}=d_v$, and $t_{u,v}=0$, if $u\ne v$,
and $t^{-1}_{v,v}=0$, if $d_v=0$,
$d_v$ - degree of $v$.

Also, when $G$ is $k$-regular, $L=I-\frac{1}{k}A$, so $\Lambda(L)=1-\frac{1}{k}\Lambda(A)$.
But in general case it's like I need to compute eigenvalues of $AT$, if I know eigenvalues of $A$. ($T$ is diagonal).

Thanks for any help.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Essentially your question is equivalent to asking for the relation between the spectrum of $A+D$ and $A$, where are $A$ is symmetric, $D$ is diagonal and both matrices are real. And, by change of basis, this is equivalent to asking for the relation between the spectrum of $A+B$ and $A$ when $A$ and $B$ are real symmetric. A lot of thought has been given to this question. The short summary is that eigenvalues of $A$ provide no information useful towards computing the eigenvalues of $A+D$.

It might also be worth pointing out that there are many more than two definitions of graph spectrum (normalized and unsigned Laplacian, Seidel, spectrum of complement, to mention four more that come quickly to mind). All of these provide the same information for regular graphs, but in no case does computing one provide much help in computing another.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ One could also add signless Laplacian and distance spectrum as two popular options. $\endgroup$
    – Felix Goldberg
    Commented Jan 14, 2013 at 13:34
  • $\begingroup$ Thank you for you answer. First, I know the answer for regular graphs, and I gave it in question. Second. Consider non-regular graphs. Let us assume that spectrums in different definitions give exactly the same information. Then there must be some injection between them, right? If not, then the do not give exact same information. Or I am missing something? Third. I agree with you that there are no general decision for eigenvalues of matrix product, but maybe there are some particular cases? $\endgroup$
    – TotalNoob
    Commented Jan 14, 2013 at 13:50
  • $\begingroup$ The different spectrums do not give the same information. For example the smallest pair of cospectral graphs (relative to the adjacency matrix) are not Laplacian cospectral. Even for trees, we do not get the same information. Note also that there is no real difference in behavior (or misbehaviour) of matrix products and that of matrix sums (for the questions we are considering). $\endgroup$
    – Chris Godsil
    Commented Jan 14, 2013 at 14:11
  • 1
    $\begingroup$ and conversely: there exist pairs of graphs that are laplacian cospectral but not adjacency cospectral: see e.g. here. I would turn the question and do not see this as a problem, but rather as an opportunity: to attack an inverse spectral problem on graphs one has many tools - i.e., many matrices - at hand. $\endgroup$
    – Delio Mugnolo
    Commented Jan 17, 2013 at 8:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .