0
$\begingroup$

There are two isomorphic graphs for which I want to find their spectrum(their eigenvalues). I am confused that the spectrum will be same for both the graphs since they are isomorphic, but I am not sure.

I first wrote the adjacency matrix for both and they are also same, unless I did something wrong. The graphs have color coded nodes so when I did the adjacency matrices for both, I wrote the nodes in the color-coded manner (like mapping the nodes from first graph to another graph for row and column of adjacency matrix, and hence, the values had to be the same). But I also did the adjacency matrix for second graph according to the number-labels given to nodes, and then the answer had to be different because now the alignment is different.

I mean if they are isomorphic then their adjacency matrices will be same or not? If yes, which sounds obvious because of their property of isomorphism, then why is the question asking for solving adjacency and spectrum for both graphs?

(I watched youtube videos and read pages online but I still have doubts if I am solving this correctly.)

These concepts are new to me, so maybe I am missing on something important here. Please if someone can simplify this or point where I am doing wrong in this problem, that would be much appreciated.

For reference, here is an image of graphs->isomorphic graphs

Adjacency matrices for the graphs.solution

$\endgroup$
  • $\begingroup$ Adjacency matrices are same for isomorphic graphs. $\endgroup$ – stackuser Feb 4 '18 at 23:05
  • 1
    $\begingroup$ not necessary, it would depend on how you label the vertices. $\endgroup$ – prashanth rao Feb 4 '18 at 23:27
  • $\begingroup$ You obtain one matrix from the other by multiplication with the right permutation matrix. $\endgroup$ – Fabio Somenzi Feb 4 '18 at 23:31
  • $\begingroup$ @FabioSomenzi Do you mean that adjacency matrices for isomorphic graphs are same? And to obtain similar matrix we need permutation matrix multiplication? $\endgroup$ – stackuser Feb 4 '18 at 23:47
  • $\begingroup$ No, they are not always the same. (Otherwise checking graph isomorphism would be trivial.) $\endgroup$ – Fabio Somenzi Feb 4 '18 at 23:57
4
$\begingroup$

Let $G_1=(V_1,E_1)$ and $G_2=(V_2, E_2)$ be two isomorphic graphs.

If $V_1= \{ v_1,.., v_n\}$ and $V_2=\{w_1,..,w_n\}$ and $f: V_1 \to V_2$ is the isomorphism, you can define a permutation $\sigma$ via $$f(v_i)=w_{\sigma(i)}$$

Now, if $P:=P_\sigma$ is the corresponding permutation matrix, then you have $$A_1=PA_2 P^{-1}$$ from where you can deduce that $A_1,A_2$ have the same spectrum.

$\endgroup$
1
$\begingroup$

In order to write the adjacency matrix of a graph, you fix a numbering of the vertices. You've done it in two different ways for the right graph, and, lo and behold, you got two different matrices.

If you are given the two graphs of the first figure without the colors, you may spend a minute or two before you figure out the numbering of the vertices that will give you identical adjacency matrices. In that couple of minutes, you are solving the isomorphism problem for those two graphs.

Suppose you numbered the two graphs in a way that the two adjacency matrices are not the same. Since we know that the two graphs are isomorphic, we know that there exists a permutation matrix, let's call it $P$, which will give us one adjacency matrix from the other. This is shown in N.S.'s answer: you pre-multiply to permute the rows and post-multiply to permute the columns.

If you know the right numbering of the vertices, you know the permutation matrix for some other numbering, and vice versa.

Linear algebra defines similar matrices as those that can be obtained from each other by this process of pre- and post-multiplication by a matrix and its inverse. So, the two adjacency matrices may not be the same (quite likely, unless we put in some work or someone does it for us by coloring the nodes) but at least they are similar.

Now, a key property of similar matrices is that they have the same spectrum. So, if two adjacency matrices have different spectra, the corresponding graphs are not isomorphic. Of course, if the number of ones in the two matrices is different, the two graphs are also non-isomorphic, but the spectral method provides an additional filter.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. It helped. $\endgroup$ – stackuser Feb 5 '18 at 1:53

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.