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

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$$?

• Your last bolded question may need disambiguation - "two adjacency matrices for non-equivalent graphs".
– Nij
Jan 26 at 8:08
• If there is actually non-uniqueness of squares of graphs, my hunch is that counterexamples can be found among bipartite graphs. Jan 26 at 8:11
– Sil
Jan 26 at 10:54
• I deleted my answer, it was stupid Jan 26 at 13:00

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.

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.

• I don't understand your example for n = 6: a disjoint union of two 3-cycles has adjacency matrix which is a direct sum (of two 3x3 matrices), while a 6-cycle does not, and the squares of their adjacency matrices don't even have the same zero pattern Jan 26 at 22:07
• @math54321If the 6-cycle looks like $1-2-3-4-5-6-1$, then organise the rows and columns so that the first 3 rows / columns correspond to vertices 1,3,5 and the last 3 correspond to 2,4,6. In particular, letting $X$ and $Y$ be the two squared adjacency matrices, there's a permutation matrix $P$ (that performs the swap mentioned in sentence 1 of this comment) such that $X$ and $Y$ are similar via $P$: so $X = PYP^{-1}$. Jan 27 at 7:20
• @math54321 The two graphs could be $\{1-2-3-4-5-6-1\}$ and $\{1-3-5-1 \,, \,2-4-6-2\}$. Isn't it the case that for any $i$ and $j$, the number of length-$2$ walks from $i$ to $j$ is the same in both graphs? Jan 27 at 7:21
• Ah I see @BrandonduPreez and responded almost simultaneously :) Jan 27 at 7:22
• Thanks @BrandonduPreez and James for the clarification. I think it's important to specify the exact graph (labeled with edges/vertices) when talking about the adjacency matrix, not just the isomorphism type of the graph (which only gives the adjacency matrix up to conjugation by permutation matrices) Jan 27 at 17:29