How many matrices with integer eigenvalues are there? 
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.
 A: 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.
