| home
| send comment
| send link
| add bookmark |
Operations on magic squares
by Stephen R. Schmitt
Definition
A magic square is an arrangement of the numbers from 1...N2 in
an NxN matrix, with each number occurring exactly once, and such that the sum
of the entries of any row, any column, or either main diagonal is equal to the
magic constant defined as:
M2 = N·(N2 + 1)/2
The simplest magic square is the 1x1 magic square whose only entry is the
number 1. The next simplest is the 3x3 magic square:
8 1 6
3 5 7
4 9 2
and those derived from it by transformations.
Transformations
If every number in a magic square is subtracted from N2+1, the
complementary magic square is created. The complement to the magic square above is:
2 9 4
7 5 3
6 1 8
Other possible operations include rotation left or right, reversal to create
a mirror image, inversion or flipping so the top row is on the bottom, and
transposition where rows and columns are exchanged. These operations due not change
the sums of the rows, columns, and diagonals and do not create distinctly new magic squares.
Multiplication
Addition of magic squares does not result in another magic square, so they cannot be added.
However, they can be multiplied. That is, given a 3x3 magic square
A and a 4x4 magic square B, the product of
A and B, denoted by A*B, will be a
12x12 magic square. The use of product and multiplication in this context is
different than multiplication of numbers.
Properties
- The multiplication of magic squares, satisfies the associative law:
If A, B, and C are magic squares, then
A*(B*C) = (A*B)*C.
- There is an identity element 1, the 1x1 magic square whose only
entry is 1.
If A is a magic square, then A*1 = A.
- The commutative law does NOT hold.
If A and B are magic squares, then
A*B ≠ B*A.
- A magic square is composite if it is the product of two strictly smaller magic squares.
- A magic square is prime if it is not composite and is not the 'unit' 1x1
magic square.
Procedure
If A has dimension N and B has dimension
M then the product C consists of an MxM matrix of
NxN sub-matrices where each element of a sub-matrix is:
aij + N2·(bxy-1)
in which i, j are the indices of A and x,
y are the indices of B. To illustrate, let
| A = |
| a11 |
a12 |
a13 |
| a21 |
a22 |
a23 |
| a31 |
a32 |
a33 |
|
and let
| B = |
| b11 |
b12 |
b13 |
b14 |
| b21 |
b22 |
b23 |
b24 |
| b31 |
b32 |
b33 |
b34 |
| b41 |
b42 |
b43 |
b44 |
|
then we can write out
| C = |
| a11+9(b11-1) |
a12+9(b11-1) |
a13+9(b11-1) |
a11+9(b12-1) |
a12+9(b12-1) |
a13+9(b12-1) |
. . . |
| a21+9(b11-1) |
a22+9(b11-1) |
a23+9(b11-1) |
a21+9(b12-1) |
a22+9(b12-1) |
a23+9(b12-1) |
. . . |
| a31+9(b11-1) |
a32+9(b11-1) |
a33+9(b11-1) |
a31+9(b12-1) |
a32+9(b12-1) |
a33+9(b12-1) |
. . . |
| a11+9(b21-1) |
a12+9(b21-1) |
a13+9(b21-1) |
a11+9(b22-1) |
a12+9(b22-1) |
a13+9(b22-1) |
. . . |
| a21+9(b21-1) |
a22+9(b21-1) |
a23+9(b21-1) |
a21+9(b22-1) |
a22+9(b22-1) |
a23+9(b22-1) |
. . . |
| a31+9(b21-1) |
a32+9(b21-1) |
a33+9(b21-1) |
a31+9(b22-1) |
a32+9(b22-1) |
a33+9(b22-1) |
. . . |
| : |
: |
: |
: |
: |
: |
. . . |
| : |
: |
: |
: |
: |
: |
. . . |
|
A numerical example is shown in the sample output near the bottom of
this page.
Zeno source code
Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy
to learn and is suitable for educational purposes.
const N : int := 20
type matrix : array[N,N] of int
program
var A, B, C : matrix
var n : int
put "\nA = "
do_magic( A, 3 )
put_square( A, 3 )
put "\ncomplemented "
complement( C, A, 3 )
put_square( C, 3 )
put "\nreversed "
reverse( C, A, 3 )
put_square( C, 3 )
put "\nflipped "
flip( C, A, 3 )
put_square( C, 3 )
put "\ntransposed "
transpose( C, A, 3 )
put_square( C, 3 )
put "\nrotated right "
rotate_right( C, A, 3 )
put_square( C, 3 )
put "\nB <-- A rotated left "
rotate_left( B, A, 3 )
put_square( B, 3 )
put "\nA * B = "
n := multiply( C, A, 3, B, 3 )
put_square( C, n )
put "magic number is ", is_magic( C, n ), "\n"
end program
procedure complement( var C, A : matrix, a : int )
% generate the complement of a magic square
var i, j : int
var m : int := a*a + 1
for i := 1...a do
for j := 1...a do
C[i,j] := m - A[i,j]
end for
end for
end procedure
procedure transpose( var T, A : matrix, a : int )
% exchange rows and columns in a square matrix
var i, j : int
for i := 1...a do
for j := 1...a do
T[i,j] := A[j,i]
end for
end for
end procedure
procedure reverse( var R, A : matrix, a : int )
% reverse the order of columns in a square matrix
var i, j : int
for i := 1...a do
for j := 1...a do
R[i,a+1-j] := A[i,j]
end for
end for
end procedure
procedure flip( var F, A : matrix, a : int )
% reverse the order of rows in a square matrix
var i, j : int
for i := 1...a do
for j := 1...a do
F[a+1-i,j] := A[i,j]
end for
end for
end procedure
procedure rotate_right( var R, A : matrix, a : int )
% rotate a square matrix to the right by 90 degrees
var X : matrix
transpose( X, A, a )
reverse( R, X, a )
end procedure
procedure rotate_left( var L, A : matrix, a : int )
% rotate a square matrix to the left by 90 degrees
var X : matrix
reverse( X, A, a )
transpose( L, X, a )
end procedure
function multiply( var R, A : matrix, a : int, var B : matrix, b : int ) : int
% multiply two magic squares to generate a new magic square
% R[a*b, a*b] <- A[a,a] * B[b,b]
var ia, ib, ja, jb, m : int
for ib := 1...b do
for jb := 1...b do
for ia := 1...a do
for ja := 1...a do
m := A[ia, ja] + (B[ib, jb] - 1)*a*a
R[(ib-1)*a+ia, (jb-1)*a+ja] := m
end for
end for
end for
end for
return a*b
end function
procedure do_magic( var mat : matrix, n : int )
% generate a magic square using the appropriate method
assert n <= N
if (n mod 2 > 0) then
odd_order( mat, n )
elsif (n mod 4 = 0) then
doubly_even( mat, n )
else
singly_even( mat, n )
end if
end procedure
procedure odd_order( var mat : matrix, n : int )
% generate a magic square using the
% siamese method for any odd value n
assert (n mod 2 > 0) % N must be odd
var i, j, N3, t : int
N3 := (n - 3) div 2
for i := 1...n do
for j := 1...n do
t := (i + j*2 - 2) mod n
mat[i, j] := (1 + t + n*((N3 + i + j) mod n))
end for
end for
end procedure
procedure doubly_even( var mat : matrix, n : int )
% generate a magic square using the
% big X method for sizes 4, 8, 12, 16 ...
var i, j : int
var nsq1 : int := n*n + 1
var val : int := 0
for i := 1...n do
for j := 1...n do
incr val
if ( ( ((i div 2) mod 2 > 0) and ((j div 2) mod 2 > 0) ) or
( ((i div 2) mod 2 = 0) and ((j div 2) mod 2 = 0) ) ) then
mat[i,j] := nsq1 - val
else
mat[i,j] := val
end if
end for
end for
end procedure
procedure singly_even( var mat : matrix, N : int )
% generate a magic square using the
% LUX method for sizes 6, 10, 14 ...
var i, j, s3, t, s, m : int
var js, is : int := 0
m := (N - 2) div 4
s := (m*2) + 1
s3 := (s - 3) div 2
for i := 1...N do
if ((i mod 2) > 0) then
incr is
end if
js := 0
for j := 1...N do
if ((j mod 2) > 0) then
incr js
end if
t := ((((is + (js*2) - 2) mod s) + s*((s3 + is + js) mod s))*4) + 1
if ((i mod 2) > 0) then % is top of 4-block?
if ( (is > m+2) or % is X
( (is = m+2) and (js ~= m+1) ) or % or L?
( (is = m+1) and (js = m+1) ) ) then
if (j mod 2 > 0) then
mat[i,j] := t
else
mat[i,j] := t + 3
end if
else
if (j mod 2 > 0) then
mat[i,j] := t + 3
else
mat[i,j] := t
end if
end if
else % is bottom of 4-block
if (is < m+3) then % is L or U?
if (j mod 2 > 0) then
mat[i,j] := t + 1
else
mat[i,j] := t + 2
end if
else
if (j mod 2 > 0) then
mat[i,j] := t + 2
else
mat[i,j] := t + 1
end if
end if
end if
end for
end for
end procedure
procedure put_square( var mat : matrix, n : int )
% sends magic square of integers to text output
var i, j : int
for i := 1...n do
for j := 1...n do
put mat[i,j]:5...
end for
put ""
end for
end procedure
function is_magic( var mat : matrix, n : int ) : int
% test rows, columns, and diagonals all sum to same value
var i, j : int
var row, col, dia1, dia2 : int
var M2 : int := magic_const( n )
% check rows, columns, diagonals
dia1 := 0
dia2 := 0
for i := 1...n do
row := 0
col := 0
dia1 := dia1 + mat[i,i]
dia2 := dia2 + mat[n+1-i,i]
for j := 1...n do
row := row + mat[i,j]
col := col + mat[j,i]
end for
if (row ~= M2) or (col ~= M2) then
return 0
end if
end for
if (dia1 ~= M2) or (dia2 ~= M2) then
return 0
end if
return M2
end function
function magic_const( n : int ) : int
% compute the number that each row, col,
% and main diagonal must sum to
return (n*(n*n+1)) div 2
end function
Sample output
A =
8 1 6
3 5 7
4 9 2
complemented
2 9 4
7 5 3
6 1 8
reversed
6 1 8
7 5 3
2 9 4
flipped
4 9 2
3 5 7
8 1 6
transposed
8 3 4
1 5 9
6 7 2
rotated right
4 3 8
9 5 1
2 7 6
B <-- A rotated left
6 7 2
1 5 9
8 3 4
A * B =
53 46 51 62 55 60 17 10 15
48 50 52 57 59 61 12 14 16
49 54 47 58 63 56 13 18 11
8 1 6 44 37 42 80 73 78
3 5 7 39 41 43 75 77 79
4 9 2 40 45 38 76 81 74
71 64 69 26 19 24 35 28 33
66 68 70 21 23 25 30 32 34
67 72 65 22 27 20 31 36 29
magic number is 369
Reference
- Wolfram Research : Magic Square
- Math Forum : Magic Squares
- The Zen of Magic Squares, Circles, and Stars : An Exhibition of Surprising Structures across Dimensions
AbCd Classics - free on-line books
Copyright © 2005, Stephen R. Schmitt