MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to construct a graph Laplacian matrix from a set of eigenvalue. I've read several papers about inverse eigenvalue problems but to be honest I didn't understand clearly. Could somebody provide me a general idea about inverse eigenvalue algorithms? Which algorithm is the best for me to choose? Or a concrete example. Below is a detailed description of my question:

Suppose we have a connected undirected graph $G$ with $n$ vertices. $L$ is the Laplacian matrix of $G$, then the eigenvalues of $L$ have the form $$ 0 = \lambda_0 \le \lambda_1 ... \le \lambda_n$$ Now if I slightly change $\lambda_1$ with arbitrary amount to $\lambda_1$* (still in the same form) is it possible to construct another graph Laplacian matrix by this new set of eigenvalues $\{$ $\lambda_0$, $\lambda_1$* $...$ $\lambda_n$ $\}$?

I know that only finite number of sets can be the eigenvalues of a graph laplacian matrix. Does the eigenvalues have any particular form to be the eigenvalues of a Laplacian matrix?

Thanks very much!

share|cite|improve this question
Maybe you could give an example of what you want to do. A list of n numbers might not be the eigenvalues of a graph, in fact only finitely many are. And the eigenvalues of a graph can also be the eigenvalues of another graph. – Aaron Meyerowitz Dec 1 '10 at 4:22
Thank you Aaron Meyerowitz! Your comment is very helpful! I've add more information about my question. – jkjium Dec 1 '10 at 6:35
There are also inverse eigenvalue problems that concern not the uniquely defined Laplacian where every nonzero off-diagonal entry is exactly $-1$, but rather consider the entire set of generalized Laplacians, where the entries that are $-1$ in the Laplacian can be any strictly negative numbers, and the diagonal entries are chosen so that each row sums to $0$. It is in the setting of generalized Laplacians that it often makes the most sense to talk about small perturbations of the spectrum. Could the papers you are reading be about generalized Laplacians? – Tracy Hall Dec 1 '10 at 10:04
Thanks Tracy Hall. The papers I'm reading only talk about general inverse eigenvalue problem. not specific for Graph Laplacians. – jkjium Dec 1 '10 at 20:17
For the standard graph Laplacian, the answer to your question is no: Since the diagonal entries are integers the trace is too, which is also the sum of the eigenvalues. Changing one eigenvalue by less than $1$ while keeping the others fixed will spoil that property. – Tracy Hall Dec 2 '10 at 6:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.