3
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ @User12345 , if $A$ is a matrix and $\pi$ is an automorphism of $A$, then $A^{\pi} =A$. $\endgroup$ – Michael May 23 '16 at 21:22
  • $\begingroup$ If you're swapping the $i,j$ vertexes of a graph, this is equivalent to swapping the $i,j$ rows and $i,j$ columns (in either order) of its adjacency matrix. $\endgroup$ – Axoren May 23 '16 at 22:30
  • $\begingroup$ @Axoren yes, but it will happen in $G_1$ But when you apply $\sigma$ it will move one of i , j $\endgroup$ – Michael May 23 '16 at 22:34
  • $\begingroup$ Are the vertex sets disjoint between $G_1$ and $G_2$? If so, you can simply combine their adjacency matrices as $\left[\matrix{A_1 & 0 \\ 0 & A_2}\right]$. This becomes the adjacency matrix of $G$. $\endgroup$ – Axoren May 23 '16 at 22:37
  • 1
    $\begingroup$ Yes, automorphism group of a graph is isomorphic to the automorphism group of the matrix, where the permutation $\pi$ acts on a matrix $A$ by applying the same permutation to the rows and columns. Furthermore, if the labelling of the graph vertices agrees with the ordering of the rows/columns of the matrix, these two groups contain the exact same permutations. $\endgroup$ – Morgan Rodgers May 24 '16 at 13:31
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ An automorphism of a graph preserves adjacency, hence this same permutation applied to the rows/columns of a matrix will leave the matrix invariant (ie completely unchanged). $\endgroup$ – Morgan Rodgers May 24 '16 at 13:35
  • $\begingroup$ @MorganRodgers That depends on how the adjacency matrix is constructed. If the rows and columns are labeled by vertices, row 1 will always belong to $v_1$. However, if swapping $v_1$ with $v_2$ changes this labeling instead, then you will in fact have no changes made to the matrix. I assumed the former, where row $i$ was associated with $v_i$. $\endgroup$ – Axoren May 24 '16 at 13:38
  • $\begingroup$ Nice answer, i am aware of equivalence relation, but i was asking if adjacent matrices are equal, how do I verify it, I mean practically $\endgroup$ – Michael May 24 '16 at 13:40
  • 2
    $\begingroup$ @Jim If it is in fact an automorphism of $G = G_{1} \cup G_{2}$, then if it swaps a vertex of $G_{1}$ with a vertex of $G_{2}$, and $G_{1}$ and $G_{2}$ are each connected, then it in fact swaps all vertices of $G_{1}$ with the vertices of $G_{2}$. It will also reorder the rows and columns of the adjacency matrix of $G = G_{1} \cup G_{2}$ in a way that preserves the matrix. $\endgroup$ – Morgan Rodgers May 24 '16 at 13:51
  • 2
    $\begingroup$ @Axoren Yeah, it's a little tricky because if you arbitrarily relabel the vertices then you of course end up with a new graph that is isomorphic to the original, but the labelings are not considered isomorphic (ie they don't agree with each other in terms of the adjacency matrices). It's a nicely written answer though, with the small correction it looks very good. $\endgroup$ – Morgan Rodgers May 24 '16 at 13:53
1
$\begingroup$

Each permutation $g \in S_n$ can be represented by an $n \times n$ permutation matrix $P(g)$ defined by $P(g)_{ij} = 1$ iff $g$ maps $j$ to $i$, and $P(g)_{ij}=0$ otherwise.

Let $A$ denote the adjacency matrix of the graph $G$. It can be verified that a permutation $g$ is an automorphism of the graph $G$ if and only if $P(g)^{-1}AP(g) = A$. In other words, a permutation $g$ of the vertex set preserves adjacency (and non-adjacency) in the graph $G$ if and only if the permutation matrix $P(g)$ preserves the adjacency matrix $A$.

In this sense, the automorphism group of a graph and of its adjacency matrix are equal. When a permutation $P(g)$ is applied to an adjacency matrix $A$, you need to make sure $P(g)$ is multiplied on both sides of $A$, so that the same permutation is effected on both the columns and the rows of the adjacency matrix. Recall that pre-multiplying a matrix $A$ effects row operations/permutations on the matrix $A$, while post-multiplying a matrix effects column operations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 , Thanks for you answer, would you please edit your answer or comment here about the example I gave in my post? $\endgroup$ – Michael May 25 '16 at 7:11
  • 1
    $\begingroup$ @Jim If you have an automorphism $\sigma$ of $G$ that swaps the $k$ and $(2k+1))$th vertices, then $P(\sigma)$ will preserve the adjacency matrix also. So it is not true that the adjacency matrices of $G$ and $G^\sigma$ are not equal. This is because the adjacency matrix of $G$ is $A$ and the adjacency matrix of $G^\sigma$ is $P(\sigma)^{-1}AP(\sigma)$, and if $\sigma$ is an automorphism then these two matrices will also be equal. $\endgroup$ – svsring May 25 '16 at 7:19
  • 1
    $\begingroup$ @Jim In fact, one can define an automorphism of a graph to be a permutation $\sigma$ such that $P(\sigma)^{-1} A P(\sigma)=A$. This is an equivalent definition for the automorphism of a graph (in terms of the adjacency matrix of the graph rather than in terms of adjacencies in the graph). $\endgroup$ – svsring May 25 '16 at 7:33

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.