Can we arrange $\{1,...,16\}$ in $4\times 4$-grid so {products of rows} = {products of columns}?

My motivation is the following question asked by Jacob Steiner, which he then deleted. For which $n\in\Bbb N$ is it possible to arrange $\{1,\ldots,n^2\}$ in an $n\times n$-grid so that the set of products of columns equals the set of products of rows?

The answer for $n=2$ is clearly No, since the only possibility, up to a transposition and a permutation of rows and columns, is

1 2 
3 4 

Since the set of products of rows are $\{2,12\}$ and the set of products of columns are $\{3,8\}$, this arrangement does not work. So for $n=2$, it is not possible to make such an arrangement.

Solution 1:

Here's a solution for $n=4$, with products 6240, 672, 2520, and 1980:

13 16  3 10 
 4  6 14  2 
 8  7  5  9 
15  1 12 11 

$n=5$:

17  2  7 15 20 
14 25  9 11 16 
 6 21 13  3 12 
10 22 18 23  1 
 5 24  4  8 19 

$n=6$:

34 10  5 30 27 14 
25 19 36 11  7  2 
18 33 29  4 20  8 
 3 35 22 31 32  9 
15 12 16 21 17 26 
28  1  6 24 13 23 

I used the following integer linear programming formulation. Let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ has value $k$. You can use any objective function, and the constraints are: \begin{align} \sum_k x_{i,j,k} &= 1 &&\text{for all $i, j$}\\ \sum_{i,j} x_{i,j,k} &= 1 &&\text{for all $k$}\\ \sum_{j,k} \log(k) x_{t,j,k} &= \sum_{i,k} \log(k) x_{i,t,k} &&\text{for all $t$} \end{align} The first constraint forces each cell to contain exactly one value. The second constraint forces each value to appear in exactly one cell. The third constraint forces row $t$ and column $t$ to have the same product.

Solution 2:

Not an answer, but pointing out a flaw in the OP logic.

If a prime factor appears singly (i.e. not squared) an odd number of times (like $5$ appearing as $\{5, 10, 15\}$ in the $4\times 4$ grid), that does not imply one of the appearances must be along the diagonal. E.g.

* 10  *  *
*  * 15  *
5  *  *  *
*  *  *  *

would meet the requirement as far as factors of $5$ are concerned: the first $3$ rows and the first $3$ columns each has exactly one factor of $5$ (and the last row and last column has no factor of $5$).

(These positions represent a (fixed-point-free) permutation in the $3 \times 3$ submatrix.)

UPDATE: Indeed Rob Pratt found such a matrix:

$$ \begin{matrix} 9 &15 &12 &1\\ 3 &11 &14 &5\\ 6 &7 &13 &16\\ 10 &2 &4 &8\end{matrix} $$

where the positions of the multiples of $5$ represent a fixed-point-free permutation of the $3\times 3$ submatrix after deleting the $3$rd row & column.

So the OP claim that the $4\times 4$ grid must have a factor of $5$ along the diagonal is wrong, and similarly, it is still unproven that $8 \times 8$ cannot be filled because that last $X$ does not need to be any multiple of $11, 17, 19$.