[Math] Automorphism group of a graph = Automorphism group of that graph’s adjacency matrix

algebraic-graph-theorygraph theorygraph-isomorphismgroup-theoryproof-verification

Is automorphism group (or set) of a graph $G$ equal to the automorphism group (or set) of adjacency matrix of $G$?

Example: $G_1, G_2$ are separate graphs where $G_1^{\pi}= G_2$ and $ G= \bar G_1 \cup \bar G_2$. Also, $\pi$ swaps only $2$ vertices of $G_1$, say, it swaps $k^{th}$ vertex with $(k+1)^{th}$ vertex.

So, the adjacency matrix of $G_1 \neq$ the adjacency matrix of $G_2$.

We will have this dissimilarity in $G$ also.

$G$ is made of 2 non equal matrices of $\bar G_1, \bar G_2$. There are only two dissimilar columns/ rows. They are $k^{th}$, $(k+n)^{th}$ and $(k+1)^{th}, (k+1+n)^{th}$ vertex. Remaining all pairs of rows/columns $(i,i+n)$ are same where $i \neq k, k+1$.

Now, consider a permutation $\sigma$ of $G$ that swaps $k^{th}$ vertex of $G$with $(k+1+n)^{th}$ vertex of $G$. Note that, $k^{th}$ vertex is in $G_1$ and $(k+1+n)^{th}$ vertex is in $G_2$.

here, the adjacency matrix of $G^{\sigma} \neq$ the adjacency matrix of $G$.

So, Automorphism group of a graph $\neq$ Automorphism group of that graph's adjacency matrix.

Is it correct?

This post is the source of my argument.

  1. If $A$ is a matrix and $\pi$ is an automorphism of $A$, then $A^{\pi} =A$.

Best Answer

Your definition of automorphism is a bit too strong, I feel. Leaving something "unchanged" in the sense that the numbers in each cell of a matrix is a VERY strong notion of equality. However, you're not using that definition of equality for graphs.

As corrected by Morgan Rodgers, strict equality actually works fine. The adjacency matrices are indeed unchanged under automorphisms when the adjacency matrices are constructed with the same vertex set and the vertex $v_i$ corresponds to column and row $i$ always.

Everything below still holds, but any mention of row-column swapping may be trivially true.

If a graph undergoes an automorphism, it has been turned into another graph with equivalent structure.

$G_1 = (V_1, E_1)$

$G_2 = (V_2, E_2)$

$f(G_1) = G_2$ is an automorphism if and only if:

  • There exists a bijection $g : V_1 \to V_2$ such that $(x, y) \in E_1$ if and only if $(g(x), g(y)) \in E_2$

This is not the same as "$f(G_1) = G_2$ if and only if $V_1 = V_2$ and $e \in E_1 \iff e \in E_2$", which would be true equality. This stricter definition is closer to the one you were holding for adjacency matrices. Essentially, each index in each of the vertex and edge is "unchanged", therefore under this equality any swapping at all is not an automorphism. This is not what you intend at all, I'm fairly certain.

If you consider that you're already constructing equivalence classes between graphs (otherwise, the only automorphism on graphs is the identity map), then you can similarly construct an equivalence class on the adjacency matrices.

You define a new $=$ relation such that $A_1 = A_2$ if and only if $A_2$ can be attained by a sequence of $(i,j)$ row-column swaps (swap the $i,j$ rows and $i,j$ columns) from $A_1$. For any finite graph, this is verifiable exhaustively by trying every possible sequence of swaps to check equality. This equality relation is far more relaxed than cell-by-cell equality and it gives you exactly what you need to verify automorphisms between the graphs these adjacency matrices represent.

This equality relation is consistent with any automorphism on your graph. If your automorphism swaps the $i,j$ vertices with each other, this bijectively maps to an automorphism in your adjacency matrices by swapping the $i,j$ row-columns. The reverse also holds following similar logic.

Any automorphism on your graphs can be factored into a minimal chain of single-swap automorphisms. Any automorphisms on your adjacency matrices can be constructed by composition of single-swap automorphisms (closure property of automorphisms). As such, there is a unique automorphism on the graphs for each automorphism on the adjacency matrices. The reverse is also true following similar logic.

We now have a bijective map from the automorphism group of the graphs to the automorphism group of their adjacency matrices. Therefore, the groups are equivalent.

Related Question