Automorphisms

An automorphism of a graph $\Gamma$ is a permutation $\pi$ of its point set $X$ such that $x \,\sim\,y$ if and only if $\pi (x) \,\sim\,\pi (y)$. Given $\pi$, we have a linear transformation $P_\pi$ on $V$ defined by $(P_\pi (u))_x = u_{ \pi (x) }$ for $u \in V$, $x \in X$. That $\pi$ is an automorphism is expressed by $AP_\pi = P_\pi A$. It follows that $P_\pi$ preserves the eigenspaces $V_\theta$ of $A$.

(More generally, if $G$ is a group of automorphisms of $\Gamma$ then we find a linear representation of degree $m( \theta ) = \dim V_\theta$ of $G$.)

We denote the group of all automorphisms of $\Gamma$ by ${\rm Aut}\ \Gamma$. One would expect that when ${\rm Aut}\ \Gamma$ is large, then $m ( \theta )$ tends to be large, so that $\Gamma$ 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 $\dim V_\theta = 1$, say $V_\theta = <u>$. Since $P_\pi$ preserves $V_\theta$ we must have $P_\pi u = \pm u$. So either $u$ is constant on the orbits of $\pi$, or $\pi$ has even order, $P_\pi (u) = -u$, and $u$ is constant on the orbits of $\pi^2$. For the Perron-Frobenius eigenvector we are always in the former case.

Corollary 1.6.1   If all eigenvalues are simple, then ${\rm Aut}\ \Gamma$ is an elementary abelian 2-group.

Proof:    If $\pi$ has order larger than two, then there are two distinct vertices $x$, $y$ in an orbit of $\pi^2$, and all eigenvectors have identical $x$- and $y$-coordinates, contradiction. $\Box$

Corollary 1.6.2   Let ${\rm Aut}\ \Gamma$ be transitive on $X$. (Then $\Gamma$ is regular of degree $k$, say.)

1. If $m( \theta ) = 1$ for some eigenvalue $\theta \ne k$, then $v = \vert X \vert$ is even, and $\theta \equiv k$ $( {\rm mod}\ 2 )$. If ${\rm Aut}\ \Gamma$ is moreover edge-transitive then $\Gamma$ is bipartite and $\theta = - k$.

2. If $m( \theta ) = 1$ for two distinct eigenvalues $\theta \ne k$, then $v \equiv 0$ $( {\rm mod}\ 4 )$.

3. If $m( \theta ) = 1$ for all eigenvalues $\theta$, then $\Gamma$ has at most two vertices.

Proof:     (i) Suppose $V_\theta = <u>$. Then $u$ induces a partition of $X$ into two equal parts: $X = X_+ \cup X_-$, where $u_x = a$ for $x \in X_+$ and $u_x = -a$ for $x \in X_-$. Now $\theta = k - 2 \vert \Gamma (x) \cap X_- \vert$ for $x \in X_+$.

(ii) If $m(k) = m( \theta ) = m( \theta' ) = 1$, then we find 3 pairwise orthogonal $( \pm 1)$-vectors, and a partition of $X$ into four equal parts.

(iii) There are not enough integers $\theta \equiv k$ $( {\rm mod}\ 2 )$ between $-k$ and $k$. $\Box$

For more details, see Cvetkovic, Doob & Sachs [6], Chapter 5.