# Complexity of the recovery of an adjacency matrix from its square

I am interested in the following problem: Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix?

Is the computational complexity of this problem known?

Remarks:

• Of course this can also be phrased as a search problem, where you are given the matrix $A^2$ for $A$ an adjacency matrix of an undirected graph and the problem is to find any adjacency matrix (of an undirected graph) $B$ such that $B^2 = A^2$.

• Motwani and Sudan (Computing roots of graphs is hard, 1994) and Kutz (The complexity of Boolean matrix root computation, 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.

• The problem is equivalent to deciding the existence of $n$ vectors with given pairwise inner products. Apr 6 '15 at 17:02
• Very recently there was a paper addressing this question for stochastic matrices rather than adjacency matrices (arxiv.org/abs/1411.7380). The property of being a square in this context is known as divisibility and is shown to be NP-complete in the paper I mentioned. Apr 6 '15 at 19:24
• @MohammadAl-Turkistany how are they equivalent? The solution to OP's problem requires additional structure than generic vectors (integer valued, certain indices must be zero, etc). Apr 6 '15 at 22:02
• This ought to be related to checking if a degree sequence is graphic. Notice that in $A^2$ the diagonal represents the degree sequence and $(A^2)_{ij}$ the number of common neighbours of vertices $i,j$. Thus it is a restriction to the graphic degree sequence problem. No idea how to solve it though. Apr 28 '15 at 20:52

Recently there was a optimization variant studied, which gives FPT algorithms for the problem when you want to test whether a graph has a square root with at most (respectively at least) $s$ edges for some given integer $s$.