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 nn, how do you find a 00-11 matrix such that its determinant is exactly nn?

We have several possible answers. Before we start, we shall ease ourselves a bit. The problem is trivial for n=0n=0. If we have a matrix for nn, we could simply switch the first two rows (assume without loss of generality it is not a 1×11\times 1 matrix) to get one for n-n. We can allow matrices with value 00 and 1-1 (but not 00, 11 and 1-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(x)=a0++an1xn1+xnp\left(x\right)=a_0+\cdots+a_{n-1}x^{n-1}+x^n, its companion matrix isA=(000a0100a1010a2001an1),\CompanionMatrixand it turns out that det(λIA)=p(λ)\det\left({\lambda I-A}\right)=p\left(\lambda\right).

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

Inner product 1

Consider the following matrix:(1x1x2xny1100y2010yn001),\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 1x1y1xnyn1-x_1y_1-\cdots-x_ny_n. Letting x1==yn=1x_1=\cdots=y_n=1 solves our problem.

Inner product 2

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

Getting smaller

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

Please enable JavaScript to view the comments powered by Disqus.