What is the fewest number of filled-in squares required to uniquely define a magic square?

Question

The magic square is a well-known grid of the numbers from 1 to 9 in which every row, column, and diagonal adds up to 15:

4 9 2
3 5 7
8 1 6

But it is also possible to create magic squares using other numbers:

24 87 45
73 52 31
59 17 80

It's also known that given just a few filled-in squares, you can determine the rest logically. For example, given the partially filled-in grid:

8 9 .
. 6 .
. 3 .

you can immediately infer that the rows, columns, and diagonals add up to 18, and so the bottom-right square is 4 and the top-right square is 1:

8 9 1
. 6 .
. 3 4

Then the right square is 13 and the bottom-left square is 11:

 8 9  1
 . 6 13
11 3  4

And finally, in a slightly uncouth twist, the left square is -1.

 8  9  1
-1  6 13
11  3  4

But in fact, it's possible to create a set of filled-in numbers that don't have any completed rows at all and still be able to fill the rest of the numbers in:

12 .. 27
.. ..  6
.. 18 ..

This, as it turns out, has a (unique) solution of:

12 24 27
36 21  6
15 18 30

So what is the fewest number of filled-in squares that are actually possible to derive the whole square from, and what arrangement are they in? And what about the case of higher-order magic squares?

Answer 1

It turns out that the magic squares form a vector space. You can add them (by adding each corresponding entry), multiply them by scalars (by multiplying every entry by the same number), and invert them (take the negative of each entry) around a zero element (the magic square where everything is zero), and they will still stay magic squares.

And this vector space has a basis of size three, as follows:

 0 -3  0     0  2  1     1  2  0
-1 -1 -1  ,  2  1  0  ,  0  1  2
-2  1 -2     1  0  2     2  0  1

This means that given any three constants a, b and c, you can define the following magic square:

          c,   2b + 2c - 3a,             b
     2b - a,      b + c - a,        2c - a
b + 2c - 2a,              a,   2b + c - 2a

where the magic constant is 3b + 3c - 3a.

The classical (Lo Shu) magic square has a = 1, b = 2, and c = 4.

So if you are given three numbers in the V shape (or its reflections and rotations):

xx .. ..
.. .. xx
xx .. ..

then you can make a magic square out of it. In fact, as long as you're given any three positions so that for each position, when you take the number in that position from each square in the basis and form a vector out of it, you end up with three linearly independent vectors, then you can still uniquely determine a magic square out of it by solving a system of linear equations.

---

I don't know anything about the higher-order squares, though. That can be left for another answer.

Answer 2

I believe (and can almost prove) that for an $n \times n$ square you need $(n-1)^2-1=n^2-2n$ givens. First, let us ignore the requirement that the diagonal sums match the row/column sums. Then you can fill the upper $(n-1) \times (n-1)$ grid however you want. If you pick the upper right element, you can calculate the row sum $R.$ The last element of the next $n-2$ rows is now fixed, as is the bottom element in the first $n-1$ columns. If $S$ is the sum of the original set of entries, the sum of the elements in the last column so far is $(n-1)R-S$, as is the sum of the elements in the last row, so you pick the lower right to be $R-((n-1)R-S)=S-(n-2)R$. This shows there are $(n-1)^2+1$ free elements in a square where the rows and columns have a common sum.

The diagonals introduce two constraints, so you would expect to subtract two from this count for fully magic squares. This would give $(n-1)^2-1$ as the number of free elements, in agreement with Joe Z's calculation for $3 \times 3$. I have not found a way to show these constraints are not redundant in the general case, but it seems unlikely.

The $n \times n$ matrices form a vector space, and I am counting the dimension of the subspace that is magic.