From a programming competition:
Construct a square matrix with $N$ rows and $N$ columns consisting of non-negative integers from $0$ to $10^{18}$, such that its determinant is equal to $1$, and there are exactly $A_i$ odd numbers in the $i$-th row for each $i$ from $1$ to $N$, or report there isn't such a matrix. $$ 2\le N \le 50; \quad 1 \le A_i \le N $$
Some examples:
$4\times 4$ matrix with $3$ odd numbers in every row. Solution: $$ \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 3 & 3 \end{bmatrix} $$
$3\times 3$ matrix with $2$ odd numbers in every row. Solution: Impossible.
$3\times 3$ matrix with $[3\,1\,3]$ odd numbers in every row, respectively. Solution: Impossible.
How I tried to solve the problem
The determinant of a matrix doesn't change if we sum a multiple of a row to another, so we could start from the identity matrix and try to build a matrix with the requested number of odd integers in every row.
But I'm not able to find an automated way to build such a matrix, and how do we know if there is a solution at all?
Thank you for any help.
You've already made a key observation, that you can start with $|I|=1$ and build from there. There are a few key invariants that will help solve this as a programming challenge:
The order of the odd counts per row do not matter, up to a sign. Interchanging the rows of a matrix flip the sign of the det. Thus looking for the odd row pattern $[3, 1, 3]$ is identical to looking for the pattern $[3, 3, 1]$ (flip the last two rows, then flip the 3s, the resulting matrix has the same det). This has the consequence that any odd pattern can be put in a canonical form, it can either be ordered (which is possible if there are at least two repeating numbers) or ordered except for the last two.
Noting that odd+odd=even, even+even=even, and odd+even=odd, any matrix you get by adding rows together can always be reduced to binary form. Simply take each element mod 2. We will keep the original matrix, but use this reduced one for comparison. Example:
$$ \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 3 & 3 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{bmatrix} $$
With these two observations, you now have a state with the combination of the matrix mod 2 and canonical row form. Note that adding rows together never decreases the row sum, we can move from state to state, starting at $I$, by trying all pairwise row sums and only keeping the new states found. This creates a directed graph that should enumerate all possible odd row combinations. I suspect that this is enough of a reduction in the problem space to solve for matrices of $N=50$.