# Graph isomorphism as permutation matrix.

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.

• Why is not it obvious? – aska langley Aug 11 '12 at 9:19
• what is the interpretation of commutation here.? – DurgaDatta Aug 11 '12 at 9:24
• Two matrices are said to commute if $AB=BA$. Hint: What is the adjacency matrix of the permuted graph? Then use the fact that permutation matrices are orthogonal. – Rahul Aug 11 '12 at 9:27
• $\pi M=M\pi$ is $M=\pi^{-1}M\pi$ – aska langley Aug 11 '12 at 9:36
• I am not yet clear, can you please elaborate. How do we get the adjacency matrix of permuted graph? – DurgaDatta Aug 11 '12 at 9:36

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$.
• 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. – Rahul Aug 11 '12 at 10:03
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.
• actually my doubt was in how did you write $f(\sigma G) = \pi f(G) \pi^{-1}$ – DurgaDatta Aug 11 '12 at 9:49