Find a 0-1 matrix whose determinant is a given integer

This entry is pre-recorded, and only revealed after the problem has been consumed by the designated competition. Gee Law is currently busy doing his diploma project.

Jinhao Zhao (15 May 2018 4:00 AM, Beijing time):

Given any integer $n$, how do you find a $0$-$1$ matrix such that its determinant is exactly $n$?

We have several possible answers. Before we start, we shall ease ourselves a bit. The problem is trivial for $n=0$. If we have a matrix for $n$, we could simply switch the first two rows (assume without loss of generality it is not a $1\times 1$ matrix) to get one for $-n$. We can allow matrices with value $0$ and $-1$ (but not $0$, $1$ and $-1$, though for certain cases this is also viable).

Companion matrix

This is the first solution that came into my mind. Each monic polynomial has its companion matrix. For $p\left(x\right)=a_0+\cdots+a_{n-1}x^{n-1}+x^n$, its companion matrix is$\CompanionMatrix$and it turns out that $\det\left({\lambda I-A}\right)=p\left(\lambda\right)$.

For $n>0$, set $p\left(x\right)=-x-x^3-\cdots-x^{2n+1}+x^{2n+3}$. Clearly $\left({-I-A}\right)$ consists of only $0$ and $-1$, and $\det\left({-I-A}\right)=p\left({-1}\right)=n$.

Inner product 1

Consider the following matrix:$\begin{pmatrix}1&x_1&x_2&\cdots&x_n\\y_1&1&0&\cdots&0\\y_2&0&1&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\y_n&0&0&\cdots&1\end{pmatrix},$its determinant is $1-x_1y_1-\cdots-x_ny_n$. Letting $x_1=\cdots=y_n=1$ solves our problem.

Inner product 2

This is a classic exercise in determinant. Let $x,y$ be two vectors (matrices with shape $n\times 1$), then $\det\left({I+xy^{\mathrm{T}}}\right)=1+x^{\mathrm{T}}y$. Let $x$ be the vector whose entries are all $1$, and $y=-x$, then $I+xy^{\mathrm{T}}$ consists of only $0$ and $-1$.

Getting smaller

It is obvious that if we have matrices $A,B$ for $m,n$, the block-diagonal matrix $\mathrm{diag}\left({A,B}\right)$ has determinant $mn$. This allows us to reduce the size of matrix required for a composite number.