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 diplomat project.
Jinhao Zhao (15 May 2018 4:00 AM, Beijing time):
Given any integer , how do you find a - matrix such that its determinant is exactly ?
We have several possible answers. Before we start, we shall ease ourselves a bit. The problem is trivial for . If we have a matrix for , we could simply switch the first two rows (assume without loss of generatlity it is not a matrix) to get one for . We can allow matrices with value and (but not , and , though for certain cases this is also viable).
This is the first solution that came into my mind. Each monic polynomial has its companion matrix. For , its companion matrix isand it turns out that .
For , set . Clearly consists of only and , and .
Inner product 1
Consider the following matrix:its determinant is . Letting solves our problem.
Inner product 2
This is a classic exercise in determinant. Let be two vectors (matrices with shape ), then . Let be the vector whose entries are all , and , then consists of only and .
It is obvious that if we have matrices for , the block-diagonal matrix has determinant . This allows us to reduce the size of matrix required for a composite number.