4x4 magic/semi-bimagic square impossibility proof
by Lee Morgenstern, August 2009.


Part 1 of 3
Complete Solution for a 4x4 Magic Square

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