Transcription
Magic SquaresJenny KenkelSeptember 4, 2018
DefinitionA magic square is a n n grid of numbers such that the sum ofeach row is equal, and equal to the sum of each column.438951276Some definitions also require the sum along the main diagonals toadd to the same total.A perfect magic square is a n n square in which each of theentries 1, . . . , n2 is used exactly once, and one in which the sum ofthe main diagonals is equal to the row (and column) sum.
Magic Squares: HistoryIThere is a legend that the (semi-mythical) emperor Yu, c.2200-2100 BCE, copied a magic square off the back of a giantturtle in the Luo, a tributary of the Huang He (Yellow River).IThe turtle’s magic square is called the Luo Shu and is4 9 23 5 78 1 6This story originated no later than 200 BCE.I
Yang Hui’s ConstructionsThe following method for constructing the Luo Shu andconstructing a 4 4 magic square come from Yang Hui’s book,1275 CE:“Xu Gu Zhai Suan Fa”“Continuation of Ancient Mathematical Methods for Elucidatingthe Strange Properties of Numbers”
Method for Constructing the Luo Shu (c. 1275)14IArrange numbers so thatthey slant downward, to therightI7258369
Method for Constructing the Luo Shu (c. 1275)14IIArrange numbers so thatthey slant downward, to therightInterchange the top and thebottom (1 and 9)I7258369
Method for Constructing the Luo Shu (c. 1275)14IIIArrange numbers so thatthey slant downward, to therightInterchange the top and thebottom (1 and 9)Interchange the left andrightmost entries (7 and 3)I725836994I3258761
Method for Constructing the Luo Shu (c. 1275)14IIIIArrange numbers so thatthey slant downward, to therightInterchange the top and thebottom (1 and 9)I5836994IInterchange the left andrightmost entries (7 and 3)Lower 9 to fill the slotbetween 4 and 2, raise 2 tofill the slot between 8 and 6272358761I438951276
Yang Hui’s Method of Constructing 4 4 Magic SquaresIIArrange the numbers 1 to16 in order in a 4 4 array15913261014371115481216
Yang Hui’s Method of Constructing 4 4 Magic SquaresIArrange the numbers 1 to16 in order in a 4 4 arrayIInterchange the numbers inthe corner of the 115138121
Yang Hui’s Method of Constructing 4 4 Magic SquaresIArrange the numbers 1 to16 in order in a 4 4 arrayIInterchange the numbers inthe corner of the 1115138121I16594211714310615138121Interchange the numbers atthe corners of the innersquare
Neat Properties of Yang Hui’s 4 4 squareNote that the sum of each quadrant is 34, the same as therow/column sum, as is the sum of the four outer corners, and thecenter square.I16594211714310615138121
Neat Properties of Yang Hui’s 4 4 squareNote that the sum of each quadrant is 34, the same as therow/column sum, as is the sum of the four outer corners, and thecenter 38121
Neat Properties of Yang Hui’s 4 4 squareNote that the sum of each quadrant is 34, the same as therow/column sum, as is the sum of the four outer corners, and thecenter 38121I16594211714310615138121
Quick Tangent: Magic Square in Durer’s Melancholia(1514)IIncludes a 4 4 magicsquare!IEtched in 1514
Durer’s Melancholia (1514) and the DaVinci Code“Exactly,” Langdon said. “But didyou know that this magic square isfamous because Dürer accomplishedthe seemingly impossible?” He quicklyshowed Katherine that in addition tomaking the rows, columns, and diagonals add up to thirty-four, Dürer hadalso found a way to make the fourquadrants, the four center squares,and even the four corner squares addup to that number. “Most amazing,though, was Dürer’s ability to position the numbers 15 and 14 togetherin the bottom row as an indication ofthe year in which he accomplished thisincredible feat!”Katherine scanned the numbers,amazed by all the combinations.- Dan Brown, the DaVinci Code
Yang Hui’s 7 7 magic ins a 5 5 magic square and a 3 3 magic square!Yang Hui did not write how he found it!
Counting Perfect Magic SquaresThere are no perfect 2 2 magic squares:1321,4342
Counting Perfect Magic SquaresThere are no perfect 2 2 magic squares:1321,4342Once I’ve fixed one entry, I need two entries to be non-distinct:11FF
3 3 perfect magic squaresISuppose we want a 3 3 perfect magic square, i.e, using thedigits 1, 2, . . . , 9.1 2 3 · · · 9 (9)(10)/2 45
3 3 perfect magic squaresISuppose we want a 3 3 perfect magic square, i.e, using thedigits 1, 2, . . . , 9.1 2 3 · · · 9 (9)(10)/2 45Ithus row sum (and column sum) 45/3 15
3 3 perfect magic squaresISuppose we want a 3 3 perfect magic square, i.e, using thedigits 1, 2, . . . , 9.1 2 3 · · · 9 (9)(10)/2 45Ithus row sum (and column sum) 45/3 15Inote that whatever number is in the middle needs to be partof 4 different ways to add up to 15
3 3 perfect magic squaresRow (and column) sum is 15
3 3 perfect magic squaresRow (and column) sum is 15I45 3c 60 (every entry, overcounting the center square 3times, gives me 4 15)
3 3 magic squaresIRow (and column) sum is 15ICenter entry must be 55
3 3 magic squaresIRow (and column) sum is 15ICenter entry must be 55Iwhatever numbers go in a diagonal spot must be in 3 differentpartitions of 15
3 3 magic squaresIRow (and column) sum is 15ICenter entry must be 55Iwhatever numbers go in a diagonal spot must be in 3 differentpartitions of 15I1 can’t be in a diagonal:1 (6 8) 15,1 (5 9) 15I951
3 3 magic squaresIRow (and column) sum is 15ICenter entry must be 55Iwhatever numbers go in a diagonal spot must be in 3 differentpartitions of 15I1 can’t be in a diagonal:1 (6 8) 15,1 (5 9) 15I3 can’t be in a diagonal:3 (7 5), 3 (8 4)951II79513
3 3 magic squaresWe have:7I9513We know 6 and 8 can’t go in the top row (9 6 15, 9 8 17)
3 3 magic squaresWe have:79513IWe know 6 and 8 can’t go in the top row (9 6 15, 9 8 17)I4We need to put 2 and 4 in top row, but 7?9513
3 3 magic squaresWe have:79513IWe know 6 and 8 can’t go in the top row (9 6 15, 9 8 17)I4We need to put 2 and 4 in top row, but 7?I2So we must have: 769514389513
3 3 magic squaresWe have:79513IWe know 6 and 8 can’t go in the top row (9 6 15, 9 8 17)I4We need to put 2 and 4 in top row, but 7?I2So we must have: 76951438This is it, up to rotations and reflections!9513
Number of Perfect Magic SquaresIf we want to consider “perfect” magic squares, i.e. those withnumbers 1 through n2 whose main diagonals also add up to therow sum, there areI0 squares of size 2 2I1 square of size 3 3 (up to rotations and reflections)
Number of Perfect Magic SquaresIf we want to consider “perfect” magic squares, i.e. those withnumbers 1 through n2 whose main diagonals also add up to therow sum, there areI0 squares of size 2 2I1 square of size 3 3 (up to rotations and reflections)I880 such squares of size 4 4 (up to rotations andreflections). This was shown by Frenicle, before 1675.
Number of Perfect Magic SquaresIf we want to consider “perfect” magic squares, i.e. those withnumbers 1 through n2 whose main diagonals also add up to therow sum, there areI0 squares of size 2 2I1 square of size 3 3 (up to rotations and reflections)I880 such squares of size 4 4 (up to rotations andreflections). This was shown by Frenicle, before 1675.I275,305,224 of size 5 5 (up to rotations and reflections)
Number of Perfect Magic SquaresIf we want to consider “perfect” magic squares, i.e. those withnumbers 1 through n2 whose main diagonals also add up to therow sum, there areI0 squares of size 2 2I1 square of size 3 3 (up to rotations and reflections)I880 such squares of size 4 4 (up to rotations andreflections). This was shown by Frenicle, before 1675.I275,305,224 of size 5 5 (up to rotations and reflections)IThe number of perfect magic squares of size 6 6 is unknown!Estimated to be near 1.7745 · 101 9.
Counting (Not perfect) Magic SquaresISuppose we want to count the number of n n magic squareswith row sum r .ILet Hn (r ) denote this numberSome gimmes:IIIHn (0) 1H1 (r ) 1
Number of Size 2 Magic Squares With Any rITo construct a size 2 magicsquare with row sum r , wecan put any integer, i, from0 to r in the first corner.Ii
Number of Size 2 Magic Squares With Any rIITo construct a size 2 magicsquare with row sum r , wecan put any integer, i, from0 to r in the first corner.The numbers in the samerow and column as i are nowfixed.IIiir-ir-i
Number of Size 2 Magic Squares With Any rIIITo construct a size 2 magicsquare with row sum r , wecan put any integer, i, from0 to r in the first corner.The numbers in the samerow and column as i are nowfixed.which in turn fixes the lastcorner.IiIir-ir-iIir-ir-ii
Number of Size 2 Magic Squares With Any rIITo construct a size 2 magicsquare with row sum r , wecan put any integer, i, from0 to r in the first corner.The numbers in the samerow and column as i are nowfixed.IiIir-ir-iIir-ir-iiwhich in turn fixes the lastcorner.We got to make 1 choice, and we had r 1 options, soIH2 (r ) r 1
Number of Size n Magic Squares With r 1To create a magic square with row sum 1, in the first row, we haven options:
Number of Size n Magic Squares With r 1To create a magic square with rown options:I 0 sum 1, in the first row, we have 1 00 0
Number of Size n Magic Squares With r 1To create a magic square with row sum 1, in the first row, we haven 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 1To create a magic square with row sum 1, in the first row, we haven options:I 0 1 0 0 0 I For the second row, we have n 1 options: 0 1 0 0 0 1 0 0IUntil finally, the nth row has 0 01only one option: 1 00 1 0 0giving a total ofHn (1) n!
Birkhoff-von NeumannISize n n matrices of 0’s and 1’s, with exactly one 1 in eachrow and each column are called permutation matrices.IThere are n! permutation matrices of size n n.
Birkhoff-von NeumannISize n n matrices of 0’s and 1’s, with exactly one 1 in eachrow and each column are called permutation matrices.IThere are n! permutation matrices of size n n.INote: If A and B are magic squares of size n n, then so isA B.
Birkhoff-von NeumannISize n n matrices of 0’s and 1’s, with exactly one 1 in eachrow and each column are called permutation matrices.IThere are n! permutation matrices of size n n.INote: If A and B are magic squares of size n n, then so isA B.IBirkhoff-von Neumann TheoremEvery n n magic square with row sum r is the sum of r (notnecessarily distinct) permutation matrices of size n n.
Birkhoff-von Neumann for Counting 3 3 magic squaresIWe know there are 3! 6 permutation matrices of size 3 3.ITo construct a size 3 magic square with row sum r , we will bechoosing r objects from these 6 possibilities
Birkhoff-von Neumann for Counting 3 3 magic squaresIWe know there are 3! 6 permutation matrices of size 3 3.ITo construct a size 3 magic square with row sum r , we will bechoosing r objects from these 6 possibilities But we can re-use permutation matrices, so we don’t want 6rI
Birkhoff-von Neumann for Counting 3 3 magic squaresIWe know there are 3! 6 permutation matrices of size 3 3.ITo construct a size 3 magic square with row sum r , we will bechoosing r objects from these 6 possibilities But we can re-use permutation matrices, so we don’t want 6rILemmaThe way to chooser , not necessarily distinct, objects from 6 options is r 5.r
Number of ways to choose r not necessarily distinctobjects from 6 optionsSuppose we know we have r matrices, each of which can be one of6 options.Why isn’t the answer r 6 ? Because order doesn’t matter: 1 0 00 0 10 0 11 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 10 1 00 1 00 0 1Instead, we can count the number of options by using stars andbars
Stars and Bars: part 1 of 2Suppose we have r stars (for my pictures, r 8)FFFFFFFFeach of which can be one of 6 options. Call the optionsP1 , P2 , P3 , P4 , P5 and P6
Stars and Bars: part 1 of 2Suppose we have r stars (for my pictures, r 8)FFFFFFFFeach of which can be one of 6 options. Call the optionsP1 , P2 , P3 , P4 , P5 and P6We are placing each of our r stars into one of 6 bins; which we cando by inserting 5 “bars” to represent the edges of the bins:FF F F F F FF
Stars and Bars: part 1 of 2Suppose we have r stars (for my pictures, r 8)FFFFFFFFeach of which can be one of 6 options. Call the optionsP1 , P2 , P3 , P4 , P5 and P6We are placing each of our r stars into one of 6 bins; which we cando by inserting 5 “bars” to represent the edges of the bins:FF F F F F FFcorresponds to having2P1 P2 P3 P4 P5 2P6and FFF F F F FF
Stars and Bars: part 1 of 2Suppose we have r stars (for my pictures, r 8)FFFFFFFFeach of which can be one of 6 options. Call the optionsP1 , P2 , P3 , P4 , P5 and P6We are placing each of our r stars into one of 6 bins; which we cando by inserting 5 “bars” to represent the edges of the bins:FF F F F F FFcorresponds to having2P1 P2 P3 P4 P5 2P6and FFF F F F FF corresponds to3P1 P3 P4 P5 2P6
Stars and Bars: Part 2 of 2In other words, we have r 5 objects, r stars and 5 bars.
Stars and Bars: Part 2 of 2In other words, we have r 5 objects, r stars and 5 bars.Choosing the position of the r starsleaves exactly 5 positions left for the 5 bars, so there are r 5rFFFF F F FF
Stars and Bars: Part 2 of 2In other words, we have r 5 objects, r stars and 5 bars.Choosing the position of the r starsleaves exactly 5 positions left for the 5 bars, so there are r 5rFFFF F F FFFFF F F F FF
A problem we didn’t count on.So there areof size 3 3.r 5r ways to have a sum of r permutation matrices
A problem we didn’t count on. So there are r 5ways to have a sum of r permutation matricesrof size 3 3.Unfortunately.
A problem we didn’t count on. So there are r 5ways to have a sum of r permutation matricesrof size 3 3.Unfortunately. 1 0 00 1 00 0 11 0 00 0 10 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 11 0 00 1 00 1 01 0 00 0 1In other words, we have a . . .
A problem we didn’t count on. So there are r 5ways to have a sum of r permutation matricesrof size 3 3.Unfortunately. 1 0 00 1 00 0 11 0 00 0 10 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 11 0 00 1 00 1 01 0 00 0 1In other words, we have a . . .SYZYGY!!!
Subtracting off SyzygiesTo count the numberof 3 3 magic squares, we have an upper r 5bound of r .Every time we see P4 P5 P6 I can replace it with P1 P2 P3 .
Subtracting off SyzygiesTo count the numberof 3 3 magic squares, we have an upper r 5bound 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 SyzygiesTo count the numberof 3 3 magic squares, we have an upper r 5bound 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 itThe number of ways to choose r many things, where three of themare fixed, is the number of ways to choose r 3 many things: (r 3) 5r 3
Subtracting off SyzygiesTo count the numberof 3 3 magic squares, we have an upper r 5bound 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 itThe number of ways to choose r many things, where three of themare fixed, is the number of ways to choose r 3 many things: (r 3) 5r 3So the number of 3 3 magic squares is r 5r 2 rr 3There are no other syzygies in this case, so we are done!Hilbert’s Syzygy Theorem promised us the process would terminateafter n! steps.
Syzygetic Method for 4 4 magic squares (R.P. Stanley)Number of 4 4 magic squares: r 9r 8r 7 14 87 999 r 6r 5r 4r 3148 87 14 9999
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)IH1 (r ) 1 is a polynomial in degree 0IH2 (r ) r 1 is a polynomial in degree 1I H3 (r ) r 5r 2 rr 31 (r 1)(r 2)(r 2 3r 4)8
Thank You!
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 de nitions 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
