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).