1
$\begingroup$

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

enter image description here

and their adjacency matrices

enter image description here enter image description here

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.

$\endgroup$
  • 6
    $\begingroup$ No this is not true. Google "cospectral graphs" $\endgroup$ – Morgan Rodgers May 2 '18 at 14:12
  • $\begingroup$ @MorganRodgers Thanks for your comment. Ok, apparently the statement is not true in general; however, if there any explanation why the statements fails to be true ? $\endgroup$ – onurcanbektas May 2 '18 at 16:05
  • $\begingroup$ I think it might be more worthwhile to ask why it should be true. $\endgroup$ – Morgan Rodgers May 8 '18 at 6:09
  • 1
    $\begingroup$ It fails because you can have similar integer matrices $B = Q^{-1}AQ$ where $Q$ is not a permutation matrix. $\endgroup$ – Morgan Rodgers May 8 '18 at 14:14
  • 1
    $\begingroup$ You're welcome ! I found these lecture notes by Dr. Rachel Quinlan very useful. You might, too: google.ro/url?sa=t&source=web&rct=j&url=http://… $\endgroup$ – Simon Jun 3 '18 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.