From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Q: Magic cubes. Do they exist? Date: 29 Jan 1996 16:59:38 GMT In article <4eihmk\$9q9@sbctri.tri.sbc.com>, Steve Monson wrote: >In article <4eerka\$799@geraldo.cc.utexas.edu>, >Miguel Lerma wrote: >>I disagree. According to W.S. Andrews: "Magic Squares and Cubes", Well, however you make your definitions, it is still legitimate to ask various questions. A 3 x 3 x 3 magic cube is a collection of 27 numbers in which various sets of three should sum to the same number S. On each of the three levels you expect a magic square. This gives 8 equations in 9 unknowns, whose solution has dimension 2 (2 degrees of freedom). Taking all three levels gives 6 degrees of freedom. If you want the vertical sums to be S too, you add 9 equations, which as it turns out reduces you from 6 to 4 degrees of freedom for the set of 27 variables. If you want the diagonals in planes parallel to the yz plane to sum to S too, that adds 6 equations and, as it turns out, leaves only 2 degrees of freedom. If you want the diagonals in planes parallel to the xz plane to sum to S too, that adds another 6 equations and as it turns out has as its only solution that each of the 27 variables equals (1/3)S. You could also ask that the 4 main diagonals sum to S, but this of course is now automatic. So if you ask for too much from your cube you get only trivial solutions. Thus it is perhaps more interesting to ask for fewer requirements. Of course, this is all simple linear algebra. dave ============================================================================== To: rusin@washington.math.niu.edu (Dave Rusin) From: mwe1@psu.edu (Dr. Michael Ecker) Subject: Re: Q: Magic cubes. Do they exist? Date: Mon, 29 Jan 1996 19:54:18 GMT Prof. D. Rusin, Dear Dave, It's probably just a minor thing I'm missing or a terminological point, so please forgive my stupidity. Did you mean to say that 8 equations in 9 unknowns yield 2 degrees of freedom? I have played very little with magic cubes - just a passing acquaintance - but wouldn't 8 equations in 9 unknowns give only 1 degree of freedom? For instance, 1 equation in 2unknowns I would consider to have only 1 degree of freedom, and 1 equation in 1 unknown would have none. (Of course, I am simplistically assuming linearity as well as no inconsistency or redundancy.) What am I not understanding? Or, was there a typo? Thanks, Mike [previous post was attached -- djr] ============================================================================== Date: Mon, 29 Jan 96 14:14:21 CST From: rusin (Dave Rusin) To: mwe1@psu.edu Subject: Re: Q: Magic cubes. Do they exist? >Did you mean to say that 8 equations in 9 unknowns yield 2 degrees of freedom? > >I have played very little with magic cubes - just a passing acquaintance - but >wouldn't 8 equations in 9 unknowns give only 1 degree of freedom? For >instance, 1 equation in 2unknowns I would consider to have only 1 degree of >freedom, and 1 equation in 1 unknown would have none. > >(Of course, I am simplistically assuming linearity as well as no >inconsistency or redundancy.) ^^^^^^^^^^ This is the issue precisely. Generally n (differentiable) equations in m unknowns will have a solution set which is (locally) m-n dimensional. But this fails if the derivative of the set of equations fails to have rank m, which is the technical condition you're referring to as redundancy. In the case of linear equations, this happens iff one of the equations is a linear combination of the others. Well, add the three equations which state that the three rows sum to S, and subtract two of the equations stating that two of the columns also sum to S. This will leave exactly the remaining equation for a column sum. So those 6 equations are already linearly dependent (redundant). The two diagonal equations are independent of these two, so there are "really" 7 equations in 9 unknowns leaving a 2-parameter family of (three-by-three) magic squares BTW, that's what accounts for the other drops in dimension being less than expected, too. It's not immediately clear what the linear dependencies are, but they're there. This allows us to find cubes which have more than 27 row sums all coming out to S . Unfortunately, as I noted, there are 49 row sums you might hope to come out to S, so you're really pushing your luck when you hope for this much redundancy, and in fact your luck doesn't quite hold out: the only solution is for all variables to equal S/3. dave ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Q: Magic cubes. Do they exist? Date: 29 Jan 1996 20:57:16 GMT In article <4eiudq\$ce5@muir.math.niu.edu>, Dave Rusin wrote: >A 3 x 3 x 3 magic cube is a collection of 27 numbers in which various sets of >three should sum to the same number S. [linear algebra deleted] >So if you ask for too much from your cube you get only trivial solutions. I suppose I should add that this search for 3 x 3 x 3 cubes can also be used for more general cubes. You can be quite lazy and ask a machine to solve the system of linear equations (I did). Although there is no 3 x 3 x 3 cube besides the ones with all entries equal, there are more solutions for larger cubes. In an n x n x n cube there are n^3 variables and you wish them to satisfy equations stating that many sets of n of them will sum to S. Well, there are n^2 rows pointing in each of the three cardinal directions, giving 3 n^2 equations to solve. There are n planes parallel to each of the 3 coordinate planes, each such plane having two diagonals; these give 6 n more equations. Finally, there are 4 "three- dimensional" diagonals. Taken together these give 3n^2+6n+4 equations in n^3 variables. There are many linear dependencies among the equations -- at the very least I could describe one for each of the n levels -- so the solution set has dimension greater than n^3-(3n^2+6n+4). (I suppose I should point out that the equations are consistent -- having all n^3 variables equal provides one solution.) In particular, n x n x n magic cubes with distinct entries exist for all n>3. Moreover, for large n, you can set almost all entries of the cube to anything you want, and then fill in the remaining entries to fit the equations. Because of the degrees of freedom, the challenge for larger cubes is to have more conditions met -- for example, some kind of symmetry or arithmetic progression. You can generalize the problem to higher dimensions, too. For example, an n x n x n x n magic (hyper)cube has n^4 entries but, following the same pattern as used in 3 dimensions, there are now (4 axes) x (n^3 rows/axis) x (1 sum/row) +(6 pairs of axes) x (n^2 planes/pair) x (2 sums/plane) +(4 triples of axes) x (n 3D sets/triple) x (4 sums/3D cube) +(1 set of all axes) x (1 4D set) x (8 sums/4D set) = 4 n^3 + 12 n^2 + 16 n + 8 = (n+2)^4 - n^4 equations among these n^4 variables. This shows that the dimension of the set of all magic 4D cubes with a given row-sum is at least 2 n^4 - (n+2)^4, which is positive if n is at least 2/(2^(1/4) - 1) = 10.5... Change that last "4" to any other natural number d and you get a bound on the size of the cubes in that dimension d which are sure to allow for magic cubes. (This number is just a little more than (2/ln2)*d - 1, so I guess there are nontrivial d-dimensional magic cubes of rank n as long as n > floor( (2/ln 2)*d ). ) I don't know if anyone has fleshed out the correct dimensions of these spaces. I would imagine that someone already has. I'd try it myself, but to do so one would have to actually think :-). dave (teaching linear algebra this semester...)