Can we recover the adjacency matrix of a graph from its square?

Question

For the sake of this question, a graph here has a finite number of vertices, with undirected simple edges, no loop, and no weight or label on edges or vertices. Therefore, its adjacency matrix $A=[a_{i,j}]$ is a symmetric matrix with entries in $\{0,1\}$, and $0$ on the main diagonal.

Assuming that $A^2$ is known, can we recover $A$?

The question comes from my self-study of graph theory and I have no idea on how to solve this question. What I know:

1. Let's label the vertices of the graph as $v_1$, $v_2$, $\dots$, $v_n$ so that $a_{i,j}=1$ if there is an edge between $v_i$ and $v_j$, and $0$ otherwise. Then, if $a_{i,j}^{(k)}$ is the entry of $A^k$ at row $i$ and column $j$, $a_{i,j}^{(k)}$ is the number of walks of length $k$ between $v_i$ and $v_j$. Therefore, what is known in the problem are the numbers $a_{i,j}^{(2)}$ of common neighbors between $v_i$ and $v_j$.
2. If the $i$th row of $A^2$ is composed of $0$s, then $v_i$ is an isolated point of the graph. (If $v_i$ is not isolated, then there is a walk $v_i-v_j-v_i$ so $a_{i,i}^{(2)}\ge 1$). So we can simplify the problem by assuming that the graph has no isolated point.
3. $a_{i,i}^{(2)}=1$ is equivalent to $\deg(v_i)=1$ (end vertex).
4. There are results about square roots of positive semi-definite matrices, but $A^2$ is not positive semi-definite, and the square root would not have its entries in $\{0,1\}$.
5. For $n=3$, by looking at the squares of the adjacency matrices of the few possible graphs with $3$ vertices, the answer is yes.

In my question, I assume that it is known that $S=A^2$ is the square of the adjacency matrix of a graph and I wonder if there is another graph whose adjacency matrix has also $S$ for square. So a reformulation of the question is

Does it exist two adjacency matrices $A$ and $B$ (as defined in the first paragraph) such that $A^2=B^2$?

Answer 1

The answer is no - you cannot recover the graph.

You state that what is known is the number of common neighbours between any two vertices. There is a nice class of graphs, Strongly regular graphs, which are essentially defined according to how many common neighbours any pair of vertices have. In particular, a graph is an $(n,k,\lambda, \mu)$ strongly regular graph if it has $n$ vertices, is $k$-regular, every pair of adjacent vertices has $\lambda$ common neighbours, and every pair of nonadjacent vertices has $\mu$ common neighbours.

Per the wikipedia article linked (or just by direct calculation with the above parameters), the adjacency matrix $A$ of an $(n,k,\lambda, \mu)$ strongly regular graph satisfies:

$$A^2 = kI + \lambda A + \mu(J-I-A)$$

Where $J$ is an all $1$s matrix, and I is the $n\times n$ identity matrix.

Thus, any two strongly regular graphs with the same parameters, in which $\lambda = \mu$, have the same squared adjacency matrix! To see this, suppose $\lambda = \mu$, and re-arrange the above equation to get:

$$A^2 = kI + \lambda A + \lambda(J-I-A)$$ $$A^2 = kI + \lambda A + \lambda(J-I) - \lambda A$$ $$A^2 = kI + \lambda(J-I)$$

And indeed there are two strongly regular graphs, with the same parameters, that have $\mu = \lambda$. They are the (4,4) Rook Graph and the Shrikhande Graph, both of which are $(16,6,2,2)$ strongly regular graphs.

Answer 2

Taking $n=4$: any graph consisting of two disjoint edges gives $A^2=I$. There are $3$ such graphs on a given vertex set of size $4$ (but of course they are all isomorphic).

For an example of two non-isomorphic graphs giving the same square: let $n=6$, and consider either a $6$-cycle graph, or a graph consisting of two disjoint $3$-cycles.