4x4 magic/semi-bimagic square
impossibility proof
by Lee Morgenstern, August 2009.
In order to prove that no 4x4 magic square of distinct integers can be semi-bimagic, we need a complete solution for a 4x4 magic square.
Suppose this is a 4x4 magic square.
A B C
D
E F G H
I J K L
M N P Q
We must have
A+B+C+D = A+F+K+Q
B+F+J+N = M+N+P+Q
C+G+K+P = D+G+J+M
Adding these equations and
cancelling terms
[1] B+C = M+Q
and by symmetry
[2] E+I =
D+Q
[3] P+N = A+D
[4] L+H = A+M
We must have
E+F+G+H = I+J+K+L
A+E+I+M = A+F+K+Q
D+H+L+Q = D+G+J+M
Adding these equations
produces
[5] E+H = J+K
and by symmetry
[6] B+N = G+K
[7] L+I = F+G
[8] C+P = F+J
A+B+C+D = B+F+J+N
M+N+P+Q =
C+G+K+P
A+F+K+Q = D+G+J+M
produces
[9] A+Q = G+J
and by
symmetry
[10] D+M = F+K
From [1], B = M+Q-C
From [7], I =
F+G-L
From [8], P = F+J-C
From [9], A = G+J-Q
From [10], D =
F+K-M
From [2], E = Q+D-I
and combined with
[7],[10], E = K+L+Q-G-M
From [4], H = A+M-L
and combined with [9],
H = G+J+M-L-Q
From [6], N = K+G-B
and combined with [1], N =
C+G+K-M-Q
Thus any 4x4 magic square can be represented by the following form. Also, you will find that the sum of every row, column, and diagonal is F+G+J+K. As a result, any assignment of the variables C,F,G,J,K,L,M,Q in this form will produce a 4x4 magic square. Therefore, this is a complete solution.
+-----------+-----------+-----------+-----------+
| G+J-Q | M+Q-C
| C | F+K-M |
+-----------+-----------+-----------+-----------+
| K+L+Q-G-M | F
| G | G+J+M-L-Q |
+-----------+-----------+-----------+-----------+
| F+G-L | J
| K | L |
+-----------+-----------+-----------+-----------+
| M | C+G+K-M-Q
| F+J-C | Q |
+-----------+-----------+-----------+-----------+
Part 2 of 3
Semi-Bimagic
Formulation
Scaling and translating does not affect the magic conditions of a magic square or any bimagic lines. We can use this to simplify the formulation.
Suppose we have a solution with distint entries and, in particular, G and L are different. Translate so that the L entry becomes 0. Then scale so that the G entry, which is still not 0, becomes 1.
We will then have a representation for a 4x4 magic square of rational numbers which can be scaled and translated back to positive integers. This representation eliminates two of the variables.
[c1] [c2] [c3]
[c4]
+-----------+-----------+-----------+-----------+
[r1]
| 1+J-Q | M+Q-C | C | F+K-M |
+-----------+-----------+-----------+-----------+
[r2] | K+Q-1-M |
F | 1 | 1+J+M-Q |
+-----------+-----------+-----------+-----------+
[r3] | F+1 |
J | K | 0 |
+-----------+-----------+-----------+-----------+
[r4] | M |
C+1+K-M-Q | F+J-C | Q |
+-----------+-----------+-----------+-----------+
To be semi-bimagic, the sum of squares of each row and column must be equal. The sum of the rows equals the sum of the columns, thus the sum of all columns minus the sum of three rows equals the sum of the other row. So the magic sum condition on one of the rows can be deduced from the others. Therefore we need only seven conditions instead of eight. We leave out [r2] since it has the most terms.
Let s2 = magic sum of squares
Computing the sum of squares of each row and column, we find that they all have the expression F^2 + J^2 + K^2 + 1 in common and all the other terms are multiplied by 2.
Let t = (s2 - F^2 - J^2 - K^2 - 1) / 2
The seven conditions for a 4x4 magic square to be
semi-bimagic are
[r1] t = C^2+M^2+Q^2 + J-Q-JQ + MQ-CM-CQ +
FK-FM-KM
[r3] t = F
[r4] t = C^2+M^2+Q^2 +
C+CK-CM-CQ+K-M-Q-KM-KQ+MQ + FJ-CF-CJ
[c1] t = 1+M^2+Q^2 + J-Q-JQ +
KQ-K-KM-Q-MQ+M + F
[c2] t = C^2+M^2+Q^2 + MQ-CM-CQ +
C+CK-CM-CQ+K-M-Q-KM-KQ+MQ
[c3] t = C^2 + FJ-CF-CJ
[c4] t =
M^2+Q^2 + FK-FM-KM + J+M-Q+JM-JQ-MQ
Grouping common terms, we can rewrite the seven
conditions as
[r1] t = (C-M)(C-Q) + (F-M)(K-M) + (1-Q)(J-Q)
[r3]
t = F
[r4] t = (C-F)(C-J) + (C-Q)(1-Q) + (1-Q)(K-M) + (K-M)(C-M)
[c1] t = F + J(1-Q) - M(K-M) - (K-M)(1-Q) + (1-Q)^2
[c2] t = (C-M)(C-Q)
+ (C-Q)(1-Q) + (1-Q)(K-M) + (K-M)(C-M)
[c3] t = (C-F)(C-J)
[c4]
t = (F-M)(K-M) + (1-Q)(J-Q) + M(1-Q) + JM
Here are some more simplifications to the formulation.
Substituting [r3] into [c1]
[c1a] J(1-Q) -
M(K-M) - (K-M)(1-Q) + (1-Q)^2 = 0
Substituting [c3] into [r4]
[r4a] (C-Q)(1-Q) +
(1-Q)(K-M) + (K-M)(C-M) = 0
Substituting [r4a] into [c2]
[c2a] t =
(C-M)(C-Q)
Substituting [c2a] into [r1]
[r1a] (F-M)(K-M) +
(1-Q)(J-Q) = 0
Substituting [r1a] into [c4]
[c4a] t = M(1-Q) +
JM
Substituting [r3] into [c4a]
[c4b] (F-M) =
M(J-Q)
Simplified formulation
[r1a] (F-M)(K-M) +
(1-Q)(J-Q) = 0
[r3] t = F
[r4a] (C-Q)(1-Q) + (1-Q)(K-M) +
(K-M)(C-M) = 0
[c1a] J(1-Q) - M(K-M) - (K-M)(1-Q) + (1-Q)^2 = 0
[c2a] t = (C-M)(C-Q)
[c3] t = (C-F)(C-J)
[c4b] (F-M) =
M(J-Q)
Impossibility Proof
We have a complete formulation for a 4x4 magic square that is also semi-bimagic. If we assume that it has distinct entries, then this leads to a contradiction.
From [r1a]
(F-M)/(J-Q) = -(1-Q)/(K-M)
and
from [c4b]
(F-M)/(J-Q) = M
thus
[m1] (1-Q) =
-M(K-M)
Substituting [m1] for one term of [c1a]
[c1b]
J(1-Q) + (1-Q) - (K-M)(1-Q) + (1-Q)^2 = 0
Since (1-Q) is not zero, otherwise Q and 1 would not be
distinct, we can factor out (1-Q) from [c1b]
[c1c] K-M =
J-Q+2
Substituting [c1c] into [r1a]
[r1b] (F-M)(J-Q)
+ 2(F-M) + (1-Q)(J-Q) = 0
Substituting [c4b] for one term of [r1b]
[r1c]
(F-M)(J-Q) + 2M(J-Q) + (1-Q)(J-Q) = 0
Since (J-Q) is not zero, otherwise J and Q would not be
distinct, we can factor out (J-Q) from [r1c]
[r1d] F+M+1-Q =
0
Substituting [m1] for one term of [r4a]
[r4b]
-M(K-M)(C-Q) + (1-Q)(K-M) + (K-M)(C-M) = 0
Since (K-M) is not zero, otherwise K and M would not be
distinct, we can factor out (K-M) from [r4b]
[r4c] (1-M)(C-Q+1) =
0
Since (1-M) is not zero, otherwise M and 1 would not be
distinct, we can factor out (1-M) from [r4c]
[r4d] C-Q+1 =
0
Review
[r1d] F+M+1-Q = 0
[r3] t =
F
[r4d] C-Q+1 = 0
[c1c] K-M = J-Q+2
[c2a] t =
(C-M)(C-Q)
[c3] t = (C-F)(C-J)
[c4b] (F-M) =
M(J-Q)
Solving [r4d] for Q
Q = C+1
Substituting the expression for Q into [r1d] and
[c2a]
[r1e] F+M-C = 0
[c2b] t = -(C-M)
Solving [r1e] for M
M = C-F
Substituting the expression for M into [c2b]
[c2c] t = -F
From [r3]
t = F
and from [c2c]
t =
-F
thus
F = -F
implying F = 0, and we have a duplication of 0
entries.
Return to the home page http://www.multimagie.com