Let $m,n \in \mathbb N$. How many $m \times m$ matrices with integer entries from $-n$ to $n$ have the property that all eigenvalues (possibly multiple) are integers?
The following table calculated with PARI shows the values for $m = 2$ and $n = 1,\dots,20$:
1 55
2 317
3 963
4 2301
5 4315
6 7793
7 12047
8 18449
9 26527
10 37325
11 48683
12 66149
13 82547
14 104713
15 131247
16 162297
17 191599
18 233813
19 270939
20 324045
For $m = 3$, I only know the values for $n = 1,2$:
1 6417
2 260353
3 2570569
Brute force method is soon not feasible. A formula depending on $m$ and $n$ would be nice.
Let $C(m,n)$ be the number of matrices with specified properties. Here's a lower bound:
Let $\mathbf{B}$ be a $(m-1) \times (m-1)$ matrix with integer entries in the range $-n$ to $+n$ and integer eigenvalues. This means that $\det(\mathbf{B}-\lambda \mathbf{I}_{m-1}) = 0$ only has integer solutions. Consider now the matrix
$ \mathbf{A} = \begin{pmatrix} a_1 & a_2 & a_3 & \cdots \\ 0 & B_{11} & B_{12} & \cdots \\ 0 & B_{21} & B_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} $
where $|a_k| \leq n$ are also integers. Using the Laplace/cofactor expansion, $\det(\mathbf{A}-\lambda \mathbf{I}_{m}) = (a_1-\mu) \det(\mathbf{B}-\lambda \mathbf{I}_{m-1})$. Thus, the eigenvalues of $\mathbf{A}$ are $a_1$ and all eigenvalues of $\mathbf{B}$. There are $(2n+1)^m$ ways of choosing the $a_k$ and each choice gives a unique $\mathbf{A}$. In conclusion:
$C(m,n) \geq (2n+1)^m C(m-1,n)$
The elements $a_k$ could alternatively have been added as the last row, the first column, or last column. But then it is more tedious to take care of all possible double counting since not quite all $\mathbf{a}$'s and $\mathbf{B}$'s result in a unique $\mathbf{A}$ in this case. I don't think the above bound is very tight, though, so it is probably safe to include a factor of 4 on the RHS of the bound.
PS. I would've made this a comment since it's just a bound, but apparently my rep is too low.