Constructing an integer matrix with given determinant and "small" entries?

I wish to construct an $n\times n$ integer matrix $M$ with a given determinant $D$. Of course, this is trivial---I can factor $D$ into $n$ arbitrary terms and place them on the diagonal, for instance. But I want a solution with $\|M\|_\max$ small.

Since $D \leq n!\,\left(\|M\|_\max\right)^n$, I'm hoping for a solution where the entries of $M$ have magnitude about $D^{1/n}.$ Is there an easy way to construct such an $M$? (Does it help if $D$ is prime?)

Solution 1:

WOLOG, let's consider the case $D > 0$.

Let $b = \left\lceil (D+1)^{1/n}\right\rceil$.

Since $b \ge (D+1)^{1/n} \implies b^n > D$, there are $n$ non-negative integers $a_0,\ldots,a_{n-1} < b$ such that

$$D = \sum_{k=0}^{n-1} a_k b^k$$ Let $p(t)$ be the polynomial $t^n + (a_{n-1} - b) t^{n-1} + \sum\limits_{k=0}^{n-2} a_k t^k$ and $C_p$ be its companion matrix,

$$C_p = \begin{bmatrix} 0 & 0 & \cdots & 0 & -a_0\\ 1 & 0 & \cdots & 0 & -a_1\\ 0 & 1 & \cdots & 0 & -a_2\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 0 & -a_{n-2}\\ 0 & 0 & \cdots & 1 & b - a_{n-1} \end{bmatrix}$$ It is well known the characteristic polynomial of $C_p$ is $p(t)$.

$$p(t) = \det(tI_n - C_p)$$ Substitute $t$ by $b$, we get

$$D = p(b) = \det(bI_n - C_p) = \left|\begin{matrix} b & 0 & \cdots & 0 & a_0\\ -1 & b & \cdots & 0 & a_1\\ 0 & -1 & \cdots & 0 & a_2\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & b & a_{n-2}\\ 0 & 0 & \cdots & -1 & a_{n-1} \end{matrix}\right|$$ $D$ is the determinant of an integer matrix whose entries falls between $-1$ and $b$ (inclusive).

Solution 2:

Here's a suggestion that should work in practice: note that the determinant of the matrix $$ \begin{pmatrix} a_1 & b_1 & 0 & 0 & \cdots & 0 \\ 0 & a_2 & b_2 & 0 & \cdots & 0 \\ 0 & 0 & a_3 & b_3 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & a_{n-1} & b_{n-1} \\ b_n & 0 & 0 & \cdots & 0 & a_n \end{pmatrix} $$ is equal to $a_1a_2\cdots a_n-(-1)^nb_1b_2\cdots b_n$. Consider all choices of the $a_j$ between $C$ and $E$ where $C$ is just a bit less than $D^{1/n}$ and $E$ is just a bit more. Make the choices so that $a_1a_2\cdots a_n$ is as close to $D$ as possible and is greater than $D$ when $n$ is even / less than $D$ when $n$ is odd. Then hopefully $|a_1a_2\cdots a_n-D|$ is so small that a trivial factorization of it into $b_1b_2\cdots b_n$ will suffice.