5
$\begingroup$

The automorphism group of a graph (lets us consider undirected) is the set of all permutation on vertices that preserve the adjacency. It is claimed: automorphism group of graph may be equivalently defined as the set of permutation matrices $\pi$ which commute with the adjacency matrix. How can we justify this claim.

Thank you.

  • 0
    I am not yet clear, can you please elaborate. How do we get the adjacency matrix of permuted graph?2012-08-11

2 Answers 2

5

Fun facts: (i) The $(i,j)$th entry of any matrix $M$ is equal to $e_i^TMe_j$, where $e_i$ is the vector with $1$ in the $i$th entry and $0$ elsewhere. (ii) $e_{\pi(i)} = Pe_i$, where $P$ is the matrix corresponding to the permutation $\pi$. (iii) Every permutation matrix $P$ is orthogonal, i.e. $P^T = P^{-1}$.

Let the adjacency matrices of the original and permuted graphs be $A$ and $B$. We want the $(\pi(i),\pi(j))$th entry of $B$ to be the same as the $(i,j)$th entry of $A$ is $1$. Equivalently, we want $(Pe_i)^TB(Pe_j) = e_i^TAe_j$. For this to hold for all $i$ and $j$, we must have $P^TBP = A$, or $B = PAP^T$.

If the permutation preserves adjacency, then $A = B = PAP^T$, so $AP = PAP^TP = PA$. Therefore $P$ commutes with $A$.

  • 0
    Presumably one can do this without introducing the $e_i$s by just figuring out how pre- and post-multiplication by $P$ move the rows and columns around, but I can never keep track of that stuff.2012-08-11
1

Let $\sigma$ be permutation and $\pi$ - corresponding matrix. let $f(G)$ is adjacency matrix of G. Then $f(\sigma G)=\pi f(G)\pi^{-1}$. Hence if $\sigma G=G$ then $\pi f(G)\pi^{-1}=f(G)$ and $f(G)\pi=\pi f(G)$. The converse argument is similar.

  • 0
    actually my doubt was in how did you write $f(\sigma G) = \pi f(G) \pi^{-1}$2012-08-11