13
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is not "a sort of vector space", it is a vector space and you have correctly identified a basis. It has a zero element (the square of all zeros), element addition (cellwise), multiplication by a scalar, and inverses. This is a good thing to find-we know a lot about vector spaces and now it is available for this problem. I could define a new basis by the top three values and we could find the change of basis matrix to express it in my basis. $\endgroup$ – Ross Millikan May 17 '14 at 14:06
  • $\begingroup$ Leave it to the mathematician to tell me not to waffle with my terms. Yes, it is a vector space. :P $\endgroup$ – Joe Z. May 17 '14 at 14:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think really what it boils down to is that we're trying to solve a system of $2n+2$ linear equations with $n^2$ variables. That somehow gives a total of $n^2 - 2n$ required unknowns. $\endgroup$ – Joe Z. May 19 '14 at 3:23
  • $\begingroup$ @JoeZ.: I believe that is correct. The question is whether there is another place the equations repeat, so there is one more free dimension. $\endgroup$ – Ross Millikan May 19 '14 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.