How many matrices with integer eigenvalues are there?

Solution 1:

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.