From: Carsten Haese Newsgroups: sci.math Subject: Mathematical Puzzle: Turn all the lights out Date: Thu, 12 Feb 1998 11:34:51 +0100 Abstract -------- This paper is concerned with a mathematical solution of an electronic puzzle game called "Lights Out". "Lights Out" is a commercially available product, so to protect myself I expressly state that this paper is not intended to influence you in any way to buy or not to buy "Lights Out". My only intention is to present a result of entertaining mathematical research and to share it with anyone who is interested in it. This paper is dedicated to Tracy, who had introduced me to "Lights Out". The Puzzle ---------- The game is a grid of 5 by 5 buttons that can light up. Pressing a button will switch its light around, but it will also switch the lights of the (4, 3, or 2) adjacent buttons around. Each problem presents you with a certain pattern of lit buttons and to solve the puzzle you have to turn all the lights out (which is not easy because if you're not careful you will turn more lights on than off). This is the primary goal, the secondary goal is to accomplish this with as little moves (pressing a button is one move) as possible. My goal here is to find a universal solution to this puzzle, i.e. to find a general algorithm that will tell you which buttons you have to press given a certain initial pattern. The central questions concerning this universal solution are a) Is there a solution for any initial pattern? If yes, why? If not, describe the set of initial patterns that have a solution. b) Assuming a solution exists for a given initial pattern, how can this solution be derived from the pattern? If you want to think about these questions on your own, stop reading here. Further below you will find my solution of the problem (which needn't be the only or most elegant one). I'll be happy about any feedback, comments or corrections by eMail to chaese@physik.tu-berlin.de The solution ------------ My approach to the puzzle is to find an equation that describes how pressing the buttons will affect the lights. First, I need to represent the lights numerically. One obvious representation that incidentally will also prove to be algebraically very useful is to represent an unlit button with 0 and a lit button with 1. I enumerate the 25 buttons/lights from left to right, top to bottom and thus each pattern of lights is represented by a 25-tuple of 0s and 1s, i.e. by an element of {0, 1}^25. To represent the way how pressing a button affects the pattern of lights, I define an addition operator on the set {0, 1} =: Z2 by 0+0 := 0 =: 1+1 and 0+1 := 1 =: 1+0. This describes accurately the switching mechanism when one summand represents the state of a light and the other summand represents whether or not that light is switched. (Not switching an unlit button results in an unlit button, as well as switching a lit button; not switching a lit button results in a lit button, as well as switching an unlit button.) By componentwise application, the addition on Z2 yields an addition on Z2^25 in a natural way. Of course, to take advantage of this addition in Z2^25, I will want to represent the effect of pressing a button as an element of Z2^25. I do this the obvious way. Each button has its own pattern of which lights it will switch and which lights it will leave. By writing 0 for leaving and 1 for switching, each of the buttons (or rather the "button action", i.e. the effect of pressing that button) is described by an element in Z2^25. Let a_i in Z2^25 (i=1,..,25) be the button action that is caused by pressing the i-th button. For example, (1,1,1,0,0, (0,0,0,0,0, 0,1,0,0,0, 0,0,0,0,0, a_2 = 0,0,0,0,0, and a_19 = 0,0,0,1,0, . 0,0,0,0,0, 0,0,1,1,1, 0,0,0,0,0) 0,0,0,1,0) For clarity I write these 25-tuples over 5 lines so that you can see where they are coming from, but there is no mathematical meaning in writing them like that. I can now start the first attempt at writing down an equation that will solve a lights out puzzle. Let y in Z2^25 be the initial light pattern of the puzzle. Now I might play around with the buttons, for example by pressing the 21st button I would transform the light pattern y into a_21 + y. Then I might press the 15th button, resulting in a_15 + (a_21 + y). And so on. The addition is associative, so I can spare the parentheses without ambiguity. The goal is to find a (finite!) sequence (n(1),n(2),...,n(N)) such that a_n(N) + a_n_(N-1) + ... + a_n_1 + y = (0,0,...,0). This approach is awkward, though. The addition in Z2^25 is commutative, so without loss of generality the sequence n(1)...n(N) can be chosen to be non-decreasing. Furthermore, since a_i + a_i = 0 for all i=1,..,25 (in fact, v + v = 0 for all v in Z2^25), the sequence can even be chosen to be strictly increasing since no button action needs to be performed more than once. Evidently this means that N<=25. To achieve an elegant form of the equation with exactly 25 summands, I define a multiplication operator on Z2 that will allow me to skip those button actions that are not needed in the solution sequence. I define 0*0 := 0*1 := 1*0 := 0 and 1*1 := 1. It is known that (Z2,+,*) is a field, and with the natural multiplication s*(v_1,..,v_25) := (s*v1,..,s*v_25), (Z2^25,+,*) is a vector space over the field Z2. Now, the above equation can be equivalently rewritten as x_1*a_1 + ... + x_25*a_25 + y = (0,0,...,0) with some x=(x_1,...,x_25) in Z2^25. By adding y to both sides of this equation I get x_1*a_1 + ... + x_25*a_25 = y. Now I want to write the left hand side as a matrix product. I should mention at this point that all vectors are supposed to be columns, even if I write them as rows for convenience. If I let M be the matrix whose i-th row is a_i (transposed), my equation becomes Mx = y. It is easy to verify that M is the block matrix [A I O O O] [1 1 0 0 0] [I A I O O] [1 1 1 0 0] M = [O I A I O] with A = [0 1 1 1 0] , I = identity matrix, [O O I A I] [0 0 1 1 1] [O O O I A] [0 0 0 1 1] and O = zero matrix. Now I have completed the task of finding an equation that describes the solution of a lights out puzzle. A sequence of button actions that is described by x in Z2^25 will make the light pattern y in Z2^25 vanish if and only if Mx = y. This is a linear equation in a vector space, so even though the equation does not deal with real numbers, I can apply standard solving methods. The above questions can now be answered by studying the properties of M. I have written a small computer program that simultaneously solves the 25 equations Mx = b_i (where {b_i | i=1,...,25} is the cartesian basis of Z2^25) using Gauss elimination. If you want to solve the equation by hand, feel free to do so :-) I won't flood this paper with the result matrix, even though the following main results can't really be verified without it. If you are interested in it, I can send it to you, as well as the source code of the solver program. The main results are: * dim range M = 23, dim kern M = 2. Therefore there are puzzles that can't be solved. Those that can be solved have 4 different solutions because (x_24, x_25) can be chosen arbitrarily from Z2^2. * Examining the last two lines in the final matrix yields a criterion for the existence of a solution. With the vectors (1,0,1,0,1, (1,1,0,1,1, 1,0,1,0,1, 0,0,0,0,0, k_1 = 0,0,0,0,0, and k_2 = 1,1,0,1,1, 1,0,1,0,1, 0,0,0,0,0, 1,0,1,0,1) 1,1,0,1,1) the criterion can be written as 0 = = , where < . , . > denotes the canonical scalar product in Z2^25. It turns out that {k_1, k_2} is a basis of kern M, which is not really surprising because the solvability of Mx=y is equivalent to y being in range M which (since M is symmetric) is equivalent to y being orthogonal to kern M. * A general solving algorithm (i.e. a formula that expresses x in terms of y) can also be found easily by evaluating the result matrix. Such an algorithm would only be suitable for a computer, though. If you are interested in a solution that a human can easily perform, I suggest the following exercises: 1) Show that for any initial pattern there is a sequence of moves that reduces the pattern to the first line. 2) Assuming solvability, show that there are 7 nontrivial patterns that have lights only in the first line. 3) Derive the solutions of these seven patterns from the final matrix. 4) Memorize them and impress your friends :-) This approach never yields a minimal solution because you will most likely press buttons twice, but it is a solution nevertheless. The main questions have been answered, so this concludes the paper. Thank you for reading this far and I hope you enjoyed it. Like I said before, I'll appreciate any comments on this paper. Please email them to chaese@physik.tu-berlin.de - Carsten Haese ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Mathematical Puzzle: Turn all the lights out Date: 14 Feb 1998 05:11:17 GMT Carsten Haese wrote: >The game is a grid of 5 by 5 buttons that can light up. Pressing a button >will switch its light around, but it will also switch the lights of the >(4, 3, or 2) adjacent buttons around. Each problem presents you with a >certain pattern of lit buttons and to solve the puzzle you have to turn >all the lights out (which is not easy because if you're not careful you >will turn more lights on than off). This is the primary goal, the >secondary goal is to accomplish this with as little moves (pressing a >button is one move) as possible. You could play the same game on an m x n grid. The same analysis applies: you are testing to see whether a given element of (Z/2)^(m*n) lies in the subgroup generated by a certain collection of m*n generators. Rather than simply ask whether or not that subgroup is the whole of the matrix group (Z/2)^(m*n), one can ask for the codimension of that subgroup (it's actually a sub-vectorspace over Z/2). It's trivial to compute that codimension for specific (m,n) (e.g. when m=n the codimension is 0,0,0,2,2,0,0,0 for the first few m=n=1,2,3,...8). Question: Can one predict this codimension as a function of m and n? Even better: I was recently asked nearly the same question in email by someone who wanted to work integrally. What are the invariants of the finitely-generated abelian group G/H, where G is the free group Z^(m*n) and H is the subgroup generated by the m*n generators M(i,j) ? (Here M(i,j)_{k,l} = 0 unless |i-k|<=1 and j=l, or i=k and |j-l| <=1; M(i,j)_{k,l} = 1 in those cases.) I can calculated the invariants for many specific m and n, but I don't see the pattern (in particular, there are unexpectedly large primes in the torsion). I did not find rank > 2 in the cases I tried, and I suppose I could conjecture the rank in general, but I wouldn't have much confidence in the conjectures. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Mathematical Puzzle: Turn all the lights out Date: 14 Feb 1998 06:34:16 GMT Dave Rusin wrote: >You could play the same game on an m x n grid. The same analysis applies: ... >It's trivial to compute that codimension for specific (m,n) (e.g. when >m=n the codimension is 0,0,0,2,2,0,0,0 for the first few m=n=1,2,3,...8). Oopsie. That's the free rank. Here are the free ranks for all one-digit (m,n): 0,1,0,0,1,0,0,1,0 1,0,1,0,1,0,1,0,1 0,1,0,0,1,0,0,1,0 0,0,0,2,0,0,0,0,2 1,1,1,0,2,0,1,1,1 0,0,0,0,0,0,0,0,0 <- this row of zeros continues for several more terms (m=6) 0,1,0,0,1,0,0,1,0 1,0,1,0,1,0,1,0,1 0,1,0,2,1,0,0,1,2 The codimension of the corresponding Z/2 - vectorspace is larger by the 2-rank of G/H; these codimensions are 0, 1, 0, 0, 1, 0, 0, 1, 0 0, 2, 0, 1, 0, 2, 0, 1 0, 0, 3, 0, 0, 2, 0 4, 0, 0, 0, 0, 4 2, 0, 4, 1, 1 0, 0, 6, 0 0, 2, 0 0, 1 8 when m <= n <= 9, and of course the table is symmetric for n < m. Patterns? Proofs? Are we ready for torsion? dave =========================================================================== [Here is that "integral" correspondence of which I spoke -- djr] =========================================================================== Date: Wed, 11 Feb 1998 11:26:21 +0000 From: Joshua Bao To: Dave Rusin Subject: Re: Diophantine Equations Suppose that we have an MxN grid of positive integers which can undergo the following transformations: 1) Subtract 1 from one element and all of its neighbors. 2) Add 1 to one element and all of its neighbors. A neighbor is defined as elements directly adjacent to the number (above or below, left or right, excluding diagonals). Example, for a plate of the shape: 5 2 1 3 8 6 8 1 2 2 4 6 5 2 9 Using transform 2) in the position (2,3) leads to the board: 5 2 2 3 8 6 9 2 3 2 4 6 6 2 9 and then, using 1) on (1,4) the following board is obtained: 5 2 1 2 7 6 9 2 2 2 4 6 6 2 9 Is it possible to describe a sequence of moves that should lead to a grid where all the elements have the same value x ? If so what is the minimum number of moves? I would really appreciate it if you could help me or referr me to some references. -- - Josh Bao SCAHS(Class of 1998) CTY-93 YSSP-95 RSI-97 SET Member Home Page - http://web.mit.edu/jbao/www/ "Always do what you love to do, and justify that love." ============================================================================== Date: Wed, 11 Feb 1998 11:04:29 -0600 (CST) From: Dave Rusin To: xxb1@psu.edu Subject: Re: Diophantine Equations What do you allow around the edges? Can I increase just one edge cell (e.g. the (1,3) cell) on the grounds that this is just the visible effect of a type-1 move centered at the (0,3) spot? How about moves centered at positions like (1,x): is it your intention to allow increasing/decreasing precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ? If it weren't for edge effects, it would be easy to show that NOT all grids can be reduced to a constant grid. If w is a primitive sube root of unity and I = sqrt(-1), we can associate to any grid the complex number S = sum( x[i,j] w^i I^j ); then your allowable moves change S by adding or subtracting w^i I^j * ( 1 + w^(-1) + w + I^(-1) + I ) = 0 That is, S is an invariant under the proposed moves. The state to which you hope to transform the grid has S = 0 if the number of columns is a multiple of 3, say; so an initial grid filled with zeroes except for a lone 1 somewhere cannot possibly be transformed to a constant grid. As I say, the previous paragraph assumes no moves are allowed along the edges (or more generally that no moves are allowed which alter S). dave ============================================================================== Date: Wed, 11 Feb 1998 18:22:18 +0000 From: Joshua Bao Dave Rusin wrote: > What do you allow around the edges? Can I increase just one edge cell (e.g. > the (1,3) cell) on the grounds that this is just the visible effect of > a type-1 move centered at the (0,3) spot? No. A move has to be centered on a cell that exist on the grid (i.e., the cell (i,j) with 1<=i<=mand 1<=j<=n). > How about moves centered at > positions like (1,x): is it your intention to allow increasing/decreasing > precisely the entries (1,x-1) (1,x) (1,x+1) and (2,x) ? Yes. A neighbor is increased or decreased as long as both it and the chosen center exists on the grid.I would like to know 1) if all grids are transferable 2) if there is a sytematic process of doing so. I apologize for the imprecision of the statement of the problem. Thank you for your help. J. Bao ============================================================================== Date: Wed, 11 Feb 1998 18:24:02 +0000 From: Joshua Bao Naturally we must assume that n,m>=3. Thanks ============================================================================== From: Dave Rusin To: xxb1@psu.edu > Naturally we must assume that n,m>=3. Thanks Au contraire, I would argue that there's no reason to disallow m,n = 1, 2. Those cases fit just fine into the framework. Let me show you what I came up with. In return, let me ask you to tell me how this particular question arose: I had a good time playing with some of the data during the day! The question concerns the set G of integer matrices of a given size (mxn). I can easily tell you what's possible and what's not for any specific m and n; giving statements for families of pairs (m,n) would require actual work :-). There are some natural conjectures, as you'll see. We have a number of "moves" on this set G of matrices, each of which adds or subtracts a matrix M(i,j), defined to be a certain sum of up to five "unit" matrices del(k,l) (that is, each entry of the matrix del(k,l) is zero except the (k,l) entry, which equals 1). Specifically, we have M(i,j) = del(i,j) +del(i-1,j), if i>1 +del(i+1,j), if i1 +del(i,j+1), if j of the quotient group G/H. So the question about the existence of the transformation amounts to giving a description of the subgroup H of G, as well as the intermediate subgroup < H, J > of G. If M can be transformed to xJ, there may be more than one way to do so. But if M + Sum( a(i,j) M(i,j) ) = xJ , then we'll also have M + Sum( b(i,j) M(i,j) ) = yJ iff Sum( [a(i,j)-b(i,j)] M(i,j) ) = (x-y)J , that is, our only option to change the a(i,j) is to add to them some numbers c(i,j) with Sum( c(i,j) M(i,j) ) = zJ for some z. These c's are easy to find: First, if any such numbers c(i,j) exist which makes z > 0, choose a set of them c0(i,j) which gives the least possible positive z; otherwise let c0(i,j) = 0 for all i,j. Second, compute the kernel of f, which is a finite-rank free abelian group. That is, find a "basis" collection of n*m-tuples c1(i,j), c2(i,j), etc. with the property that Sum( c1(i,j) M(i,j) ) = 0 and likewise for c2, c3, ... Then your general choices for the c's are to take n*m-tuples of the form c(i,j) = a0*c0(i,j) + a1*c1(i,j) + ... for arbitary integers a0, a1, ... Thus you can enumerate all the possible "moves" which take the initial matrix M to a multiple of J: you use "move" M(i,j) this many times: a(i,j) + [a0*c0(i,j) + a1*c1(i,j) + ...] here the numbers a0, a1, ... are arbitrary but apparently you wish to minimize the sum of the absolute values of these n*m expressions. The number of degrees of freedom at your disposal exclusive of a0 (that is, the number of variables a1, a2, ... above) is the free rank of the kernel of f, which equals the rank of the cokernel, which is the rank of the group G/H. These can be determined as the dimension of the kernel of the integral matrix representing the map f. In the "nice" case that all these ranks are zero, the determinant of that integral matrix equals the cardinality of the finite group G/H (in absolute value). Let me translate these last few paragraphs into English in a few special cases. m=1,n=3: You have 3 "moves", which correspond respectively to adding (or subtracting) the following matrices from a general 1x3 matrix: M(1,1)=[1 1 0] M(1,2)=[1 1 1] M(1,3)=[0 1 1] So here f is the map f: Z^3 -> G given by sending the three generators to those matrices. Using standard coordinates for G this f is represented by the 3 x 3 matrix [ 1 1 0 ] [ 1 1 1 ] [ 0 1 1 ] whose columns contain the entries of the M(i,j)'s. This matrix has determinant -1, so G/H is a group of order 1, i.e., all of G is in H, which in turn means every integer 1x3 matrix is an integer linear combination of the M(i,j); indeed [x y z] = (y-z) M(1,1) + (x+z-y) M(1,2) + (y-x) M(1,3). Those three coefficients are the a(i,j). Now, J also is a linear combination of the M(i,j) of course: it's 0M(1,1)+ 1M(1,2) + 0M(1,3); those are the c0(i,j). The kernel of f in this problem is just the zero vector, so there are no a1, a2, ... to play with. Following my general formula, I announce that the only "moves" which take [x,y,z] to a multiple of J are (y-z+a0*0) M(1,1) + (x+z-y+a0*1) M(1,2) + (y-x+a0*0) M(1,3) The total number of moves then is |y-z| + |x+z-y+a0| + |y-x| With x, y, and z given, and only a0 variable, your only hope to minimize this is to use a0= y-x-z, which in this case means "don't use any moves M(1,2)". Now let's try a different combination, m=2,n=2: Now you have four "moves", namely adding/subtracting M(1,1) = [ 1 1 ], M(1,2) = [ 1 1 ], M(2,1) = [1 0], M(2,2)=[0 1] [ 1 0 ] [ 0 1 ] [1 1] [1 1] Now f is a map from Z^4 to G. Using standard coordinates in G (that is, reading off the entries of a matrix by rows) we thus represent f by a 4x4 matrix [ 1 1 1 0 ] [ 1 1 0 1 ] [ 1 0 1 1 ] [ 0 1 1 1 ]; you can see the M(i,j)'s in the columns again. This time the matrix has determinant -3, so G/H is a group of order 3. Some matrices are _not_ linear combinations of the M(i,j) (for example J isn't). On the other hand, a group of order 3 is cyclic, so J must then generate G/H: _every_ matrix can be transformed using your moves to a multiple of J. In fact, it's easy to see which multiple(s) will do: all four moves preserve the sum s of a matrix's four entries, mod 3, while the sum of the entries of J is 1 mod 3. So a matrix can only be transformed to sJ. Now let's look at the minimality problem. We can't get J as a combination of the M(i,j), but 3J we can do: it's just the sum of the M(i,j). Thus we have c0(i,j) = 1 for all four (i,j)'s. Again in this problem f has no kernel, so there are no c1's, c2s, etc. So here's what we do: given a matrix M we write M - sJ as a sum of the M(i,j)'s, say a(1,1)M(1,1) + a(1,2)M(1,2) + a(2,1)M(2,1) + a(2,2)M(2,2). The the only options for change we can do is to replace a(i,j) by a(i,j) + a0*c0(i,j) = a(i,j) + a0. The total number of moves used would be |a(1,1) + a0| + |a(1,2)+a0| + |a(2,1)+a0| + |a(2,2)+a0| You can show that the minimum value of this expression is attained by taking a0 to be any number between the negatives of the two medium-most a(i,j)'s. Let me show you what I mean: if you have to start with M = [ 6 9] [ 7 10] then s = (6+7+9+10) mod 3 = 2 mod 3, so M - 2J = [ [4 7 ] [5 8] ] should be in the image of f. Indeed, solving the four linear equations or inverting the 4x4 matrix shows that M-2J is a sum 0 M(1,1) + 3 M(1,2) + 1 M(2,1) + 4 M(2,2) Sorting the coefficients (0,1,3,4) picking a number between the middle two (2) and negating (-2) gives an optimal a0, that is we can use -2 M(1,1) + 1 M(1,2) + (-1) M(2,1) + 2 M(2,2), a total of only 6 moves, to change M into 4J; 6 is minimal here. The next level of difficulty appears with m=3,n=4. Now you have 12 distinct moves. The map f : Z^12 -> G is represented by a 12x12 matrix whose determinant is -9, i.e., only one matrix out of 9 is a combination of the 12 M(i,j). In this case, J is not in H either, but 3J is -- it's the sum of the 10 M(i,j)'s "around the edge". So J is only an element of order 3 in the group G/H of order 9. That means the quotient group G/ still has order 3, i.e, one matrix out of three can't even be transformed into a multiple of J. An example is the matrix del(1,1): it cannot be transformed to a multiple of J. (On the other hand, 3 times it _is_ a linear combination of the M(i,j); in fact, here are the multipliers you need for those 12 moves: [ 3 1 -2 0] [-1 -2 1 2] [ 0 1 1 -3] The fact that G/ is cyclic of order 3 implies that there is some weighted sum of the 12 entries of a matrix which must come out to be zero mod 3 for the matrix to be reducible by your 12 moves to a multiple of J. I haven't worked out yet what that sum is. As far as the minimality stuff goes, once you have _some_ set of 12 multipliers for the M(i,j) to transform a specific M to a multiple of J, then since once again f has no kernel your only recourse to change those multipliers c(i,j) is to add to each the term a0*c0(i,j) (where the c0's are the entries in the 3x4 matrix shown above). Again it's true that to minimize the total number of moves you should choose a0 so as to get one of the multipliers c(i,j)+a0*c0(i,j) as close to zero as possible; there's no particularly easy way to tell which one, but hey, there are only 12 such expressions to play with and each would suggest just one optimal a0. Try all 12 and select the best. The fun really begins with a case like m=2,n=3. Same deal: 6 "moves" implies a map f: Z^6 -> G represented by a 6x6 matrix. Only this time the determinant is _zero_. That means there are matrices in G _no multiple of which_ is a linear combination of the 6 M(i,j)'s, that is, G/H is an infinite group. The problem is that if you take this combination of the coefficients in any matrix in H: [-1 0 1] (I'll write Q for this matrix below) [ 1 0 -1] you'll get zero, that is, all of H -- even fractional combinations thereof -- lies in the orthogonal complement of this element of G. In fact, it's clear that J is in that orthogonal complement, too. That's about as bad as it gets though: if this "alternating sum" of entries of M is zero, then M is a least a _fractional_ combination of the M(i,j). (I haven't looked at the denominators yet, that is, I don't know how big the finite group (Q^\perp)/H is.) So a matrix like del(1,1) has the property that _no multiple of it_ can be "moved" to any multiple of J. That's something new. The flip side of this is that since f has a kernel, we have more flexibility in choosing our multipliers. The matrix Q lies in the kernel of f, that is, its entries are the previously-un-encountered c1(i,j)'s. If a matrix M has been written as sum( c(i,j) M(i,j) ), then since J = M(1,1) + M(2,3), we can add to the c(i,j)'s any multiple of these c0(i,j) (which are =1 for (i,j)=(1,1) or (2,3) and =0 for other (i,j)'s, if you're still with me!); this much is just like previous paragraphs. But we can also add in any multiple of the c1's ! That is, every sum sum( [c(i,j)+ a0*c0(i,j) +a1*c1(i,j)] M(i,j) ) will yield a matrix of the form M + xJ where now a0 AND a1 are arbitrary. This gives you two parameters to play with to try to minimize the total number of operations used. Well, the analysis of other pairs (m,n) proceeds similarly. In many cases, f has a nonzero determinant, so that G/H is finite: a matrix M need only pass a certain linear modularity requirement to be reducible to zero, and a weaker modularity requirement to be reducible to a multiple of J. In other cases, a stronger requirement must first be passed: some linear condition must be passed on the nose (i.e. not mod N for any N). Interestingly, almost all the conditions I've found so far are built up from Q! For example, for 2 x 5 matrices, it's this combination of the coefficients which must vanish: [ -1 0 1 0 -1 ] [ 1 0 -1 0 1 ] and the pattern repeats for 2x7 matrices, etc. For 3x5 matrices we extend the transpose of Q: the appropriate condition is that this sum of coefficients must be zero: [ 1 -1 0 1 -1 ] [ 0 0 0 0 0 ] [ -1 1 0 -1 1 ] and the extra 3 columns are tacked on again for 3x8's, etc. Turn sideways again and extend to the right by alternating signs, and you get a condition for 5x5 matrices, which can then be extended for 5 x 7 matrices, ... Actually for 5x5 matrices, there's an _additional_ condition a matrix must satisfy to be reducible to a multiple of J, which is simply the linear combination of the entries, using coefficients obtained from the _transpose_ of the previous 5x5 matrix. (This in turn can be extended rightward to give linear conditions for 5x8 matrices, 5x11, ...). The fact that there are two distinct linear tests to pass is a restatement of the fact that f has a kernel of rank 2; this in turn means that when a matrix _is_ reducible to a multiple of J, you can adjust the multipliers c(i,j) by adding in arbitrary multiples of _three_ 25-tuples, c0(i,j), c1(i,j), and c2(i,j); that is, you have three free parameters a0, a1, a2. (This kernel-of-rank-2 phenomenon first shows up with 4x4 matrices; I just skipped over it because the corresponding linear conditions are not so obviously related to Q; instead, they are given by the matrices [ 0 1 -1 0] [-1 0 0 1] [ 1 0 0 -1] [ 0 -1 1 0] and [ 1 0 0 -1] [-1 -1 1 1] [ 1 1 -1 -1] [-1 0 0 1] Now these patterns can be repeated after columns of zeros to give conditions for 4x9 matrices, ...; repeating also downward gives the conditions for 9x9 matrices.) Oh, I almost forgot: you have a similar condition even for 1xn matrices with n=2, 5, 8, ... : your "moves" cannot take (any multiple of) a matrix [q1, q2, q3, ...] to a multiple of J unless 0 = (q1-q2)+(q4-q5)+(q7-q8)+... that is, you can play these games with 1x2, 1x5, 1x8, ... matrices using the coefficients in [1 -1], or [1 -1 0 1 -1], or [1 -1 0 1 -1 0 1 -1], ... respectively. Let me close with some of the data I have computed. These numbers give the determinants of the matrices f; their absolute values give the size of the groups G/H. When there's a number in parentheses, that means det(f)=0, i.e. G/H is infinite; in that case, the number in parentheses is (the rank of G/H) = (the rank of the kernel of f) = (the number of linear conditions imposed) = (number of free parameters a1, a2, ...) = ... In all cases in the table, this is also the rank of G/. (I did not try to compute the sizes of the smaller groups G/ when finite.) n= m=1 m=2 m=3 m=4 m=5 m=6 m=7 m=8 m=9 1 1 (1) -1 -1 (1) 1 2 -3 (1) 5 (1) -7 3 -7 -9 (1) -7 119 4 (2) 55 29 279 -95 (2) 5 (2) -1183 (1) (1) 6 2197 -791 28672 * 7 -34391 (1) 8 -4002939 9 (2) Observations: (1)In all cases the group G/H is finite unless it's possible to write down an "obvious" obstruction using the matrix Q as above (or one of the 4x4 replacements also shown above); indeed, even when G/H is infinite, its rank is just the number of these "obvious" obstructions. (2)A multiple of _every_ 6xn matrix is reducible, that is, G/H is finite for all cases with m=6! I carried out the row m=6 further; these are the numbers I got (all nonzero!) starting with m=9: -165271, -79507, -587951, -383643, -49887279, 71532937, 22923223 That checks even as far as 6x15 matrices! (3)It would be of interest to determine the structure of these finite abelian groups G/H and in particular to determine the position of J in them (e.g. is it a generator?) Finally, I enclose the Maple program I used to get these numbers, should you wish to play with them further. Well, as you can see, I had a good time thinking about your questions. Now perhaps you can tell me how you got interested in these? Is this from some game, perhaps? dave ------------------------------------------------------------------------------ #Maple program. with(linalg): #just load this once m:=2:n:=3: #or whatever F:=matrix(m*n,m*n): for i from 1 to m*n do for j from 1 to m*n do F[i,j]:=0:od:od: for i from 1 to m do for j from 1 to n do k:=(j-1)*m+i: F[k,k]:=1: if i>1 then F[k,k-1]:=1:fi: if i1 then F[k,k-m]:=1:fi: if j Dave Rusin wrote: > > Naturally we must assume that n,m>=3. Thanks > > Au contraire, I would argue that there's no reason to disallow m,n = 1, 2. > Those cases fit just fine into the framework. Let me show you what I came up > with. In return, let me ask you to tell me how this particular question arose: > I had a good time playing with some of the data during the day! Thank you for the extensive analysis !! A special case of the problem comes from a chinesepuzzles book. I would also like to know a way to find 'move's to transfer the given matrix to the form of xJ(all elements are same integer) where the x is an given integer. Clearly, this is much easier - all we need to do is solve a system of linear integer (diophantine) equations. Is there a systematic method of doing this (with matrix and integer operations), particularly when G/H is infinite ? Thanks. Sincerely, J. Bao ============================================================================== Date: Mon, 16 Feb 1998 10:48:39 -0600 (CST) From: Dave Rusin > I would also like to know a way to find 'move's to transfer > the given matrix to the form of xJ(all elements are same integer) I don't know if there's anything more elegant than brute force. You are given an mxn matrix M and m*n matrices M(i,j) of the same size; you want to solve m*n equations in m*n+1 unknowns Sum x(i,j) M(i,j) = M + x J Well, that system of linear equations may be written as a single matrix equation A X = B where A is an m*n by m*n+1 matrix, and X and B are columns of the appropriate sizes. You can do row-reduction to determine the solutions, but since you want to find all _integer_ solutions, you need to do this without division. It turns out that you can reduce all integer matrices to a canonical form this way (I think it's usually called "Smith normal form"). If you view ordinary row-reduction as writing every matrix A in the form U Z V with U and V invertible and Z of the special form [ identity matrix possible zeros ] [ possible zeros possible zeros ] then the right statement for integer matrices is that one can do row-reduction without division and write A = U Z V where U and V are integral matrices with integral inverses, and Z has the form [ diagonal matrix possible zeros ] [ possible zeros possible zeros ] where the diagonal entries satisfy d1 | d2 | d3 | ... and all d_i > 0. With those conditions, Z is unique (U and V are not). In this case, the equation A X = B may be written Z (V X) = U^(-1) B which is then easy to solve: there is no solution unless the rows of U^(-1)B are zero whenever the corresponding row of Z is zero (those are the rows at the bottom of Z), and there is no solution unless the i-th row of U^(-1) B is a multiple of d_i. Otherwise there are solutions, and it's clear how to get them: the i-th entry of (VX) must be (i-th entry of U^(-1)B)/(d_i) and the entries of VX corresponding to the zero rows of Z are arbitrary. That is, the solutions have the form (VX) = W_0 + [0, 0, ..., r_1, r_2, ...]^t (I write []^t for the transpose of a row vector rather than trying to type out a column vector on my screen!) Here the r_i are arbitrary integers. Then you have the solution to your original problem: X = V^(-1) ( W_0 + [0, 0, ..., r_1, r_2, ...]^t ) The entries of this column matrix describe the complete solution for your unknowns x(i,j). Since I'm sure I've lost you at this point, let me do an example. Suppose you wanted to find moves taking M = [ 1 2 3 ] [ 4 8 6 ] to a multiple of the identity. We need to find 7 unknowns which make sum( x(i,j) M(i,j) ) = M + x J, that is, x(1,1)[ 1 1 0] + x(1,2)[1 1 1] + x(1,3)[0 1 1] + [ 1 0 0] [0 1 0] [0 0 1] x(2,1)[ 1 0 0] + x(2,2)[0 1 0] + x(2,3)[0 0 1] - x [1 1 1] = [1 2 3] [ 1 1 0] [1 1 1] [0 1 1] [1 1 1] [4 8 6] So I get 6 equations in the 7 unknowns. I peel off the coefficients of each unknown in the usual fashion to get a matrix equation A X = B : [ 1 1 0 1 0 0 -1] [x(1,1)] [ 1 ] [ 1 1 1 0 1 0 -1] [x(1,2)] [ 2 ] [ 0 1 1 0 0 1 -1]*[x(1,3)] =[ 3 ] [ 1 0 0 1 1 0 -1] [x(2,1)] [ 4 ] [ 0 1 0 1 1 1 -1] [x(2,2)] [ 8 ] [ 0 0 1 0 1 1 -1] [x(2,3)] [ 6 ] [ x ] I can perform all the "U^(-1)" work described above by simply doing row- reduction using integer transformations in the usual methodical fashion: [ 1 0 0 0 1 -1 0 | -1 ] [ 0 1 0 0 -1 0 0 | -3 ] [ 0 0 1 0 1 1 -1 | 6 ] [ 0 0 0 1 0 1 -1 | 5 ] [ 0 0 0 0 2 0 0 | 6 ] [ 0 0 0 0 0 0 0 | 0 ] I can further reduce using column operations, although this will alter the solution set as I'll describe below. But by adding multiples of the first four columns to the other columns, we can clear achieve the matrix Z = [ 1 0 0 0 0 0 0 ] [ 0 1 0 0 0 0 0 ] [ 0 0 1 0 0 0 0 ] [ 0 0 0 1 0 0 0 ] [ 0 0 0 0 2 0 0 ] [ 0 0 0 0 0 0 0 ] Here d1=d2=d3=d4=1, d5=2. There is a zero row, but it's opposite a zero in the right-hand column "U^(-1)B". Likewise, the 5th entry of that column (=6) is a multiple of d5 (=2). Thus there are integer solutions to the original problem. All the solutions to Z (VX) = U^(-1)B are clearly of the form (VX) = [ -1 ] <- just dividing by d1=1 here [ -3 ] [ 6 ] [ 5 ] [ 3 ] <- had to divide by d5=2 here [ r_1] <- any arbitrary integer here [ r_2] <- ... and here (Z had two columns of zeros) (That's "W" in the discussion above). Now, V is the matrix for which A' = ZV, where A' was the result of doing just the row operations. It's straightforward to see that V^(-1) = [ 1 0 0 0 -1 1 0 ] [ 0 1 0 0 1 0 0 ] [ 0 0 1 0 -1 -1 1 ] [ 0 0 0 1 0 -1 1 ] [ 0 0 0 0 1 0 0 ] [ 0 0 0 0 0 1 0 ] [ 0 0 0 0 0 0 1 ] (That is, V^(-1) is built from the same "blocks" as A', with sign changes off the diagonal.) Thus we recover our solutions X by multiplying (VX) by this V^(-1) on the left: [x(1,1)] [-4+r1 ] [x(1,2)] [0 ] [x(1,3)] =[3-r1+r2] [x(2,1)] [5-r1+r2] [x(2,2)] [3 ] [x(2,3)] [r1 ] [ x ] [r2 ] So now you know just what moves are possible to turn the original M into xJ: use (-4+r1) of the first, none of the second, etc. Here, a negative number of moves means to subtract 1's from certain spots rather than add them, of course. Total number of moves is then |-4+r1| + |0| + |3-r1+r2| + |5-r1+r2| + |3| + |r1| = |-4+r1| + |3-r1+r2| + |5-r1+r2| + |r1| + 3. The minimum value of this expression across the entire r1-r2 plane is 9, which occurs in a box bounded by r1=0, r1=4, r2-r1=-3, r2-r1=-5. So for example you could use r1=4 and r2=0, meaning 0, 0, -1, 1, 3, 4 moves of types 1, 2, ..., 6 respectively to go from xJ = r2 J = the zero matrix to the original matrix M. You can check this directly. As it turns out, there is enough of a pattern to the M(i,j) that you can expect the matrix A to have a pattern, too, making it plausible that the computations can be done more elegantly. But for small m and n this procedure is fairly efficient as it stands. dave ============================================================================== [More mail received -- djr ] Date: Wed, 09 Dec 1998 01:30:09 -0500 (EST) From: Chris Ruebeck Subject: Analysis of games To: Dave Rusin I recently saw your web pages about games and their solutions. There is a game I've seen called "All lights". Basically the 2-D grid turns on or off the nearby squares (3 of them if in the corner, 4 if on edge, 5 if not in corner or on edge). The goal is to turn on the 25 lights. I've found solutions for the 3x3 and 4x4 grids, but not the 5x5 grid. Know of analyses or directions to work? My description may have been lacking. Try these any of these links for Java versions. http://novatrain.com/java/lightson.html http://www.troysplace.com/gamesallLights.html http://www.pagelinx.com/alllights.html Thanks for any thoughts. I'd love to learn some math that can address this question! Chris ruebeck@jhu.edu http://www.econ.jhu.edu/people/Ruebeck/ ============================================================================== [Another -- the "attachment" is a zipped Postscript file available here: http://www.math.niu.edu/~rusin/uses-math/games/other/lo.zip It's nicely written. --djr] From: "=?iso-8859-1?B?03NjYXIgTWFydO1u?=" To: "Dave Rusin" Subject: Our paper on Lights Out, finally. Date: Mon, 11 Oct 1999 20:15:54 +0100 Dear Dave: It has been a long time since we were in contact. First of all, we want to thank you one more time for your help, and also for your patience. At last, we have been able to complete the paper, a copy of which is attached to this message in (zipped) PS format. It has been registered as a technical report in the Universidad Complutense de Madrid, and it has also been submitted for publication to "The Mathematical Intelligencer". This should be considered as a preprint (indeed, a couple of errors have still slipped). Besides, we have made freely available a Windows implementation of the game in which you can play several variations and generalizations. You can get it at http://dalila.sip.ucm.es/miembros/cpareja/lo We hope you'll enjoy both the paper and the game, and would be happy to read your comments on the subject. If you want to enrich your web site with pointers on Lights Out, you'll find a couple of them in the references of our paper. Cristobal Pareja (cpareja@sip.ucm.es) Oscar Martin (oscar@poboxes.com)