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

If true, this would imply that symmetric matrices with $0,1$ entries are similar iff their characteristic polynomials are equal (which is likely known).

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-similar 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

If true, this would imply that symmetric matrices with $0,1$ entries are similar iff their characteristic polynomials are equal (which is likely known).

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?

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

If true, this would imply that symmetric matrices with $0,1$ entries are similar iff their characteristic polynomials are equal (which is likely known).