2
$\begingroup$

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.

1 Answers 1

5

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