From Wikipedia. In linear algebra, two n-by-n matrices A and B are called similar if $$ B = P^{-1} A P$$ for some invertible n-by-n matrix $P$. If $P$ is a permutation matrix, $A$ and $B$ are **permutation similar**. Two graphs $G,H$ are isomorphic iff their adjacency matrices $A_G,A_H$ are permutation similar. If $A_G$ and $A_H$ are not similar then $G$ and $H$ are not isomorphic. It is possible $A_G$ and $A_H$ to be similar and $G$ and $H$ are not isomorphic. Experimentally this doesn't happen often. Recognizing matrix similarity is polynomial, $O(n^3)$. $A$ and $B$ are similar if and only if they have the same rational canonical form (AKA Frobenius form). > Is there characterization of the graphs for which $A_G \sim A_H \implies G \cong H$? Consider the following algorithm for graph isomorphism. Recursively delete vertex from $G$ and from $H$ and check the matrices for similarity. If we don't hit bad case we will find isomorphism in polynomial time. The exponential case is if we hit bad cases very often. > Is there construction of non-isomorphic graphs for which the above algorithm is exponential? --- **Added** The sequence of non-symmetric matrices of graphs of order $n$ starts 1 , 2 , 4 , 11 , 33 , 151 , 988 , 11453 , 247357 This coincides with [OEIS A082104 Number of distinct characteristic polynomials among all simple undirected graphs on n nodes](https://oeis.org/A082104) If true, this would imply that symmetric matrices with $0,1$ entries are similar iff their characteristic polynomials are equal (which is likely known).