Finding Graph from eigenvectors

Question

I have an matrix A whose columns I want as the eigenvectors of the Laplacian of a graph. I can take any real eigenvalues such that the graph exists. How do I go from here to reconstructing the graph ? The only approach I could think of was one where I take random eigenvalues in the diagonal matrix and then just multiply by the eigenvector matrix and its inverse and then see what graph pops out. This won't ensure that I end up with a Laplacian for an actual graph. Any suggestions or ideas are highly appreciated.

Answer 1

You can't construct a graph in this way from any given collection of eigenvectors. Some basic results in spectral graph theory give us the following properties of the Laplacian:

1. The Laplacian matrix is positive semidefinite
2. The multiplicity of $0$ as an eigenvalue of $L$ is the number of connected components of our graph and its eigenspace is spanned by the indicator vectors of the graph components.

The indicator vector of a subset $X$ of the graph vertices is the vector that is constant over $X$, $$ \mathbf 1_X(i) = \begin{cases} 1 &\text{if } i \in X \\ 0 &\text{otherwise.} \end{cases} $$

For a collection of vectors to be the eigenvectors of a Laplacian matrix, that collection has to include indicator vectors for the graph components. Each other vector must be orthogonal to these indicator vectors and their corresponding eigenvalue must be positive. If the columns of $A$ are orthogonal and the first $k$ are indicator vectors of the desired components, then for an arbitrary sequence of positive real numbers $\lambda_{k+1}, \lambda_{k+2} \ldots, \lambda_n$, the matrix $$ L = \sum_{i=k+1}^n \lambda_i \mathbf a_i \mathbf a_i^T, $$ is the Laplacian matrix of a weighted, undirected graph with $k$ components. Most graphs constructed this way will be dense.