0

If I have a $4\times 4$ square where all the rows columns and $2$ main diagonals must sum to a specific given value (same in each case), what's the minimum number of squares that are required to be filled in before there's only one possible way to fill in the remaining squares. Here the values in each square can be any integer, positive or negative.

I know how to pick $8$ squares so that the rest can be determined but I don't know how to pick $7$ squares.

blademan9999
  • 796
  • 1
    We are given 10 linear equations, so we can generally solve for 10 unknowns, hence we ought to fill no more than 6 squares. – RSpeciel Jul 30 '20 at 16:08
  • @blademan9999: Do you mean that all row, column, and diagonal sums have the same given value $s$, or that they have $10$ maybe different given values? – Christian Blatter Jul 31 '20 at 18:03
  • @RomainS: there is one redundancy between the equations, because the sum of the four row equations equals the sum of all the numbers in the square equals the sum of the four column equations. That should say we need $7$ numbers, not $6$. – Ross Millikan Aug 01 '20 at 03:38
  • @ChristianBlatter: I think the question says it is always the same $s$ and that it is known. In that case your answer applies. – Ross Millikan Aug 01 '20 at 03:39

1 Answers1

0

Let $A=\bigl[a_{ik}\bigr]$ be the unknown $(4\times4)$-matrix in question. Given that the $10$ described sums all have the same value $s$ we have a system ${\cal S}$ of $10$ linear equations in the $16$ unknown variables $a_{ik}$. The $(10\times16)$-matrix $M$ (all entries are $0$ or $1$) of this system has only rank $9$. In fact the four rows of $M$ corresponding to the four rows of $A$ sum to $(1,1,\ldots,1)$, as do the next four rows of $M$ corresponding to the four columns of $A$. The rank of $M$ could be even smaller because we do not really understand the influence of the two rows of $M$ corresponding to the main diagonals of $A$.

When believe in ${\rm rank}(M)=9$ then we can argue as follows: Setting up for ${\cal S}$ a Gaussian reduction process for the $16$ unknowns $a_{ik}$ will in the end present $9$ of these unknowns as functions of the $7$ others. A non resolvable case cannot result when all row and column sums have the equal value $s$.

According to the algorithm of the calculation we therefore can choose the values of $7$ suitable $a_{ik}$, and we have to make all these choices in order to determine the $16$ $a_{ik}$ completely. I solved the system with Mathematica. Here is the system:

enter image description here

And these are the solutions:

enter image description here

You see that $9$ variables $a_{ik}$ appear as functions of the seven others and $s$. Which variables are the "free" ones depends on the algorithm of the solver. Here the variables $a_{11}$, $a_{12}$, $a_{13}$, $a_{21}$, $a_{22}$, $a_{23}$, $a_{31}$ are "free".

Christian Blatter
  • 226,825
  • And what are these 7 suitable $a_{ik}$? – blademan9999 Jul 31 '20 at 04:56
  • @blademan9999 This answer assumes that the sums of the 10 lines are known. If they are not known, but are known to be equal to a single magic constant, then you have in effect an extra unknown variable in your system. That means that 8 given cells is the minimum to determine the magic square. – Jaap Scherphuis Jul 31 '20 at 13:56