Let G be an undirected graph with bounded degree and n vertices. Let L[G] be the corresponding graph Laplacian, which is a symmetric $n \times n$ matrix. Let V be an $n \times n$ diagonal matrix. I am interested in estimating the gap between the lowest and second lowest eigenvalues of matrices of the form -L[G]+V for various graphs G and diagonal matrices V. I am aware that a lot is known about the gap between the lowest and second lowest eigenvalues of -L[G]. My understanding is that this is the main content of the subject called spectral graph theory. However, I have not found many references on the more general problem, where we add a diagonal term (which I think of as being analogous to the potential term in Schroedinger's equation). I would be most grateful for any suggestions of relevant references or keywords.

  • $\begingroup$ Since any real symmetric matrix is similar to a diagonal matrix, asking for what happens to the spectrum when you add a diagonal matrix to a symmetric matrix is equivalent to asking what can be said about the spectrum of a sum of two symmetric matrices (in terms of the matrices in the sum). I think the short answer to this is: not much. $\endgroup$ – Chris Godsil Feb 28 '13 at 19:33
  • $\begingroup$ Thanks, Chris. Your observation shows me that I must be a bit more specific. I am interested in fairly special G and V. For example, I suspect that if G is a Cayley graph of diameter d and V has no local minima other than one global minimum, then my physical intuition leads me to suspect that the spectral gap of -L[G]+V should be at least of order 1/d^2. However, I don't know how to attempt to prove this sort of thing. $\endgroup$ – StephenJ Feb 28 '13 at 20:20
  • $\begingroup$ If your diagonal matrix has only one or two nonzero entries, some sort of perturbation theory argument might apply. (Rank-1 updates are often easy.) $\endgroup$ – Chris Godsil Feb 28 '13 at 21:25

Your Answer

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

Browse other questions tagged or ask your own question.