6
$\begingroup$

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!

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Dec 1, 2010 at 4:22
  • $\begingroup$ Thank you Aaron Meyerowitz! Your comment is very helpful! I've add more information about my question. $\endgroup$
    – jkjium
    Dec 1, 2010 at 6:35
  • 2
    $\begingroup$ 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? $\endgroup$
    – Tracy Hall
    Dec 1, 2010 at 10:04
  • $\begingroup$ Thanks Tracy Hall. The papers I'm reading only talk about general inverse eigenvalue problem. not specific for Graph Laplacians. $\endgroup$
    – jkjium
    Dec 1, 2010 at 20:17
  • 3
    $\begingroup$ 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. $\endgroup$
    – Tracy Hall
    Dec 2, 2010 at 6:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.