# Can we argue that two graphs are isomorphic iff their adjacency matrices have the same eigenvalues?

## Context:

Inspired from the idea that we can show the isomorphism between two graphs by showing that the adjacency matrix of one of the graphs can be obtained by interchanging rows&columns (applying the corresponding operations at the same time) of the other's adjacency graph (when we give some order to their vertex set); I thought that since the adjacency matrix of any graph is symmetric, if we think it as a linear map (from $\mathbb{R}^n \to \mathbb{R}^n$)for a second, we can argue that it is diagonalisable. Since the elementary row operations just correspond to multiplying the matrix from left and right by some permutation matrices, as stated in here; hence, two graphs should be isomorphic iff their adjacency matrices should have the "eigenvalues" when we consider their adjacency matrix as a linear map. Therefore, if formalise it;

two graphs are isomorphic iff the adjacency matrix of two graphs (with some ordered vertex set) have the same "eigenvalues".

For example, consider the graphs

and their adjacency matrices

As I have computed in here and here both have the same (or some permutation of each other) diagonal form, so with this logic, they should be isomorphic (and actually are).

## Question:

Is this idea works in general. Can you spot where the argument might fail ? I mean after all, the adjacency matrix can't even have any real entries, and there is no geometric meaning of matrix multiplication for the adjacency matrix of a graph, so I couldn't prove this statement in formal way, but still ,for computational purposes, can we argue something about the validity of this method ?

Because as you can see, computationally diagonalising a matrix is not that of a problem (as long as the number of vertex is not large), and this method would give us a algorithm for determining whether two graphs are isomorphic or not.

• It fails because you can have similar integer matrices $B = Q^{-1}AQ$ where $Q$ is not a permutation matrix. – Morgan Rodgers May 8 '18 at 14:14