How one can find a matrix with given condition?

Jaakko Seppälä
67 ●5 ●10 ●19

slelievre
17809 ●22 ●163 ●352 http://carva.org/samue...

I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?

Consider a $4\times 4$ matrix with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$ . Now form four sets $A_1$ , $A_2$ , $A_3$ , $A_4$ . Say that $A_1$ is the set of elements $a_{i,j}$ . Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$ i.e. the set of sums of elements of $2\times 2$ -subsquares of the matrix. Similarly, denote by $A_3$ the set of sums of $3\times 3$ -submatrices and $A_4$ the set containing the sum of all elements of the given $4\times 4$ -matrix.

Now, I heard a rumor that one can give an example of 16 integers $a_{i,j}$ such that all integers from 1 to 25 belong to $A_1 \cup A_2 \cup A_3 \cup A_4$ . How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there are still so many elements that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithms or simulated annealing work for such a problem but I don't have enough experience to implement that.

The best I know is that getting all integers from 1 to 24 is possible, for instance using the matrix:

-42  22  23   7
 13  11 -32  14
-23  16  15   8
 19   9 -22   1

answered 4 years ago

Max Alekseyev

7073 ●10 ●59 ●173

updated 4 years ago

Here is a matrix you want:

-21 -20 20 11 
6 2 8 -25 
5 4 9 15 
1 12 -22 16

I found it by first selecting at which $25$ squares we get values $\{1,2,\dots,25\}$ (there are $\binom{30}{25}=142506$ ways to make such a selection), and then by solving an Integer Linear Programming problem.

In our ILP, we introduce integer variables $a_{u,v}$ ( $u,v=1,2,3,4$ ) denoting the matrix elements, and let $S_i$ be the sums of those elements in the $i$ -th selected square ( $i=1,\dots,25$ ). Essentially we want $(S_1,S_2,\dots,S_{25})$ be a permutation of $\{1,2,\dots,25\}$ . For this purpose, we introduce binary indicator variables $p_{i,j}$ ( $i,j=1,\dots,25$ ) telling whether $S_i = j$ , and constraints: $\begin{cases} S_i = \sum_{j=1}^{25} p_{i,j} j,\\ \sum_{j=1}^{25} p_{i,j} = 1, \end{cases} \qquad\text{for }i=1,2,\dots,25$ and $\sum_{i=1}^{25} p_{i,j} = 1\qquad\text{for }j=1,2,\dots,25.$ The solution above was obtained on the $1617$ -th selection of squares, within just a few minutes of running my Sage code.

PS. Another solution:

9 3 6 5 
8 1 4 10 
11 2 16 -23 
19 -15 12 13

PS2. There even exists a matrix delivering sums $\{0,1,2,\dots,25\}$ , for example:

0 6 21 4 
9 7 -24 17 
14 -25 11 8 
16 15 1 3

However, the sums $\{1,2,3,\dots,26\}$ are not possible to obtain.

link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

How one can find a matrix with given condition?

1 Answer

Your Answer

Question Tools

Stats

Related questions

How one can find a matrix with given condition? savecancel

1 Answer

Your Answer

Question Tools

Stats

Related questions

How one can find a matrix with given condition?