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

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.

share|cite|improve this question

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

share|cite|improve this answer

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.