Magic Squares
Jenny Kenkel
September 4, 2018
Definition
A magic square is a n × n grid of numbers such that the sum of
each row is equal, and equal to the sum of each column.
4 9 2
3 5 7
8 1 6
Some definitions also require the sum along the main diagonals to
add to the same total.
A perfect magic square is a n × n square in which each of the
entries 1, . . . , n2 is used exactly once, and one in which the sum of
the main diagonals is equal to the row (and column) sum.
Magic Squares: History
I There is a legend that the (semi-mythical) emperor Yu, c.
2200-2100 BCE, copied a magic square off the back of a giant
turtle in the Luo, a tributary of the Huang He (Yellow River).
I The turtle’s magic square is called the Luo Shu and is
4 9 2
3 5 7
8 1 6
I This story originated no later than 200 BCE.
Yang Hui’s Constructions
The following method for constructing the Luo Shu and
constructing a 4 × 4 magic square come from Yang Hui’s book,
1275 CE:
“Xu Gu Zhai Suan Fa”
“Continuation of Ancient Mathematical Methods for Elucidating
the Strange Properties of Numbers”
Method for Constructing the Luo Shu (c. 1275)
1
4 2
I 7 5 3
I Arrange numbers so that
8 6
they slant downward, to the
9
right
Method for Constructing the Luo Shu (c. 1275)
1
4 2
I 7 5 3
I Arrange numbers so that
8 6
they slant downward, to the
9
right
I Interchange the top and the
bottom (1 and 9)
Method for Constructing the Luo Shu (c. 1275)
1
4 2
I 7 5 3
I Arrange numbers so that
8 6
they slant downward, to the
9
right
9
I Interchange the top and the
4 2
bottom (1 and 9)
I 3 5 7
I Interchange the left and 8 6
rightmost entries (7 and 3) 1
Method for Constructing the Luo Shu (c. 1275)
1
4 2
I 7 5 3
I Arrange numbers so that
8 6
they slant downward, to the
9
right
9
I Interchange the top and the
4 2
bottom (1 and 9)
I 3 5 7
I Interchange the left and 8 6
rightmost entries (7 and 3) 1
I Lower 9 to fill the slot
between 4 and 2, raise 2 to 4 9 2
fill the slot between 8 and 6 I 3 5 7
8 1 6
Yang Hui’s Method of Constructing 4 × 4 Magic Squares
1 2 3 4
5 6 7 8
I
I Arrange the numbers 1 to 9 10 11 12
16 in order in a 4 × 4 array 13 14 15 16
Yang Hui’s Method of Constructing 4 × 4 Magic Squares
1 2 3 4
5 6 7 8
I
I Arrange the numbers 1 to 9 10 11 12
16 in order in a 4 × 4 array 13 14 15 16
I Interchange the numbers in 16 2 3 13
the corner of the outer 5 6 7 8
I
square 9 10 11 12
4 14 15 1
Yang Hui’s Method of Constructing 4 × 4 Magic Squares
1 2 3 4
5 6 7 8
I
I Arrange the numbers 1 to 9 10 11 12
16 in order in a 4 × 4 array 13 14 15 16
I Interchange the numbers in 16 2 3 13
the corner of the outer 5 6 7 8
I
square 9 10 11 12
I Interchange the numbers at 4 14 15 1
the corners of the inner 16 2 3 13
square 5 11 10 8
I
9 7 6 12
4 14 15 1
Neat Properties of Yang Hui’s 4 × 4 square
Note that the sum of each quadrant is 34, the same as the
row/column sum, as is the sum of the four outer corners, and the
center square.
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
Neat Properties of Yang Hui’s 4 × 4 square
Note that the sum of each quadrant is 34, the same as the
row/column sum, as is the sum of the four outer corners, and the
center square.
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
Neat Properties of Yang Hui’s 4 × 4 square
Note that the sum of each quadrant is 34, the same as the
row/column sum, as is the sum of the four outer corners, and the
center square.
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
16 2 3 13
5 11 10 8
I
9 7 6 12
4 14 15 1
Quick Tangent: Magic Square in Durer’s Melancholia
(1514)
I Includes a 4 × 4 magic
square!
I Etched in 1514
Durer’s Melancholia (1514) and the DaVinci Code
“Exactly,” Langdon said. “But did
you know that this magic square is
famous because Dürer accomplished
the seemingly impossible?” He quickly
showed Katherine that in addition to
making the rows, columns, and diag-
onals add up to thirty-four, Dürer had
also found a way to make the four
quadrants, the four center squares,
and even the four corner squares add
up to that number. “Most amazing,
though, was Dürer’s ability to posi-
tion the numbers 15 and 14 together
in the bottom row as an indication of
the year in which he accomplished this
incredible feat!”
Katherine scanned the numbers,
amazed by all the combinations.
- Dan Brown, the DaVinci Code
Yang Hui’s 7 × 7 magic square
46 8 16 20 29 7 49
3 40 12 14 18 41 47
44 37 33 23 19 13 6
28 15 11 25 29 35 22
5 24 31 27 17 26 45
48 9 38 36 32 10 2
1 42 34 30 21 43 4
Contains a 5 × 5 magic square and a 3 × 3 magic square!
Yang Hui did not write how he found it!
Counting Perfect Magic Squares
There are no perfect 2 × 2 magic squares:
1 2 1 4
,
3 4 3 2
Counting Perfect Magic Squares
There are no perfect 2 × 2 magic squares:
1 2 1 4
,
3 4 3 2
Once I’ve fixed one entry, I need two entries to be non-distinct:
1 1 F
F
3 × 3 perfect magic squares
I Suppose we want a 3 × 3 perfect magic square, i.e, using the
digits 1, 2, . . . , 9.
1 + 2 + 3 + · · · + 9 = (9)(10)/2 = 45
3 × 3 perfect magic squares
I Suppose we want a 3 × 3 perfect magic square, i.e, using the
digits 1, 2, . . . , 9.
1 + 2 + 3 + · · · + 9 = (9)(10)/2 = 45
I thus row sum (and column sum) = 45/3 = 15
3 × 3 perfect magic squares
I Suppose we want a 3 × 3 perfect magic square, i.e, using the
digits 1, 2, . . . , 9.
1 + 2 + 3 + · · · + 9 = (9)(10)/2 = 45
I thus row sum (and column sum) = 45/3 = 15
I note that whatever number is in the middle needs to be part
of 4 different ways to add up to 15
3 × 3 perfect magic squares
Row (and column) sum is 15
3 × 3 perfect magic squares
Row (and column) sum is 15
I 45 + 3c = 60 (every entry, overcounting the center square 3
times, gives me 4 × 15)
3 × 3 magic squares
I Row (and column) sum is 15
I Center entry must be 5
5
3 × 3 magic squares
I Row (and column) sum is 15
I Center entry must be 5
I whatever numbers go in a diagonal spot must be in 3 different
partitions of 15
3 × 3 magic squares
I Row (and column) sum is 15
I Center entry must be 5
I whatever numbers go in a diagonal spot must be in 3 different
partitions of 15
9
I 1 can’t be in a diagonal: I 5
1+(6+8)= 15,
1
1+(5+9)=15
3 × 3 magic squares
I Row (and column) sum is 15
I Center entry must be 5
I whatever numbers go in a diagonal spot must be in 3 different
partitions of 15
9
I 1 can’t be in a diagonal: I 5
1+(6+8)= 15,
1
1+(5+9)=15
9
I 3 can’t be in a diagonal:
3+(7+5), 3+(8+4)
I 7 5 3
1
3 × 3 magic squares
We have:
9
7 5 3
1
I We know 6 and 8 can’t go in the top row (9+6=15, 9+8=17)
3 × 3 magic squares
We have:
9
7 5 3
1
I We know 6 and 8 can’t go in the top row (9+6=15, 9+8=17)
4 9
I We need to put 2 and 4 in top row, but 7 5 3
? 1
3 × 3 magic squares
We have:
9
7 5 3
1
I We know 6 and 8 can’t go in the top row (9+6=15, 9+8=17)
4 9
I We need to put 2 and 4 in top row, but 7 5 3
? 1
2 9 4
I So we must have: 7 5 3
6 1 8
3 × 3 magic squares
We have:
9
7 5 3
1
I We know 6 and 8 can’t go in the top row (9+6=15, 9+8=17)
4 9
I We need to put 2 and 4 in top row, but 7 5 3
? 1
2 9 4
I So we must have: 7 5 3
6 1 8
This is it, up to rotations and reflections!
Number of Perfect Magic Squares
If we want to consider “perfect” magic squares, i.e. those with
numbers 1 through n2 whose main diagonals also add up to the
row sum, there are
I 0 squares of size 2 × 2
I 1 square of size 3 × 3 (up to rotations and reflections)
Number of Perfect Magic Squares
If we want to consider “perfect” magic squares, i.e. those with
numbers 1 through n2 whose main diagonals also add up to the
row sum, there are
I 0 squares of size 2 × 2
I 1 square of size 3 × 3 (up to rotations and reflections)
I 880 such squares of size 4 × 4 (up to rotations and
reflections). This was shown by Frenicle, before 1675.
Number of Perfect Magic Squares
If we want to consider “perfect” magic squares, i.e. those with
numbers 1 through n2 whose main diagonals also add up to the
row sum, there are
I 0 squares of size 2 × 2
I 1 square of size 3 × 3 (up to rotations and reflections)
I 880 such squares of size 4 × 4 (up to rotations and
reflections). This was shown by Frenicle, before 1675.
I 275,305,224 of size 5 × 5 (up to rotations and reflections)
Number of Perfect Magic Squares
If we want to consider “perfect” magic squares, i.e. those with
numbers 1 through n2 whose main diagonals also add up to the
row sum, there are
I 0 squares of size 2 × 2
I 1 square of size 3 × 3 (up to rotations and reflections)
I 880 such squares of size 4 × 4 (up to rotations and
reflections). This was shown by Frenicle, before 1675.
I 275,305,224 of size 5 × 5 (up to rotations and reflections)
I The number of perfect magic squares of size 6 × 6 is unknown!
Estimated to be near 1.7745 · 101 9.
Counting (Not perfect) Magic Squares
I Suppose we want to count the number of n × n magic squares
with row sum r .
I Let Hn (r ) denote this number
I Some gimmes:
I Hn (0) = 1
I H1 (r ) = 1
Number of Size 2 Magic Squares With Any r
I To construct a size 2 magic
square with row sum r , we i
I
can put any integer, i, from
0 to r in the first corner.
Number of Size 2 Magic Squares With Any r
I To construct a size 2 magic
square with row sum r , we i
I
can put any integer, i, from
0 to r in the first corner.
i r-i
I The numbers in the same I
r-i
row and column as i are now
fixed.
Number of Size 2 Magic Squares With Any r
I To construct a size 2 magic
square with row sum r , we i
I
can put any integer, i, from
0 to r in the first corner.
i r-i
I The numbers in the same I
r-i
row and column as i are now
fixed. i r-i
I
r-i i
I which in turn fixes the last
corner.
Number of Size 2 Magic Squares With Any r
I To construct a size 2 magic
square with row sum r , we i
I
can put any integer, i, from
0 to r in the first corner.
i r-i
I The numbers in the same I
r-i
row and column as i are now
fixed. i r-i
I
r-i i
I which in turn fixes the last
corner.
We got to make 1 choice, and we had r + 1 options, so
H2 (r ) = r + 1
Number of Size n Magic Squares With r = 1
To create a magic square with row sum 1, in the first row, we have
n options:
Number of Size n Magic Squares With r = 1
To create a magic square with row sum 1, in the first row, we have
n options:
I
0 1 0
∗ 0 ∗
∗ 0 ∗
Number of Size n Magic Squares With r = 1
To create a magic square with row sum 1, in the first row, we have
n options:
I
0 1 0
∗ 0 ∗
∗ 0 ∗
I For the second row, we have n − 1 options:
0 1 0
0 0 1
∗ 0 0
Number of Size n Magic Squares With r = 1
To create a magic square with row sum 1, in the first row, we have
n options:
I
0 1 0
∗ 0 ∗
∗ 0 ∗
I For the second row, we have n − 1 options:
0 1 0
0 0 1
∗ 0 0
I Until finally, the nth row has only one option:
0 1 0
0 0 1
1 0 0
giving a total of
Hn (1) = n!
Birkhoff-von Neumann
I Size n × n matrices of 0’s and 1’s, with exactly one 1 in each
row and each column are called permutation matrices.
I There are n! permutation matrices of size n × n.
Birkhoff-von Neumann
I Size n × n matrices of 0’s and 1’s, with exactly one 1 in each
row and each column are called permutation matrices.
I There are n! permutation matrices of size n × n.
I Note: If A and B are magic squares of size n × n, then so is
A + B.
Birkhoff-von Neumann
I Size n × n matrices of 0’s and 1’s, with exactly one 1 in each
row and each column are called permutation matrices.
I There are n! permutation matrices of size n × n.
I Note: If A and B are magic squares of size n × n, then so is
A + B.
I Birkhoff-von Neumann Theorem
Every n × n magic square with row sum r is the sum of r (not
necessarily distinct) permutation matrices of size n × n.
Birkhoff-von Neumann for Counting 3 × 3 magic squares
I We know there are 3! = 6 permutation matrices of size 3 × 3.
I To construct a size 3 magic square with row sum r , we will be
choosing r objects from these 6 possibilities
Birkhoff-von Neumann for Counting 3 × 3 magic squares
I We know there are 3! = 6 permutation matrices of size 3 × 3.
I To construct a size 3 magic square with row sum r , we will be
choosing r objects from these 6 possibilities
But we can re-use permutation matrices, so we don’t want 6r
I
Birkhoff-von Neumann for Counting 3 × 3 magic squares
I We know there are 3! = 6 permutation matrices of size 3 × 3.
I To construct a size 3 magic square with row sum r , we will be
choosing r objects from these 6 possibilities
But we can re-use permutation matrices, so we don’t want 6r
I
Lemma
The way to choose r , not necessarily distinct, objects from 6
options is r +5
r .
Number of ways to choose r not necessarily distinct
objects from 6 options
Suppose we know we have r matrices, each of which can be one of
6 options.
Why isn’t the answer r 6 ? Because order doesn’t matter:
1 0 0 0 0 1 0 0 1 1 0 0
0 1 0 + 1 0 0 = 1 0 0 + 0 1 0
0 0 1 0 1 0 0 1 0 0 0 1
Instead, we can count the number of options by using stars and
bars
Stars and Bars: part 1 of 2
Suppose we have r stars (for my pictures, r = 8)
FFFFFFFF
each of which can be one of 6 options. Call the options
P1 , P2 , P3 , P4 , P5 and P6
Stars and Bars: part 1 of 2
Suppose we have r stars (for my pictures, r = 8)
FFFFFFFF
each of which can be one of 6 options. Call the options
P1 , P2 , P3 , P4 , P5 and P6
We are placing each of our r stars into one of 6 bins; which we can
do by inserting 5 “bars” to represent the edges of the bins:
FF|F|F|F|F|FF
Stars and Bars: part 1 of 2
Suppose we have r stars (for my pictures, r = 8)
FFFFFFFF
each of which can be one of 6 options. Call the options
P1 , P2 , P3 , P4 , P5 and P6
We are placing each of our r stars into one of 6 bins; which we can
do by inserting 5 “bars” to represent the edges of the bins:
FF|F|F|F|F|FF
corresponds to having
2P1 + P2 + P3 + P4 + P5 + 2P6
and FFF||F|F|F|FF
Stars and Bars: part 1 of 2
Suppose we have r stars (for my pictures, r = 8)
FFFFFFFF
each of which can be one of 6 options. Call the options
P1 , P2 , P3 , P4 , P5 and P6
We are placing each of our r stars into one of 6 bins; which we can
do by inserting 5 “bars” to represent the edges of the bins:
FF|F|F|F|F|FF
corresponds to having
2P1 + P2 + P3 + P4 + P5 + 2P6
and FFF||F|F|F|FF corresponds to
3P1 + P3 + P4 + P5 + 2P6
Stars and Bars: Part 2 of 2
In other words, we have r + 5 objects, r stars and 5 bars.
Stars and Bars: Part 2 of 2
In other words, we have r + 5 objects, r stars and 5 bars.
Choosing the position of the r stars leaves exactly 5 positions left
for the 5 bars, so there are r +5
r
FFF F F F FF
Stars and Bars: Part 2 of 2
In other words, we have r + 5 objects, r stars and 5 bars.
Choosing the position of the r stars leaves exactly 5 positions left
for the 5 bars, so there are r +5
r
FFF F F F FF
FFF||F|F|F|FF
A problem we didn’t count on...
r +5
So there are r ways to have a sum of r permutation matrices
of size 3 × 3.
A problem we didn’t count on...
So there are r +5
r ways to have a sum of r permutation matrices
of size 3 × 3.
Unfortunately...
A problem we didn’t count on...
So there are r +5
r ways to have a sum of r permutation matrices
of size 3 × 3.
Unfortunately...
1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0
0 1 0 + 0 0 1 + 1 0 0 = 0 0 1 + 0 1 0 + 1 0 0
0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1
In other words, we have a . . .
A problem we didn’t count on...
So there are r +5
r ways to have a sum of r permutation matrices
of size 3 × 3.
Unfortunately...
1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0
0 1 0 + 0 0 1 + 1 0 0 = 0 0 1 + 0 1 0 + 1 0 0
0 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1
In other words, we have a . . .
SYZYGY!!!
Subtracting off Syzygies
To count the number of 3 × 3 magic squares, we have an upper
r +5
bound of r .
Every time we see P4 + P5 + P6 I can replace it with P1 + P2 + P3 .
Subtracting off Syzygies
To count the number of 3 × 3 magic squares, we have an upper
r +5
bound of r .
Every time we see P4 + P5 + P6 I can replace it with P1 + P2 + P3 .
I’ve overcounted everything with a P4 + P5 + P6 in it
Subtracting off Syzygies
To count the number of 3 × 3 magic squares, we have an upper
r +5
bound of r .
Every time we see P4 + P5 + P6 I can replace it with P1 + P2 + P3 .
I’ve overcounted everything with a P4 + P5 + P6 in it
The number of ways to choose r many things, where three of them
are fixed, is the number of ways to choose r − 3 many things:
(r − 3) + 5
r −3
Subtracting off Syzygies
To count the number of 3 × 3 magic squares, we have an upper
r +5
bound of r .
Every time we see P4 + P5 + P6 I can replace it with P1 + P2 + P3 .
I’ve overcounted everything with a P4 + P5 + P6 in it
The number of ways to choose r many things, where three of them
are fixed, is the number of ways to choose r − 3 many things:
(r − 3) + 5
r −3
So the number of 3 × 3 magic squares is
r +5 r +2
−
r r −3
There are no other syzygies in this case, so we are done!
Hilbert’s Syzygy Theorem promised us the process would terminate
after n! steps.
Syzygetic Method for 4 × 4 magic squares (R.P. Stanley)
Number of 4 × 4 magic squares:
r +9 r +8 r +7
+ 14 + 87 +
9 9 9
r +6 r +5 r +4 r +3
148 + 87 + 14 +
9 9 9 9
About how many magic squares are there, though?
Every Hn (r ) is a polynomial in r of degree (n − 1)2
(Conjectured by Anand-Dumir-Gupta in 1966, proven by R.P.
Stanley in 1973)
About how many magic squares are there, though?
Every Hn (r ) is a polynomial in r of degree (n − 1)2
(Conjectured by Anand-Dumir-Gupta in 1966, proven by R.P.
Stanley in 1973)
I H1 (r ) = 1 is a polynomial in degree 0
I H2 (r ) = r + 1 is a polynomial in degree 1
I
r +5 r +2
H3 (r ) = −
r r −3
1
= (r + 1)(r + 2)(r 2 + 3r + 4)
8
Thank You!
