How many k × k magic squares are possible? If you start from a liberal definition of magic square, there’s an elegant result. For the purposes of this post, a magic square is a square arrangement of non-negative numbers such that the rows and columns all sum to the same non-negative number m called the magic constant. Note that this allows the possibility that numbers will be repeated, and this places no restriction on the diagonals.
With this admittedly non-standard definition, the number of k × k magic squares with magic constant m is always a polynomial in m of degree no more than (k – 1)2. For k = 3, the result is
(m + 1)(m + 2)(m2 + 3m + 4)/8
There is no general formula for all k, but there is an algorithm for finding a formula for each value of k.
Source: The Concrete Tetrahedron
Update: I had reported the polynomial degree as k + 1, but looking back at Concrete Tetrahedron, that book lists the order as (k + 1)2. However, the paper cited in the comments lists the exponent as (k – 1)2, which I believe is correct.
Somewhat tangentially related, Steve Gibson has cooked up a neat personal encryption algo using Latin Squares… no computer required:
http://www.grc.com/sn/sn-315.htm
It’s worth listening to the podcast as I think he does a really good job explaining some of the combinatorial math.
-JD
Are you sure about the max exponent? This paper from the Monthly by Beck et. al http://arxiv.org/PS_cache/math/pdf/0201/0201013v3.pdf gives the maximum exponent as (n – 1)^2. (What you call magic squares, they call semi-magic.) The exponent of (n – 1)^2 sort of intuitively makes sense as you are counting lattice points in an (n – 1)^2 dimensional polytope (you have n^2 variables and 2n – 1 constraints).
Thanks for updating the result. You seem to have inadvertently demonstrated the evil of typos in math books. I suspect that your reasoning (probably not conscious reasoning) was to note that (n + 1)^2 did not match the example but n + 1 did, so you automatically corrected it by dropping the square. It is the same instinct that makes debugging code difficult (you see what you think was written, not what is actually written.)
Looking at the “Concrete Tetrahedron” on google books the discussion of magic squares seems to be an aside, but typos in the text can be very annoying, see the amazon reviews for Bickel and Doksum’s Mathematical Statistics as an example (I am told that they have fixed the typos in a more recent printing, and it is a good book otherwise.)
I don’t think you can tell the number of magic squares in a certain order that much surely, with the exception of order 4×4, 5×5 like that.
For instance I can create 6.87×10 power 2210 different 8×8 magic square from just one method only. I can create 8×8 magic squares in about 25 different methods.
@Mahesh The Ehrhart polynomial for 8×8 magic squares (with magicness as defined above) is given here as H_8(t). The magic constant is given here by t.
Note that (m + 1)(m + 2)(m2 + 3m + 4)/8 = T(T(m+1)) where T(m) denotes the m’th triangular number.
By, the way, where would one find a proof of this fact ?
@xyz Probably the best place for understanding this is “Computing the Continuous Discretely’ by Beck and Robins. It is available online at http://math.sfsu.edu/beck/ccd.html . Unfortunately, there is too much machinery behind it to explain in a blog comment (neither the particular result or the general Ehrhart polynomial theory are difficult though)
Yes, I did look it up in that book, which proves the general case.
But I was looking for an elementary proof in the special 3 X 3 case.
Anyway, thank you for replying.
There are two arrangements for a 2×2 Latin Square. But, did you know there are 6,147,9419,904,000 Latin Squares of order 7×7. Read more about it on my blog: http://www.glennwestmore.com.au/category/latin-squares/.