An automorphism of a graph is a permutation of its point set such that if and only if . Given , we have a linear transformation on defined by for , . That is an automorphism is expressed by . It follows that preserves the eigenspaces of .
(More generally, if is a group of automorphisms of then we find a linear representation of degree of .)
We denote the group of all automorphisms of by . One would expect that when is large, then tends to be large, so that has only few distinct eigenvalues. And indeed the arguments below will show that a transitive group of automorphisms does not go very well together with simple eigenvalues.
Suppose , say . Since preserves we must have . So either is constant on the orbits of , or has even order, , and is constant on the orbits of . For the Perron-Frobenius eigenvector we are always in the former case.
Proof: (i) Suppose . Then induces a partition of into two equal parts: , where for and for . Now for .
(ii) If , then we find 3 pairwise orthogonal -vectors, and a partition of into four equal parts.
(iii) There are not enough integers between and .
For more details, see Cvetkovic, Doob & Sachs , Chapter 5.