If I wanted to describe it as a minimum problem, where I want to identify the minimum value of the constant for a certain matrix order, how should I do it?
2 Answers
$\begingroup$
$\endgroup$
Before we find a function to minimize, we should first find some equalities that determine whether a grid $(a_{ij})$ is a magic square. First off, a magic square has the restriction that the entries $a_{ij}$ are some permutation of $1$ to $n^2$.
Here's a trick to ensure that: We just need to ensure that the polynomial $(X-a_{11}) \cdot (X-a_{12}) \cdots (X-a_{nn})$ is the same as the polynomial $(X-1)\cdot (X-2) \cdots (X-n^2)$. If two polynomials are equal, all their coefficients are equal, so just expand the polynomial in X to get coefficient-wise equalities in $a_{11} \ldots a_{nn}$.
Here's an example for $n = 2$ (I know there aren't any $n=2$ magic squares, but for demonstration purposes): Let's say the magic square is $\begin{pmatrix}a&b\\c&d\end{pmatrix}$. Then the polynomial identity is
$(X-a)(X-b)(X-c)(X-d) = (X-1)(X-2)(X-3)(X-4)$. Expanding both sides yields
$$X^4+(-a-b-c-d)X^3+(ab+ac+ad+bc+bd+cd)X^2\\+(-abc-abd-acd-bcd)X+abcd = X^4-10X^3+35X^2-50X+24$$.
Comparing coefficients, we get the following four equations: $$a+b+c+d=10$$ $$ab+ac+ad+bc+bd+cd=35$$ $$abc+abd+acd+bcd=50$$ $$abcd=24$$
The left sides of these equalities are known as elementary symmetric polynomials.
So far, so good. Now we still need to ensure that the square is magic, i.e. that the rows, columns and diagonals are equal. That's more simple, we can just write down a set of equalities for that.
In the case of the magic square $\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}$, the equations are just $$a+b+c=d+e+f=g+h+i=a+d+g=b+e+h+c+f+i=a+e+i=c+e+g$$
Simple. Now that we have found a way to describe magic squares as a system of equations, we can make it an optimization problem by the following procedure:
For each equality $x = y$ , consider the quadratic difference $(x-y)^2$. The equalities are all true if and only if the sum of the quadratic differences is minimal (i.e. zero). Let's try to construct a minimization problem for $n = 2$ (again, I know there are no $n=2$ magic squares):
Our equalities are $$a+b+c+d=10$$ $$ab+ac+ad+bc+bd+cd=35$$ $$abc+abd+acd+bcd=50$$ $$abcd=24$$ $$a+b=c+d$$ $$a+b=a+c$$ $$a+b=b+d$$ $$a+b=a+d$$ $$a+b=b+c$$
Together, the term we need to minimize is as follows:
$$(a+b+c+d-10)^2+(ab+ac+ad+bc+bd+cd-35)^2+(abc+abd+acd+bcd-50)^2+(abcd-24)^2+(a+b-c-d)^2+(a+b-a-c)^2+(a+b-b-d)^2+(a+b-a-d)^2+(a+b-b-c)^2$$
You might complain that the elementary symmetric polynomials start having a large amount of terms quickly, and you'd be right. Instead of the elementary symmetric polynomials, an equivalent set of equalities is the following power sums (which I won't prove though):
$$a_{11}^1 + a_{12}^1 + \ldots + a_{nn}^1 = 1^1+\ldots+(n^2)^1$$ $$a_{11}^2 + a_{12}^2 + \ldots + a_{nn}^2 = 1^2+\ldots+(n^2)^2$$ $$\vdots$$ $$a_{11}^{n^2} + a_{12}^{n^2} + \ldots + a_{nn}^{n^2} = 1^{n^2}+\ldots+(n^2)^{n^2}$$
This should make the final term much more easy to write down.
$\begingroup$
$\endgroup$
2
Suppose there is an $n$ X $n$ square; so clearly it has $n^2$ numbers: from $1$ to $n^2$. Also, let $K$ be the magic constant.
Since this is a magic square, the sum of each row, column and diagonal are equal. For our purpose, let's consider the row-sums only. Since there are $n$ rows which contain all the numbers from $1$ to $n^2$ exactly once, the sum of $n$ rows will equal the sum of numbers from $1$ to $n^2$. This will also equal to the magic constant $K$ times $n$. In other words:
$ 1 + 2 + 3 + ... + n^2 = nK $
so, $\frac{n^2(n^2+1)}{2} = nK$
so, K = $\frac{n(n^2+1)}{2}$
This holds true for all $ n \neq 2 $
