6

(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!

YiFan Tey
  • 17,431
  • 4
  • 28
  • 66
  • The eigenvalues of a matrix do not necessarily have the same signs as the diagonal entries. – Misha Lavrov Sep 30 '18 at 04:15
  • I remember learning about something like that in linear algebra... Or is it only true for a tridiagonal matrix or something? – YiFan Tey Sep 30 '18 at 04:31
  • The characteristic polynomial $\det(t I-A)\in\mathbb{Z}[t]$ is monic, so ... – user10354138 Sep 30 '18 at 04:34
  • You can argue that for a symmetric matrix $A$, if some of the diagonal entries are negative, then the eigenvalues can't all be positive (or vice versa), which might be what you're thinking of. But that's a much weaker claim. – Misha Lavrov Sep 30 '18 at 04:42
  • I see, thanks. I will update the question to reflect that. – YiFan Tey Sep 30 '18 at 04:48

2 Answers2

7

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.

Misha Lavrov
  • 142,276
5

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

Robert Israel
  • 448,999