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?)
 A: 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).
A: 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.
