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:
- 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$.
- 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.
- $a_{i,i}^{(2)}=1$ is equivalent to $\deg(v_i)=1$ (end vertex).
- 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\}$.
- 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$?
Best Answer
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.