|
Hello, i'm researching the second largest eigenvalue of transition-matrices P for graphs. Let A the adjacency matrix and D the diagonal degree matrix. Then P = D^(-1)A. The laplacian is defined as L = I - D^(-1/2) A D^(-1/2) = D^(-1/2)(D - A)D^(-1/2). I'm interested in the second lagest eigenvalue X of P. If L = I - P it would be enough to examine the second smallest eigenvalue 1-X of L. In my opinion 1-X dont have to be a eigenvalue of L. Is that right? Why are people studing L in search of eigenvalues of P, which are important for the convergence against the stationary pi since ||m^(0)P^n - pi|| <= c*X^n for some c in R and any initinal distribution m^(0)? For interested readers who dont know graphs. A,D,P are symmetric, A and P are non negativ and P has, without limitation, only non negativ eigenvalues. Greetings |
|
I am not sure I understand the question- are you asking how the eigenvalues are related, or why do we care about the laplacian instead of P directly? If it's the first question, the eigenvalues of L are related to eigenvalues of D^{-1/2} A D^{-1/2} (through x-> 1-x). Now take an eigen vector/value (v,lambda) pair of P=D^{-1}A, and let w=D^{1/2}v. Then D^{-1/2} A D^{-1/2} w = D^{1/2} D^{-1}A D^{-1/2} D^{1/2} v = D^{1/2} (D^{-1}A)v= D^{1/2} lambda v= lambda w Therefore, the eigenvectors are not the same, but the eigenvalues are the same. As for why the laplacian is more pleasant to study than P - well, P is not generally symmetric unless you have a regular graph (if 1~2, 1 has degree 2 but 2 has degree 1, P_{1->2}=1/2 but P_{2->1}=1). Also, studying the laplacian matrix eigenvalues using a Rayleigh quotient has a particular nice form (sum of square difference between node potentials on numerator, sum of square potential on denominator), which makes the analysis much more tractable. For instance, I think Cheeger's inequality is proved much more naturally using that particular form. Thank you, that all i wanted to know.
(Jun 06 '12 at 06:09)
Olli Schmitz
|
I'm awfully curious -- if someone disliked this question enough to vote it down, why they didn't offer some amount of constructive criticism.