Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

up vote 2 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|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
add comment

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|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
add comment

Your Answer

 
discard

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.