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



When are the adjacency matrices of non-isomorphic graphs similar?
There is no characterization known of when a graph is determined by its spectrum. The probability that a tree on $n$ is determined by its characteristic polynomial goes to zero as $n$ tends to infinity. It is *conjectured* that for graphs the probability goes to one.


