Can a symmetric $0$-$1$-matrix $A$ be recovered from its eigenvectors and eigenvalues?

61 Views Asked by At

Let $n \in \mathbb{N}_{\geq 1}$ and $A \in \mathbb{Sym}_{n \times n}(\{0,1\})$ be a symmetric $n \times n$-matrix with entries $a_{i,j} \in \{0,1\}$ and diagonal entries $a_{i,i} = 0$. Then $A$ can be interpreted as the adjacency matrix of an undirected, simple graph without self-loops.

Since $A$ is symmetric, it has $n$ (possibly identical) real eigenvalues $\lambda_1,...,\lambda_n$ if counted via algebraic multiplicity. Associated with those eigenvalues is an orthonormal basis of eigenvectors $v_1,...,v_n$ of $A$.

Does knowing the set of eigenvectors $\{v_1,...,v_n\}$ as well as the set of eigenvalues $\{\lambda_1,...,\lambda_n\}$ allow one to fully and unambiguously reconstruct $A$ ?

If no, can this be done if one additionally knows the algebraic multiplicities of all eigenvalues?