Showing that every rational eigenvalue of a graph is integral

Question

(This is taken from the exercises in Bondy and Murty's Graph Theory.) Let the adjacency matrix of a graph $G$ be denoted by $\mathbf{A}$. The eigenvalues $\lambda$ of $G$ are defined as the roots of the characteristic polynomial of $\mathbf{A}$, $\lvert \mathbf A-\lambda\mathbf I\rvert=0$. I am asked to show that, if $\lambda\in\mathbb Q$, then $\lambda\in\mathbb Z$.

I have already managed to show that $\lambda$ is real. This is because $\mathbf A$ is symmetric by definition, then it becomes a simple linear algebra fact that its eigenvalues are real. Then, if $G$ is simple, all diagonal entries of $\mathbf A$ are $0$, and since the eigenvalues of a matrix have the same signs as the diagonal entries (I hope!) then all the eigenvalues are $0$. However, I'm not given that $G$ is simple and so this line of reasoning doesn't work, and I have no idea where to use the fact that $\lambda$ is rational in the proof anyway. Any help is appreciated!

Answer 1

Let $\mathbf x$ be an eigenvector of a rational eigenvalue $\lambda$: that is, $(\mathbf A - \lambda \mathbf I)\mathbf x = \mathbf 0$.

First, we can argue that if $\lambda$ is rational, then the entries of $\mathbf x$ can be all rational. There's probably some clever argument here, but basically the reason is that if you solve this system of equations with Gaussian elimination, then you never introduce irrational numbers, and all the entries of $\mathbf A - \lambda \mathbf I$ start out rational.

Nest, we can assume that the entries of $\mathbf x$ are integers with greatest common divisor $1$, because we can scale $\mathbf x$ to get another eigenvector to make this the case. (Stop if you think you see where this is going.) We have $\mathbf A \mathbf x = \lambda \mathbf x$, and here at least $\mathbf A \mathbf x$ is an all-integer vector. So $\lambda \mathbf x$ is also an all-integer vector.

If $\lambda = \frac pq$ had a denominator $q$ other than $\pm 1$, then we could find an entry $x_i$ of $\mathbf x$ not divisible by $q$ (since the entries have GCD $1$), and then $\lambda x_i$ would not be an integer. Since we know this doesn't happen, $\lambda$ must be an integer.

Answer 2

More generally, if $A$ is a square matrix whose entries are integers, the characteristic polynomial of $A$ is a monic polynomial with integer coefficients, so the eigenvalues of $A$ are algebraic integers. Every algebraic integer that is a rational number is an ordinary integer (see e.g. here).