Given a graph G with adjacency matrix A, the set of automorphisms of G is precisely those permutations which preserve every eigenspace of A.

Suppose we examine the restriction of the permutation-matrix representation of the automorphic group to one such subspace. Should one expect this restriction to be reducible or irreducible?

I would like to ignore in this respect the graph with only self-loops, which has only one eigenspace, and the automorphic group, which is all of S_n is reducible to a trivial, and a (n-1)-degree irreps.


For most graphs the automorphism group is trivial, and so any eigenspace of dimension greater than two is reducible. Also the eigenspaces of a vertex-transitive graph cannot all be 1-dimensional (see e.g. Biggs's "Algebraic Graph Theory") and if $d\ge5$, there are Cayley graphs for $\mathbb{Z}_2^d$ with full automorphism group $\mathbb{Z}_2^d$ (but this is quite non-trivial).

To get examples where the eigenspaces are irreducible, look at distance-transitive graphs. The line graphs of the complete graphs for example. (I am not saying that, for distance-transitive graphs, the eigenspaces will always be irreducible.)

| cite | improve this answer | |

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.