Consider an unknown symmetric matrix $A$ consisting of zeroes and ones. We know
- The eigenvalues of $A$.
- Every row in $A$ has the same number of ones, which implies that one eigenvector of $A$ is $v=(1,1,\dots, 1)^T$.
Can we find $A$ (up to permutations, perhaps) efficiently?
Let $u=[1,\cdots,1]^T$. Since $A$ is a non-negative matrix and also a symmetric matrix, there is a permutation $P$ s.t. $B=PAP^{-1}=diag(B_i)_{i\leq k}$ where the $B_i$ are irreducible or $0$ and, moreover, are symmetric.
Notice that $Pu=u$ and $Au=\lambda u$, where $\lambda$ is a positive integer; then $Bu=\lambda u$ and, moreover, $B_iu=\lambda u$ and all the $(B_i)$ are irreducible.
$\rho(B_i)=\lambda$ is the Perron-Frobenius eigenvalue of $B_i$. Since $B_i$ is symmetric, the only possible eigenvalues with maximal modulus are $\pm \lambda$. Let $h_i$ be the period of $B_i$. If $-\lambda\in spectrum(B_i)$, then $h_i=2$ and $\pm\lambda$ are simple eigenvalues of $B_i$; else, $B_i$ is aperiodic and primitive (there is $m_i$ s.t. ${B_i}^{m_i}>0$).
When $h_i=2$, there is a permutation $Q$ s.t. $QB_iQ^{-1}=\begin{pmatrix}0_r&C\\C^T&0_r\end{pmatrix}$. Then $\chi_{B_i}=\det(\lambda^2I-CC^T)$ divides the known polynomial $\chi_A$ and has opposite real roots ($\pm$ the singular values of $C$); in particular, the dimension of $B_i$ is even.
Remark. The multiplicity of $\lambda$ in $spectrum(A)$ is equal to $k$. The multiplicity ($\leq k$) of $-\lambda$ in $spectrum(A)$ is equal to the number of $B_i$ s.t. $h_i=2$.
Toy example. $A=\begin{pmatrix}0&0&1\\0&1&0\\1&0&0\end{pmatrix},B_1=[1],h_1=1,B_2=\begin{pmatrix}0&1\\1&0\end{pmatrix},h_2=2$.
EDIT. We consider the OP's example: $\chi_A=(x-4)(x^2-2)^3$.
Here, $\lambda=4$ and there is only one block $B_1$ of dimension $7$ which is primitive. Notice that my post above reduces the problem to submatrices of $B$, only when $k>1$; thus my study is useless for this example.
Yet, we can solve it, using the Grobner basis method. We consider an algebraic system in the $28$ unknowns $(a_{i,j})_{i\leq j}$.
i) The simplest relations are $Au-u=0$ and ${a_{i,j}}^2-a_{i,j}=0$.
ii) Since $trace(A)=4$, we may assume (up to a permutation) that $a_{1,1}=a_{2,2}=a_{3,3}=a_{4,4}=1,a_{5,5}=a_{6,6}=a_{7,7}=0$.
iii) We add the relations $trace(A^2)=28,trace(A^3)=64,trace(A^4)=280$. In particular, we do not use the values of $trace(A^5),trace(A^6),trace(A^7)$.
We obtain the Grobner basis in 1"7 and the previous relations are enough for all solutions to have $\chi_A$ as characteristic polynomial. There are $24$ solutions; to obtain a particular solution, one arbitrarily imposes
$a_{1,2}=a_{1,3}=a_{2,5}=a_{1,6}-1=0$. Finally, a particular solution is
$A=\begin{pmatrix}1&0&0&1&1&1&0\\0&1&0&1&0&1&1\\0&0&1&1&1&0&1\\1&1&1&1&0&0&0\\1&0&1&0&0&1&1\\1&1&0&0&1&0&1\\0&1&1&0&1&1&0\end{pmatrix}$.
We can see that $A^2>0$.