# Relationship Between Two Adjacency Matrices

Given a graph $A$ with nodes $p_{1},p_{2},...,p_{n}$, let $\{A^{*}\}$ be the set of all graphs isomorphic to $A$. Consider a graph $Q$ with vertices $a,b,$ and $c$ where there are three edges between $a$ and $b$, one edge between $a$ and $c$, and no edges between $b$ and $c$. Then $Q^{*}\in \{Q^{*}\}$ if and only if it has vertices $d,e,$ and $f$ where there are three edges between two of these nodes, one edge between one of the previous two nodes and the third, and zero edges between the other one of the first two nodes and the third node.

Now, consider the adjacency matrix for a graph $P$. Call it $M(P)$. Then, what conditions may we impose on the relationship between $M(P)$ and $M(A)$ which are necessary and sufficient for saying that $P\in \{A^{*}\}$? Are there results pertaining to this issue? If there are, what are they?

-
This seems like homework. Are you familiar with the term "Graph Isomorphism"? – EuYu Nov 2 '12 at 19:07
This isn't homework. It's just a thought I have. I am now aware of what a graph isomorphism is, but it does not seem there is a necessary/sufficient theorem pertaining to the relation between the adjacency matrices. – Jebruho Nov 2 '12 at 19:10
I wasn't stating it as a condition. I'm merely pointing out that your set $A^{*}$ is more compactly stated as the set of all graphs isomorphic to $A$. – EuYu Nov 2 '12 at 19:13
I edited it accordingly. Thank you. – Jebruho Nov 2 '12 at 19:15

Two graphs are isomorphic if and only if there is a permutation matrix $P$ relating their adjacency matrices such that $$A = PBP^{-1}$$ where $A$ and $B$ are the adjacency matrices of the two graphs. More compactly, two graphs are isomorphic if and only if their adjacency matrices are similar through a permutation matrix.
To see this, suppose that $\sigma$ is a permutation on the vertices. Let $P$ be the corresponding permutation matrix. Then the adjacency matrices are related by $$b_{i,\ j} = a_{\sigma(i),\ \sigma(j)}$$ Since the entry $b_{i,\ j}$ gives the connectivity condition between vertices $i$ and $j$, this is precisely the isomorphism condition.
Thank you, but is there an efficient way to see if this $P$ exists? – Jebruho Nov 2 '12 at 19:30