Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve this answer
actually my doubt was in how did you write $f(\sigma G) = \pi f(G) \pi^{-1}$ – DurgaDatta Aug 11 '12 at 9:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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