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.
Addendum:
As @Morgan pointed out in his comment, there are graphs which are not isomorphic but have the same set of eigenvalues, called cospectral graphs. However, I would like to know why the statement fails to be true.