If you are looking for a more abstract proof based on representation and group theory, I suggest you to work on a more general question as follows:

Assume that $G=\langle S\rangle$ is a finite group which is generated by $S=S^{-1}$ ($1\not\in S$) such that for every complex representation $\phi$ of G the matrix $\sum_{s\in S} \phi(s)$ has only rational eigenvalues. Then is $|G|$ bounded above by a function of $|S|$?

The answer to the above question is positive and a crude known bound is
$\frac{|S|(|S| − 1)^{2|S|} − 2}{|S| − 2}$.

Note that, what you need by the representation theoretic assumption is that the eigenvalues of the linear transformation $T=\sum_{s\in S}s$ on the vector space $\mathbb{C}(G)$ are all rational (and so integer). Note that $T$ is an element of the group ring $\mathbb{C}(G)$.

You may find some related graph theoretic results in the following paper:

Alireza Abdollahi and E. Vatandoost, Which Cayley graphs are integral?, The Electronic Journal of Combinatorics 16 (2009), #R122.

Sorry for the self-promotion!

11more comments