The Mathematics Of Lights Out Pdf

The Mathematics of Lights Out

References

A good simple reference for the mathematics is Issue 7/8 of Cubic Circular (David Singmaster, Summer 1985) which has an analysis of the XL-25, and some of the information below is based on that. There are many mathematical research papers which are related to the game, and have some interesting results that I won't be able to prove here. Here is a list of some of the better ones:

[AF] Turning Lights Out with Linear Algebra, by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4, October 1998, pp. 300-303.
[CG] Loop Deletion for the Lamp Lighting Problem, by William Y. C. Chen and Nancy S. S. Gu.
[DW] Universal Configurations in Light-Flipping Games, by Yevgeniy Dodis and Peter Winkler (2001). Proceedings of 12th Annual ACM/SIAM Symposium on Discrete Algorithms, January 2001, pp. 926-927.
[EES] Note on the lamp lighting problem, by Henrik Eriksson, Kimmo Eriksson and Jonas Sjöstrand (2001). Adv. Appl. Math., vol. 27, pp. 357-366.
[GTK1] Setting Switches in a Grid, by John Goldwasser, William F. Klostermeyer, George E. Trapp, and C. Q. Zhang (1995). Technical Report TR-95-20, Dept. of Statistics and Computer Science, West Virginia University.
[GTK2] Characterizing Switch-Setting Problems, by John Goldwasser, William F. Klostermeyer, and George E. Trapp (1997). Linear and Multilinear Algebra, vol. 43, pp. 121-135.
[GK1] Maximization Versions of "Lights Out" Games in Grids and Graphs, by John Goldwasser and William F. Klostermeyer (2002). Congressus Numerantium, vol. 126, pp. 99-111.
[GKW] Fibonacci Polynomials and Parity Domination in Grid Graphs, by John Goldwasser, William F. Klostermeyer and Henry Ware (2002). Graphs and Combinatorics, vol. 18, pp. 271-283.
[GK2] Odd and Even Dominating Sets with Open Neighborhoods, by John L. Goldwasser and William F. Klostermeyer. To appear in Ars Combinatoria.
[GWW] Does the lit-only restriction make any difference for the σ-game and σ⁺-game?, by John Goldwasser, Xinmao Wang, and Yaokun Wu (2008). To appear in the European Journal of Combinatorics.
[HMP] Chebyshev polynomials over finite fields and reversability of σ-automata on square grids, by Markus Hunziker, António Machiavelo, and Jihun Park.
[Kl] Lights Out!: A Survey of Parity Domination in Grid Graphs, by William F. Klostermeyer.
[SF] Two Reflected Analyses of Lights Out, by Óscar Martín-Sánchez and Cristóbal Pareja-Flores (1998). Math Magazine, vol 74 (2001), pp. 295-304.
[St] Lights Out Series Z, by Jon Stadler. Math Magazine.
[ST] Algebraic Approaches to FlipIt, by Josef Schicho and Jaap Top. The Resolution of Singular Algebraic Varieties, Clay mathematics Proceedings, vol. 20 (2014), pp 319-325.
[Su] σ-Automata and Chebyshev-Polynomials, by Klaus Sutner (1996). Theoretical Computer Science, vol. 230, (2000), no. 1-2, pp. 49-73.

The basic linear algebra

Consider the lights as a list (or vector) of 25 values, 0 if the light is off, or 1 if the light is on. Thus any position can be written as such a vector of 25 noughts and ones. The effect of a button press (or several presses) can also be written as a list of 25 bits; 0 of a light does not change, and 1 if a light changes because of the button pattern. If you apply a button pattern to a particular position, then the result is described by a vector which is the sum of the two vectors modulo 2. This means that the result for a particular light is computed by adding the corresponding entries in the two vectors, and that if we have two ones then the result of 1+1 should be 0 (a light which is on, and is changed by a button pattern, will be off afterwards). You might also consider this an 'Exclusive Or' operation on a 25 bit word.

Summation is commutative, in other words it doesn't matter in which order we add things up. This means that it also doesn't matter in which order vectors are added up, and therefore the effect of several button presses is simply the sum of their individual effects in any order. Such summation of vectors can be written as a matrix multiplication.

Lets work out the matrix algebra explicitly:
Let A be a matrix where a_ji is 1 if light i is changed by button j, or 0 otherwise.
Let p be starting position vector, i.e. p_i is 1 if light i is on at the start, 0 otherwise.
Let x be the button pattern we press, i.e. x_j is 1 if we press button j, or 0 if not.
Let r be the end position vector, i.e. r_i is 1 if light i should be on at the end, 0 otherwise.

The state of light i afterwards is then given by its state at the beginning, plus the effects of all the button presses have on it. Algebraically this is

r_i = p_i + Sum_j x_ja_ji

or in matrix form (using row vectors):

r = p + x A
or
x A = r - p = c

Here c = r-p is the difference between the start and end position, or in other words the pattern of lights that have to be changed. Normally we know A and c (we know what the buttons do, and which lights we want to change), and want to find out x (the buttons we have to press to do it). This essentially boils down to solving 25 equations in 25 unknowns, which is a lot of work to do by hand, each time you want to solve the puzzle. If however we can invert the matrix A, we get:

x = c A^-1

This makes it a lot simpler; to solve any position, all we have to do is plug in the numbers, and out comes the button pattern we need. Each light pattern will directly give a unique button pattern needed to solve it. Such a game is completely solvable, i.e. every light pattern can be solved.

Lets call the entries of the A^-1 matrix b_ij, and examine them more closely. Suppose we try to only change light k, so c_k=1 and all other c_i=0. This isolates one row of the matrix:

x_j = Sum_i c_i b_ij = b_kj

This means that the rows of A^-1 are the button patterns that change each light individually. Calculating A^-1 from A is fairly straightforward, and can be found in any linear algebra book. We will do this later.

The (pseudo)inverse

Unfortunately not every matrix A that occurs in this context is invertible. This happens when it is not possible to find a button pattern for each light that changes only that light and no others. In other words, the lights are not all independent from each other. The rank m of a matrix A is the number of rows that are independent from each other. In the standard game, the rank of A is m=23, because the effect of two moves can be simulated by using the other 23 buttons.

All is not lost when A is not invertible. Instead of using all the lights, and all the buttons, we use only the independent buttons, and their lights. In the normal game we therefore no longer use the 25×25 matrix A, but a 23×23 matrix which is invertible.

There are however practical reasons for using the full matrix A. For a start, we don't know beforehand what the rank is of matrix A, and only find this out when trying to calculate its inverse. Furthermore, the pseudo-inverse B we get in that case has as a sub-matrix the inverse of the smaller matrix, together with rows containing (generators of) the quiet button patterns, i.e. those button patterns that have no effect on the lights at all.

Below on the left is the full 25×25 matrix A, and on the right is an identity matrix of the same size:

1100010000000000000000000 1000000000000000000000000 1110001000000000000000000 0100000000000000000000000 0111000100000000000000000 0010000000000000000000000 0011100010000000000000000 0001000000000000000000000 0001100001000000000000000 0000100000000000000000000 1000011000100000000000000 0000010000000000000000000 0100011100010000000000000 0000001000000000000000000 0010001110001000000000000 0000000100000000000000000 0001000111000100000000000 0000000010000000000000000 0000100011000010000000000 0000000001000000000000000 0000010000110001000000000 0000000000100000000000000 0000001000111000100000000 0000000000010000000000000 0000000100011100010000000 0000000000001000000000000 0000000010001110001000000 0000000000000100000000000 0000000001000110000100000 0000000000000010000000000 0000000000100001100010000 0000000000000001000000000 0000000000010001110001000 0000000000000000100000000 0000000000001000111000100 0000000000000000010000000 0000000000000100011100010 0000000000000000001000000 0000000000000010001100001 0000000000000000000100000 0000000000000001000011000 0000000000000000000010000 0000000000000000100011100 0000000000000000000001000 0000000000000000010001110 0000000000000000000000100 0000000000000000001000111 0000000000000000000000010 0000000000000000000100011 0000000000000000000000001

Note that each row of the right matrix is a button pattern (with only one button press), and when that pattern is pressed the light pattern is given by the same row in the left matrix. To find the (pseudo) inverse, we use row operations on this combined 25×50 matrix (i.e. swap any two rows, or add one row to another) until the left half has become the identity (or as close to the identity as we can get). During this process, we always have light patterns and corresponding button patterns on each row. After doing this process, called Gaussian elimination, we get this result:

1000000000000000000000001 0111000101000110000100000 0100000000000000000000010 1101101000001110001000000 0010000000000000000000011 1011110110001101111101000 0001000000000000000000010 1110001000000000100011100 0000100000000000000000001 0110110000101010010111000 0000010000000000000000011 0010101101001000001100000 0000001000000000000000000 0101011011000101110001000 0000000100000000000000011 1010010110000011010110100 0000000010000000000000000 0010001110100111001001100 0000000001000000000000011 1000011000101010110100100 0000000000100000000000010 0000100011001011111001000 0000000000010000000000010 0000000000000000100011100 0000000000001000000000000 0110110001101100010011000 0000000000000100000000010 1110001010001110001000000 0000000000000010000000010 1100100111100111101010000 0000000000000001000000011 0010001110100011010110100 0000000000000000100000000 0011001001110010111000100 0000000000000000010000011 0010101101101001101110000 0000000000000000001000000 0110010010100110111000100 0000000000000000000100011 1010110101000001010110100 0000000000000000000010001 0001100100011011010111000 0000000000000000000001010 0011101010111000000011100 0000000000000000000000111 0001000111010001101101000 0000000000000000000000000 0111010101110111010101110 0000000000000000000000000 1010110101000001010110101

The square matrix on the right is the pseudo-inverse of the matrix A.

Here are some neat facts that can be deduced from these matrices:

• There is a 23×23 identity matrix on the left. This shows that by using the button patterns (given by the rows on the right) we can turn on each of those 23 lights on or off, but that the state of the last two lights is then forced.
• The bottom two rows on the right show two quiet patterns (the third is given by the sum of the two rows).
• There are five rows on the left that contain a single 1, so there are only five lights that can be switched on individually.
• If you add all the rows of the left matrix together, you clearly will get 23 ones, but the last two columns also sum to ones. This shows that it is possible to switch on all lights. The button pattern needed to do that is given by the sum of all the rows of the right matrix (last two rows optional).

Note that if you want to analyse a game by hand, these matrices are all far too large. In the standard game, it is easier to use the fact that you can chase the lights. Press a button on the top row, chase the lights down, and see the effect on the bottom row. This way there are 5 possible button presses (the top row) with their effect on 5 lights (the bottom row). This leads to a much smaller matrix, only 5×5 on the standard game. It looks like this:

01101 10000 11100 01000 11011 00100 00111 00010 10110 00001

This reduces to:

10001 11000 01010 11100 00111 01100 00000 01110 00000 10101

From this, nearly all the facts listed before can be deduced.

Solving in the minimal number of moves.

On the main page I have already explained how to solve a particular position in the minimal number of moves, by finding any solution and then combining it with any quiet pattern to reduce the number of moves as much as possible. What is the worst position to solve, and how many moves does that take?

Below I have marked the 5×5 grid with the letters a-d, separating the squares into four sets.

c	b	a	b	c
a	d	a	d	a
b	b	d	b	b
a	d	a	d	a
c	b	a	b	c

The three non-trivial quiet patterns of the game are given by the squares a and b, b and c, or a and c. The squares d are not part of any quiet pattern. Suppose we have a position that is most difficult to solve, and have an optimal solution to it. We can assume the solution uses A+B+C+D button presses, where A,B,C,D are the number of buttons of each set that were pressed (so 0<=A,B<=8, 0<=C<=4, 0<=D<=5). If we apply to our solution the quiet pattern formed by a and b, the number of buttons used in the solution becomes (8-A)+(8-B)+C+D. Since we have assumed that we had an optimal solution, this solution cannot be better. This means that (8-A)+(8-B)>=A+B, or A+B<=8. The other quiet patterns give A+C<=6 and B+C<=6. If we maximise A+B+C+D within these constraints, we reach a maximum of 15 when A=B=4, C=2, D=5.

All the worst positions, those that need at least 15 moves to solve, will use 4 button presses in each of the sets a and b, 2 of the buttons in c, and all of the buttons in d. There are 8!/4!² · 8!/4!² · 4!/2!² = 29400 such button patterns, but these only correspond to 29400/4 = 7350 light patterns.

I originally used this method to calculate the number of positions that need n button presses to solve for each n<=15. This was then adapted to calculate the number of positions of the Lights Out Cube at each distance, shown on the tables page.

Some general definitions.

So far we have used the standard Lights Out game as a basis. We will generalise the theory a little, and must be careful not to implicitly assume that all types of Lights Out game have the same properties.

The matrix A we used is clearly symmetric, i.e. a_ij=a_ji. In terms of the game itself, this means that if pressing one light changes a second light, then pressing that second light will also change the first. This is a very common feature of these games, but it is not necessary. The original Merlin Magic Square game for example is not symmetric (i.e. does not have a symmetric matrix).

Another property of the standard Lights Out matrix is that it is reflexive (i.e. a_ii = 1). In terms of the game itself, this means that pressing a light will always change its own state. The Orbix is not a reflexive game for example, and also the 5×5 matrix above that we got when chasing lights was not reflexive.

The solvability test.

In a symmetric game there is an easy way to test if a pattern of lights can be solved. Well, it is easy once you know the quiet patterns that the game has. I will therefore assume that you have calculated the (pseudo)inverse and therefore have some quiet patterns as given by the bottom few rows of that matrix. Every quiet pattern of the game is the sum of one or more of those rows.

Solvability test:
In a symmetric game a light pattern is solvable if, and only if, the number of lights in common with each quiet button pattern is even.

Proof: Click to hide proof.
By definition, pressing the buttons of a quiet pattern will change each light an even number of times so that in the end nothing has changed. Therefore each and every light is affected by an even number of the buttons in the quiet pattern. The game is symmetrical, so the converse also holds: each and every button will affect an even number of lights in the quiet pattern. A solvable position must have an even number of lights switched on in each quiet pattern arrangement for it to be possible to bring this number down to zero.
All solvable light patterns will certainly satisfy this test. By counting how many patterns pass this test, it can be shown that only solvable patterns qualify because there is no room for any others.

It follows from this test that the only lights that can be switched on or off independently of the others are those that are not in any of the quiet patterns. In the classic 5×5 game there are 5 such squares (in a previous table the ones marked by letter d), the centre and the diagonally adjacent ones. This also shows why, in the 25×25 simplified matrix we got when calculating the pseudo-inverse, the last two columns are nearly the same as the quiet patterns. All this is not necessarily the case in non-symmetric games.

Switching on/off all lights.

Any Lights Out game that is reflexive and symmetric has the nice property that it is always possible to solve the pattern with all lights on.

Theorem 1:
Every reflexive, symmetric variant of the Lights Out game is solvable, i.e. it is possible to switch all the lights off when starting with all the lights on.

In Cubic Circular it says that László Mérõ has proved this result, but the proof is not given. The shortest way to prove it is probably as follows:

Proof 1 of theorem 1: Click to hide proof.
If A is a reflexive symmetric matrix, then modulo 2 we get

x A x ^T = x I x ^T = x x ^T

because all off-diagonal terms occur twice by symmetry and hence cancel modulo 2, leaving only all the diagonal terms (which are all 1 because of reflexivity). If x is a quiet pattern, i.e. xA=0 , then

x x ^T = x A x ^T = 0 x ^T = 0

which means that x must use an even number of buttons. From the solvability check we can then deduce that in every reflexive symmetric Lights Out game we can solve the position with all lights on.
Q.E.D.

It is possible to generalise the theorem a bit. Suppose you have a Lights Out game that is a mix of reflexive and non-reflexive. Some lights act reflexively, meaning that it changes its own state when pressed, while others act non-reflexively. The proof above then shows that a position with only the reflexive lights on will be solvable. See also [DW].

I originally proved theorem 1 in a very different way, not relying on the algebra at all. I prefer this proof, despite the fact that it is much longer. To prove the theorem, I will need to prove a simpler result first.

Lemma:
In a symmetric Lights Out game with an odd number of buttons, there is always some button that affects an even number of other lights. This can also be stated in an equivalent way which is easier to understand: At a gathering of an odd number of people, there is always someone who shakes hands an even number of times.

Proof of lemma: Click to hide proof.
Suppose there are n people at the gathering, with n odd. Let m_i be the number of times that person i shakes hands. The total number of handshakes must therefore be (m₁+m₂+...+m_n)/2, because each handshake has two people taking part. This is a proper integer only if the sum is even, which can only mean that not all m_i can be odd. Therefore at least one person shakes hands an even number of times.

With that lemma, we can get the following proof for theorem 1.

Proof 2 of theorem 1: Click to hide proof.
If there were unsolvable ones, then there would have to be one with the smallest possible number of lights, say n. In other words, any game with n-1 buttons is solvable, but we have a particular game with n buttons that is not.

For any light/button i, the other n-1 buttons and lights form a smaller game and are therefore solvable. Changing all those n-1 lights will however not change light i because we have assumed this game was unsolvable. We can therefore find n patterns which each change everything except for a single light.

Suppose we perform these n patterns which each change all but one light. Every light will now have changed n-1 times. If n were even, this would mean that every light has changed state which would make our game solvable. Therefore our unsolvable game must have n odd.

Suppose there were some button pattern we could press which changes the state of an odd number of lights. For each light that was changed, perform the pattern which changes everything except that light. Now every light will have changed an odd number of times, which again would make the game solvable. Therefore all button patterns in an unsolvable game change an even number of lights.

So far I have proved that the smallest unsolvable game must have an odd number of lights/buttons, and that every button pattern changes an even number of lights. However, if the game is reflexive and symmetric, then from the previous lemma there must be some button which changes an odd number of lights (itself and an even number of others). Therefore there can be no unsolvable reflexive symmetric Lights Out game.
Q.E.D.

It turns out that a very similar proof was found and published a few months before this one (see [EES]). It does not assume the game is symmetric, but assumes its non-symmetric effects form a bipartite graph, a property that symmetric games certainly have (since they don't have any non-symmetric effects). It also applies to Merlin's Magic Square, or in fact to any reflexive game on a rectangular grid where each button affects only some or all of the four neighbouring lights, due to the fact that the grid can be given a checkerboard colouring. Suppose you push all the buttons. This changes every light except those that are affected by an odd number of other buttons. In a symmetric game (and non-symmetric bipartite games) this will leave an even number of lights unchanged, and this is used in the last step of the proof instead of applying the lemma I used.

Corollary:
Every quiet pattern in a symmetric reflexive game has an even number of buttons.
This follows directly from the solvability check of the position with all lights on. (Note - In proof 1 we proved this first in order to prove the theorem. In proof 2 it is done the other way round, the theorem proves this result.)

Pressing only lit buttons.

The Lights Out Deluxe, the Mini Lights Out and the Gamze Lights Out have a variation of the game where you are only allowed to press lit buttons. This makes things a little more complicated.

Theorem 2:
A standard Lights Out game on a rectangular grid which starts completely lit can be switched off by pressing only lit buttons. [EES]

Proof of theorem 2: Click to hide proof.
From theorem 1 it is clear that the pattern with all lights on can be solved. It remains only to be shown that the button presses in this solution can be done in such an order that only lit buttons are pressed. Imagine the grid of buttons marked like a chess board, alternating black and white. First press all the buttons in the solution that are marked black, and then all the buttons that are marked white. Pressing a black button will never change any other black one (because no two black ones are adjacent), so when pressing the black buttons you will always be pressing lit buttons. After pressing the remaining white buttons they will all be off, so before you press them they must have been alight. This is therefore a solution (only one of many).
Q.E.D.

In fact, any pattern that can be solved normally can also be solved by pressing only lit buttons. It may take a few extra button presses however. Note that [EES] contains a supposed counterexample, but that is false.

Theorem 3:
Any solvable pattern of any reflexive symmetric game can be solved by pressing only lit buttons.

I found this remarkably hard to prove. Several of my earlier attempts at proof had holes in them, until I got the following fairly long proof:

Proof 1 of theorem 3: Click to hide proof.
Consider the button pattern that solves the position if it were a regular game. If any of the buttons in the solution are lit, then press them. Eventually you reach a position in which all remaining buttons of the solution are unlit. If any such button b is adjacent to a light l then press lbl. This has the same effect as pressing b alone would have had if it were allowed. Thus we can assume we arrive at a position in which all the remaining buttons of the solution are unlit as well as all their neighbours.

If at this point there are no lights left on, then we are finished. Suppose therefore that there are still lights left on. We can move a light around through an unlit area in the following manner. Suppose there is a path of buttons, a₀ , a₁ , ..., a_k where a₀ is lit, a₁ , ..., a_k are unlit. We can assume that this is the shortest such path between a₀ and a_k , so that each a_i is adjacent to a_i-1 and a_i+1 but not to any others in the path. We can press the move sequence a₀ , a₁ , ..., a_k-1 to light up a_k . We can later undo this by pressing the sequence a_k-2a_k-1a_k-2 , a_k-3a_k-2a_k-3 , ..., a₁a₂a₁ , a₀a₁ . In this way we can bring a light to where it is needed, to allow a move sequence to be performed.

If b is one of the (unlit) buttons of the solution then we know that it has at least one neighbouring button c also part of the solution. If there weren't such a neighbour then pressing all the buttons in the solution would make button b lit, contrary to the fact that it is a solution. So we have two adjacent unlit buttons b and c which are part of the solution.

It must be possible to bring a light to some neighbour of b or c in such a way that neither b nor c is changed, as the shortest path from a light to b or c must pass some neighbour of b or c first. Let n be that neighbour. There are now two cases to consider - n is a neighbour of only one of b or c, or n is a neighbour of both b and c.

Case 1: n is a neighbour of b, but not of c. Let l be the button that was pressed to light up n (so it is a neighbour of n, and is currently unlit). Do the move sequence n bcb l n b. In effect this presses b and c, and undoes the previous press of l. Bring the light of l back to where it came from, and the net effect is that only b and c have been pressed as required. Clearly if n is a neighbour of c but not of b, then the same method applies with b and c interchanged.

Before we do the second case, consider what would happen if b and c had exactly the same neighbours. Pressing both b and c would then leave all their neighbours and themselves unaffected. Thus it is a quiet pattern, and the button presses b and c need not be part of the solution. We can therefore assume that there is at least one button, say m, that is a neighbour of c but not of b (or vice versa).

Case 2: n is a neighbour of both b and c. Let l be the button that was pressed to light up n (so it is a neighbour of n, and is currently unlit). We also have m which is a neighbour of c but not of b. If m and n are not themselves neighbours, then do nl cmc b cn cmc, but if n and m are adjacent then do nl b mnm c. In either case the effect is that this presses b and c, and undoes the previous press of l. Bring the light of l back to where it came from, and the net effect is that only b and c have been pressed as required. Clearly if m is a neighbour of b but not of c, then the same method applies with b and c interchanged.

The previous argument has shown that in a lit-only game the buttons that are part of the regular solution to a position can be pressed in some way regardless of whether they are lit or not. Thus the position can still be solved in the lit-only game provided it is solvable in the normal game.
Q.E.D.

It turns out that the bulk of the proof above can be bypassed. Nevertheless, I'll keep that proof on the page, if only because it gives and explicit method for moving a light around the board. Below is a second, much shorter proof found by Robert Torrence.

Proof 2 of theorem 3: Click to hide proof.
Consider the button pattern that solves the position if it were a regular game. If any of the buttons in the solution are lit, then press them. Eventually you reach a position in which all remaining buttons of the solution are unlit. If any such button b is adjacent to a light l then press lbl. This has the same effect as pressing b alone would have had if it were allowed. Thus we can assume we arrive at a position in which all the remaining buttons of the solution remaining to be pressed are unlit as well as all their neighbours.

The remaining solution buttons only affect themselves and their neighbours, so cannot ever affect any buttons further away. As this set of buttons is a solution in the regular game, all those more distant buttons must be unlit too. This means however that we have arrived at a state with no lights on, which means that there are in fact no buttons left to press at all.

This argument shows that the procedure in the first paragraph converts any solution in the regular game to a solution in the lit-only game. Therefore if a position can be solved normally, then it can also be done by pressing only lit buttons.
Q.E.D.

I first put theorem 3 and its proof on this page in 2004. In the 2008 paper [GWW], the authors cite this page and use somewhat similar ideas to prove a more general result. They show that the lit-only restriction not only still allows you to switch all lights off, it also still allows you to reach any other position that you could reach if that restriction were not there, except for the all-on position. I will copy their proof here. It relies on the following lemma.

Lemma 3a:
Suppose you are pressing buttons in order to change position A to position B in an ordinary symmetric reflexive game. It is always possible to reach B without any intermediate position having all lights on or all lights off. [GWW]

Proof of lemma 3a: Click to hide proof.
Suppose you have a sequence of button presses that changes position A to position B. If the sequence reaches the all-off position more than once, then we can remove from the sequence all moves between the first and last occurrence. The same holds for the all-on position. So we may assume that each occurs at most once. Let m and n be two consecutive moves in that sequence, such that the position reached after pressing m has all lights on or all lights off. If m and n have the same effect on the lights, then we can simply remove the two cancelling moves from the sequence. If they have different effects on the lights, then we might be able to avoid the all-on or all-off position by replacing mn by nm. The only time this fails is if mn toggles all lights, because then we have simply changed the unwanted all-off position with the all-on position or vice versa. In that case let k be any light that is affected by m but not by n, and replace the moves mn in the sequence by the moves kmnk.
In this way we can remove every all-on and all-off position arrived at in the move sequence.

Theorem 3b:
If, in some reflexive symmetric game, you can reach position B from position A, then you can also do so using only lit buttons provided that A has at least one light on and B has at least one light off. [GWW]

Proof of Theorem 3b: Click to hide proof.
From lemma 3a we have a sequence of button presses that transform position A into position B without reaching the all-on or all-off positions in between. We have to show that we can perform this sequence, or its equivalent, even with the lit-only restriction. Let a be the next button in the sequence. If a is lit, it can be pressed. If a is not lit but has a lit neighbour b, then press bab. This leaves only the case where both a and its immediate neighbours are unlit. Seeing as it is not the all-off position, and that pressing a (if it were allowed) would not give the all-on position, there must be some lights on as well as some lights off outside the immediate neighbourhood of a. Suppose there is an on light n and an off light f, both at distance 2 from a. One of the following cases must then occur:

1. 

   There is a button b that is adjacent to a, n, and f. The move sequence nbn a fbf is a lit-only equivalent to pressing a.

2. 

   The button b between a and n and the button c between a and f are not neighbours. The move sequence nbn aca b a fcf is a lit-only equivalent to pressing a.

3. 

   The button b between a and n and the button c between a and f are neighbours. The move sequence nbn cfc a cbc f is a lit-only equivalent to pressing a.

If the lights at distance 2 from a are all on, then there must be a path from a to some off light further away. Let this path be a₀ =a, a₁ , a₂ , ..., a_k , with k>2, where a₀ , a₁ , and a_k , are off and a₂ to a_k-1 are on. Press a_k-1a_ka_k-1 a_k-2a_k-1a_k-2 , ..., a₃a₄a₃ so that a₃ becomes switched off (if k=3, do nothing). Then do a₂ , a₁ a₀ a₁ , a₃ a₂ a₃ to toggle a. Finish with a₄ , a₅ , ..., a_k-1 to return the rest of the path to its previous state.
Lastly, if the lights at distance 2 from a are all off, then there must be a path from a to some on light further away. Let this path be a₀ =a, a₁ , a₂ , ..., a_k , with k>2, where a₀ , to a_k-1 are off and a_k is on. Press a_k , a_k-1 , ..., a₃ so that a₂ becomes switched on and a₃ off. Then do the same as the previous case, a₂ , a₁ a₀ a₁ , a₃ a₂ a₃ to toggle a. Finish with a₂ a₃ a₂ , a₃ a₄ a₃ , ..., a_k-1 a_k a_k-1 to return the rest of the path to its previous state.

Although theorem 3 shows regular solvable positions can always be solved in the lit-only game, it is not guaranteed that it can be done in the same (minimal) number of moves. In other words there may be buttons that need to be pressed twice. The following theorem goes some way to characterize which positions can be solved as lit-only games without extra moves.

Theorem 4:
Given a solvable position in a reflexive symmetric game for which there is a lit-only solution that has the same number of moves as the regular solution. The buttons of the solution consists of one or more regions of connected buttons, which satisfy the following two conditions:

1. Each region has at least one lit button.
2. The number of unlit buttons in a region has the same parity as the number of neighbouring pairs of buttons.

Proof of Theorem 4: Click to hide proof.
This is fairly trivial. Eventually some button in a region will be pressed, so if there aren't any extraneous moves at least one of its buttons must already be lit. If you consider playing the solution in reverse, starting from the solved position, then it is easy to verify that any move in the solution always preserves the parity condition. It follows that the parity condition is a necessary condition for a position to be solvable in the lit-only game.
Q.E.D.

On the right you see an example of a position for which the lit-only solution uses exactly the same button presses as the regular solution. The twelve buttons that form the solution fall apart into three regions:

1. The five buttons at the top left forming a cross. The centre button is lit so the first condition is met. There are four neighbouring pairs (the centre is adjacent to each of the four others), and there are four unlit buttons. These are both even, so the second condition is met.
2. The region of six buttons at the bottom right. Several buttons are lit so the first condition is met. There are six neighbouring pairs (three horizontal and 3 vertical pairs), and there are two unlit buttons. These are both even, so the second condition is met.
3. The single button at the right. It is lit so the first condition is met. There are zero neighbouring pairs and zero unlit buttons. These are both even, so the second condition is met.

The reverse of this theorem is not quite true, but is a reasonable rule of thumb:
Given a solvable position in a reflexive symmetric game. If its regular solution consists of one or more regions of connected buttons which each satisfy conditions 1 and 2 above, then it is most likely possible to press the buttons in such an order that it is a solution to the lit-only game.

This is a pretty good rule, especially on a rectangular grid, but unfortunately not always a totally accurate predictor. I found this out when I tried to prove it and failed. The problem lies in the fact that a button press could split a region of buttons in two which both fail the parity condition. It is usually possible to reorder the moves to avoid that problem, but not always. There are some rare bad cases such as the one shown on the right. There are 15 buttons in the regular solution of which one is lit, and 16 adjacent pairs, so the parity condition does hold. Nevertheless it needs more than 15 moves to solve as a lit-only game, as pressing the only lit button in the solution leads to a position that fails the conditions.

The Toggle game.

This is yet another variation that is found in the Lights Out Deluxe. Here you must alternately press lit and unlit buttons to solve it. This is quite a bit more difficult to solve than the lit-only game.

The first thing to realise with the Toggle game is that the last move must always be pressing a lit button to switch it off. Therefore, if the regular solution has an even number of moves, the first move in the Toggle game is pressing an unlit button, and if the solution has an odd number of moves it starts by pressing a lit button.

Theorem 5:
Suppose a solvable position in a symmetric reflexive game requires an even number of button presses, and that the position is solvable in the Toggle game. Consider for a moment only those buttons that are part of the regular solution. These satisfy the following parity conditions:
1. The number of currently lit buttons is even.
2. The number of the currently unlit buttons is even also.
Note this is about the state of all the buttons at one moment, not the state of the individual buttons at the moment you press them during the solving of the position.
3. Half the total number of solution buttons plus the number of neighbouring pairs amongst them, is also even.

On the right you see an example of a position solvable in the toggle game. There are six buttons in the solution, two lit and four unlit. There are three adjacent pairs of buttons, half the number of buttons is also three, and together this makes six. All three numbers are even.

Proof of Theorem 5: Click to hide proof.
The solved position clearly satisfies the parity conditions since zero is even.
Let's start with any position that satisfies the parity conditions, and then press an unlit button that is not already one of the solution buttons. As it is unlit, it must have an even number of neighbours (possibly none) that are part of the regular solution. The change in state of these neighbours will therefore not affect conditions 1 and 2, nor the parity of the number of neighbouring pairs. The button itself does however change things, namely it either adds one (now lit) button to the solution.
Now we press a lit button that is not yet one of the solution buttons. As it is lit, it must have an odd number of neighbours that are part of the regular solution already. The change in state of these neighbours will therefore change the parity of the number of lit buttons as well as the number of unlit solution buttons, and also the parity of the number of neighbouring pairs. The button itself also changes, namely adds one (now unlit) button to the solution.
Combining all these changes together, we see that the number of lit buttons was incremented by the first press, and then the neighbours of the second button press changed the parity again, so condition 1 still holds. Similarly for condition 2. The total number of solution buttons was increased by two, and an odd number of new neighbouring pairs was formed, so condition 3 also still holds.
It is easy to check the conditions still hold if one or both the buttons are already part of the regular solution.
Q.E.D.

The reverse of the theorem is also true, at least for games that don't have too few buttons. I will describe a solving strategy below. It is useful however to first find some move sequences which have no effect but which involve more lit buttons than unlit buttons or vice versa.

Suppose you have two adjacent buttons, a and b, where a is lit and b is unlit. The sequence baba presses four unlit buttons but does not have any effect on the lights. If you have three adjacent buttons a,b,c (c is not adjacent to a) all unlit then the sequence acbacb also involves four more unlit presses than lit ones. The sequence bcabca works if all three buttons are lit. Sequences such as these allow you some leeway with the alternating lit/unlit presses, because you can generate a surplus of one or the other.

Note however that all of these have a surplus of four. It is in fact impossible to have a sequence that generates a surplus of two in a symmetric reflexive game.

Theorem 6:
In a reflexive symmetric game, any move sequence in which every button involved is pressed an even number of times, the number of lit button presses and the number of unlit button presses both have the same parity as half the total number of button presses.

Proof of Theorem 6: Click to hide proof.
This is clearly true for a sequence where each button is pressed an even number of in succession without being interrupted by other moves. Suppose it is true for some move sequence, then it is also true if a pair of successive moves in that sequence are interchanged. This is obvious if the swap involves buttons that do not influence each other, but equally true when they do. The only change is that the two moves change from lit to unlit or vice versa. The result then follows since any move sequence can be rearranged by such swaps to that sequence where each button is pressed an even number of times in succession.
Q.E.D.

This theorem shows that a surplus of 2 is not possible because then the number of lit and unlit buttons would be say k+1 and k-1, the number of button presses is 2k, and then the theorem requires k+1 and k-1 to have the same parity as k. This is clearly not the case.

The solving strategy is now as follows. Find out the buttons in the regular solution to the position, and then solve the toggle game as far as possible, pressing only the buttons in that regular solution. Eventually there is no direct move left, either because it is solved or because there are no buttons in the regular solution that have the correct state. Thus you must have an odd number of buttons in regular solution, all unlit, or an even number, all lit. The first case is impossible since each button must have an odd number of neighbours in the solution for it to be unlit, and this contradicts lemma 1.

So you must reach a position with only lit buttons in the regular solution, and the next move is pressing an unlit button. If any two buttons in the regular solution are adjacent, then you can change them if you first press any unlit button not adjacent to them (*) so that you can now do the right kind of moves to press the adjacent buttons. Then continue on as normal.

You may end up with an even number of lit buttons to press which are all separated. From theorem 5, half the number of buttons is even so the number of buttons must be a multiple of four. Now the move sequences that generate surplus moves come in handy. If a,b,c are adjacent unlit buttons, then the sequence axcxbxaxcb will do the trick where each x is a press of a lit solution button. If you cannot find three adjacent unlit buttons, then you can usually (**) make room by 'moving' a solution button (i.e. switch one new button on, switch a solution button off).

The above strategy is not a rigorous proof of the converse of theorem 5. In other words it does not prove that all positions that satisfy the parity restrictions in the theorem are solvable in the Toggle game. This is because there are assumptions made at * and ** that certain buttons can be found. In small games this is not necessarily the case, but I do think the converse of theorem 5 holds for all games as long as there remain some unlit buttons.

A special case.

Let's consider the matrix of the Mini Lights Out:

1101100000001000 1110010000000100 0111001000000010 1011000100000001 1000110110000000 0100111001000000 0010011100100000 0001101100010000 0000100011011000 0000010011100100 0000001001110010 0000000110110001 1000000010001101 0100000001001110 0010000000100111 0001000000011011

This matrix A is a little bit special because A²=I. This means that A=A^-1, i.e. that the matrix is its own inverse. When this happens you can change any single light by pressing those lights that would be changed if you pressed it, in other words press the light itself and its four neighbours.

The Orbix (game type 1) has the same property, that A²=I. To change a single light press those lights that would be changed if you pressed it, in other words just press its five neighbours.

Both puzzles have a relatively small number of lights, and a lot of symmetry. There are 60 ways to rotate the Orbix. It clearly should not matter which way the puzzle is held, so this means that the 12 buttons should give the same kind of light pattern, and that the light pattern should have 5-fold symmetry. This 5-fold symmetry around a light/button gives rise to 4 orbits - the light itself, the ring of 5 adjacent lights, the opposite light, and the ring of the remaining 5 lights. Let a, b, c, and d represent whether those orbits change state when a button is pressed. So a=1 if each button press changes its own light, and a=0 otherwise. Also b=1 if each button press changes the 5 adjacent lights, b=0 otherwise. Similarly c for the other ring of 5 lights, and d for the opposing light. In this way a, b, c, and d can encode all possible light patterns that can be chosen as the Orbix move shape under the condition that it respects the symmetry of the puzzle. We can now construct the matrix for this game.

a  b b b b b  c c c c c  d  b  a b c c b  d c b b c  c b  b a b c c  c d c b b  c b  c b a b c  b c d c b  c b  c c b a b  b b c d c  c b  b c c b a  c b b c d  c  c  d c b b c  a b c c b  b c  c d c b b  b a b c c  b c  b c d c b  c b a b c  b c  b b c d c  c c b a b  b c  c b b c d  b c c b a  b  d  c c c c c  b b b b b  a

If you evaluate the square of the matrix every term in a non-diagonal entry occurs an even number of times, so modulo 2 there will automatically be only zeroes in all non-diagonal entries. Thus the symmetry of the Orbix forces A²=I or A²=O. In fact, the entries on the diagonal will be a+b+c+d, so we have A²=I if and only if the light pattern of a move changes an odd number of the four light orbits.

The Mini Lights Out also has a lot of symmetry. You can move the top row to the bottom or vice versa, or the left column to the right hand side and vice versa, and you can rotate the board a quarter turn. This gives 16·4=64 symmetries. As with the Orbix, if you insist that the lights affected by a button also follow these symmetries, then they force A²=I or A²=O, and again we have A²=I if and only if the light pattern of a move changes an odd number of lights.

Determinants.

Let's now examine when a normal lights out game has quiet patterns or not, i.e. when the matrix of the game is invertible or not. There is a way to determine whether a square matrix is invertible without actually trying to invert it, and that is by determining a number called the determinant of the matrix. If this number is 0 then it is not invertible.

One way of calculating the determinant of an n×n matrix {a_ij} is as follows. Let p be a permutation of the numbers 1 to n (i.e. p is an element of the symmetric group S_n). Calculate the product sgn(p)·a_{1 p(1)}·a_{2 p(2)}·a_{3 p(3)}·...·a_{n p(n)}, where the sgn(p) is +1 if p is an even permutation, or -1 if p is an odd permutation. Do this for all n! possible permutations, and add these numbers together. The result is the determinant. This is generally a rather labour intensive way to calculate the determinant but as we shall see later, it is useful in this setting.

Before going on, I shall prove a few useful properties of the determinant.

Property 1: If two rows of a matrix are swapped, the determinant changes sign, but not its magnitude.

Proof: Click to hide proof.
Let x and y be the numbers of the rows that we will swap, and let p be a permutation. Define a permutation q as q(x)=p(y), q(y)=p(x), and q(i)=p(i) when i is not equal to x or y. Then q is clearly also a permutation, as it is simply the transposition (x y) composed with p, and furthermore q will be of opposite parity to p. As p ranges over all possible permutations, so does q, and vice versa. Consider one of the terms in the determinant calculation:
sgn(p)·a_{1 p(1)}·a_{2 p(2)}·...·a_{x p(x)}·...·a_{y p(y)}·...·a_{n p(n)}
The row swap turns it into:
sgn(p)·a_{1 p(1)}·a_{2 p(2)}·...·a_{y p(x)}·...·a_{x p(y)}·...·a_{n p(n)}
This is equal to:
-sgn(q)·a_{1 q(1)}·a_{2 q(2)}·...·a_{y q(y)}·...·a_{x q(x)}·...·a_{n q(n)}
Each term in the determinant after the swap has become the negation of some term before the swap. The determinant is therefore the same apart from the changed sign.

Property 2: If a matrix has two equal rows, then the determinant is zero.

Proof: Click to hide proof.
Swap the two equal rows. According to property 1, the determinant changes sign. The matrix is unchanged by the swap, so the determinant cannot have changed either. Therefore the determinant is 0.

Property 3: If we multiply a whole row of a matrix by some number r, then the determinant is also multiplied by r.

Proof: Click to hide proof.
Each term in the determinant calculation will have exactly one factor from that row, so each term is multiplied by r. The determinant is then also multiplied by r.

Property 4: If a row of a matrix has only zeroes, then the determinant is zero.

Proof: Click to hide proof.
Each term in the determinant calculation will have one factor from the zero row, so each term is 0. The determinant is then also 0. Alternatively, multiply the zero row by r. According to property 3, the determinant is also multiplied by r, but as the matrix has not been changed, the determinant is not changed by multiplication by any r. Therefore the determinant is 0.

Property 5: If a multiple of one row of the matrix is added to another, the determinant remains the same.

Proof: Click to hide proof.
Lets suppose that we add r times row 2 to row 1. Consider one of the terms in the determinant calculation:
sgn(p)·a_{1 p(1)}·a_{2 p(2)}·...·a_{n p(n)},
After the row addition this term becomes:
sgn(p)·(a_{1 p(1)}+r·a_{2 p(1)})·a_{2 p(2)}·...·a_{n p(n)},
This is equal to:
sgn(p)·a_{1 p(1)}·a_{2 p(2)}·...·a_{n p(n)} + r·sgn(p)·a_{2 p(1)}·a_{2 p(2)}·...·a_{n p(n)},
The first term summed over p is just the original determinant. The other term summed over p can be seen as (r times) the determinant of a matrix with the first and second row equal. This is zero by property 2, so the value of the determinant has not changed.

Armed with these properties we can see why a matrix that is invertible must have non zero determinant. If we use Gaussian elimination then (from properties 1, 3, 5) the determinant of a matrix will either remain zero throughout, or remain non-zero throughout. A non-invertible matrix results in a zero row, so (by property 4) its determinant is zero. An invertible matrix on the other hand results in the identity matrix, which has determinant 1 (i.e. non-zero). This proves the following:

Corollary: The determinant of a matrix is non-zero if, and only if, the matrix has an inverse.

Domino/monomino tilings.

The information in this section and the next is based on a thread on the Grey Labyrinth Forum in December 2003, in particular the posts by 'Bicho the Inhaler'.

Let's now find the determinants of the matrices we generally get from a standard Lights Out game. We want to determine the terms in the determinant, and somehow relate them to the actual game board, so that we can find out if the game on that board is completely solvable. Lets therefore take an extremely simple game board with only five buttons/lights, in the shape of the P-pentomino:

The five squares have been labelled with the numbers 1 to 5. If we use the usual type of move, i.e. each button changes its own light as well as its neighbours, then the associated matrix is:

1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1

Lets consider some permutations p, and see what their corresponding terms are in the determinant calculation.

Permutation p	(123)	(1254)	(1452)	(23)(45)
Matrix entries i,p(i) marked	1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1	1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1	1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1	1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1
determinant term	1·1·0·1·1 = 0	1·1·1·1·1 = 1	1·1·1·1·1 = 1	1·1·1·1·1 = 1

The first permutation is (123). As you can see a_{3 p(3)} = a₃₁ = 0, because squares 3 and 1 are not adjacent. The resulting term of the determinant is therefore also 0. This shows that the only permutations that we need to worry about are those which move each square either to itself or to an adjacent square.

The second permutation does move each square to an adjacent one or to itself. The corresponding entries in the matrix are indeed all non-zero. The third permutation is the inverse of the second, and it is easy to see that the pattern of matrix entries is now the mirror image of the previous one. Since we are analysing a symmetric game, the terms coming from a permutation and from its inverse will be exactly the same. Working modulo 2, these two terms cancel each other out.

The only permutations that remain are ones which are the same as their inverse. These have order 2, so consist only of disjoint 2-cycles. One example is the fourth permutation above. It swaps the adjacent squares 2 and 3 as well as 4 and 5, and does not move 1. The pattern of the corresponding entries in the matrix is indeed symmetric as expected.

We can visualise such a permutation by putting a coloured domino on the adjacent squares which are swapped by the permutation. Any squares that are not affected by the permutation are also given some colour. This gives this pattern:

This is a tiling of the game board by dominoes and monominoes (i.e. 2x1 rectangles and 1x1 squares). Every such tiling corresponds to a permutation that contributes a non-zero term to the determinant. Our aim throughout all of this is to determine whether the determinant is 0, but as we are working modulo 2, we really only need to see whether the number of the non-zero terms is even or odd. Therefore, we just need to find out how many ways there are to tile the game board with dominoes and monominoes. If that number is odd then the matrix is invertible, and if it is even then it is not invertible. This proves the following:

Theorem 7: If standard Lights Out is played on a grid-like board, then all light patterns on that board are solvable if, and only if, the number of ways to tile the board with dominoes and monominoes is odd.

Tilings of rectangular boards.

Lets now put this into practice on some rectangular boards. To make things easier, let R(m,n) be the number of monomino/domino tilings of an m×n rectangle.

Example 1: 1×n: When tiling this board, we can start with a monomino on the left and then tile the remaining 1×(n-1) rectangle in any one of R(1,n-1) ways. If we start with a domino on he other hand, then the remainder is a 1×(n-2) rectangle that can be filled in R(1,n-2) ways. Therefore, R(1,n)=R(1,n-1)+R(1,n-2). It is trivial to check that R(1,1)=1 and R(1,2)=2, we find that R(1,n) are the Fibonacci numbers, 1, 2, 3, 5, 8, 13, 21, ...
It is easily checked that this is even exactly when n=2 modulo 3. In other words, rectangles of size 1×(3k+2) have quiet patterns, whereas other 1×n rectangles have none. The quiet pattern looks like this:

X	X		X	X		X	X		X	X		X	X

Example 2: 2×n: Suppose we have a domino/monomino tiling of this board. If it is asymmetric along its long axis, then we can skip it because it will be cancelled out by its mirror image. After all, we only need to know whether the total number of tilings is even or odd. Therefore we only need to look at tilings that are symmetric about the long axis. In the tilings that remain, every monomino in the top row has a matching monomino in the bottom row.
We can now do a similar trick, not by pairing a tiling with its mirror image, but another kind of pairing. Given a pattern, exchange every vertical domino by two monominoes, and vice versa. Two tilings related to each other by such an exchange can be skipped. This leaves only tilings which have no monominoes and no vertical dominoes, i.e. only tilings with horizontal dominoes.
If n is even, then there is exactly one such tiling left. Therefore, R(2,2k) is odd, and in any 2×2k rectangle all light patterns are solvable.
If n is odd, then there are no tilings with only horizontal dominos, so then R(2,2k+1) is even, and there must be quiet patterns, such as the one shown below.

X		X		X		X		X		X
X		X		X		X		X		X

Example 3: 5×n: Consider a horizontal line through the middle of the board. Like before, any tiling that is not symmetric about this line can - together with its mirror image - be ignored, since we only need the parity of the number of tilings. We only need symmetric tilings. As the line of symmetry goes through a row of squares, there can be no vertical dominoes on this row (that would be asymmetric). The row is then only monominoes and horizontal dominoes, and therefore the symmetric tilings can be split into a tiling of the top 2×n board, a tiling of the 1×n middle row, and a tiling of the bottom 2×n board that is a mirror image of the top part. The number of these tilings is therefore R(5,n)=R(2,n)·R(1,n). For this to be odd both factors must be odd, so from the previous examples we see that n must be even and also not 2 modulo 3. The number of tilings is therefore odd exactly when n is 0 or 4 modulo 6. In other words all light patterns in 5×6k or 5×(6k+4) rectangles are solvable, but on other 5×n rectangles there are quiet patterns.

5 × (2k+1)	5 × (3k+2)
X X X X X X X X X X X X X X X X X X X X X X X X	X X X X X X X X X X X X X X X X X X X X X X X X

We can generalise the last example a bit to get:

Lemma: On an (2k+1)×n rectangle there are quiet patterns when n is 2 modulo 3. If n is not 2 modulo 3, then there are quiet patterns if and only if there are quiet patterns on the k×n rectangle.

Proof: Click to hide proof.
The same reasoning as in the previous example shows that R(2k+1,n) = R(k,n)·R(1,n). If n is 2 modulo 3 then R(1,n) is even and then so is R(2k+1,n). This gives the patterns below left. Otherwise, R(2k+1,n) is even exactly when R(k,n) is even. This case leads to the kind of pattern below right - a quiet pattern on a k×n rectangle is used in the top half and repeated in mirror image in the bottom half.

2k+1 × 3k+2	2k+1 × n, given a pattern on k×n
X X X X X X X X X X X X X X X X X X X X X X X X	X X X X X X X X X X X X X X X X

What remains now are the rectangles where all the sides have even length. These are not easily analysed in general, and sometimes give rise to more complicated quiet patterns. Lets do some simple cases.

Example 4: 4×4: Using the same trick as before, we can restrict ourselves to tilings that are symmetric. In fact we can do the trick twice, along the two diagonals of the square. For a tiling to be symmetric about the diagonals, there can only be monominoes on those diagonals. This nearly fixes the whole tiling, except for the 2×1 area along the edges. These must all be the same due to symmetry, and they can be filled with one domino or two monominoes. There are then exactly two symmetric tilings, which means that R(4,4) is even. Therefore there are quiet patterns, such as the ones below.

X X X X X X X X

X X X X X X X X

X X X X X X X X

X X X X X X X X X X X X

Example 5: 4×n: Again only symmetric tilings need be considered, so the top two rows are the mirror image of the bottom two rows. Now use the same trick as used in the 2×n case - pair up tilings by exchanging any vertical dominoes that cross the line of symmetry by two monominoes and vice versa. These pairs can be ignored so we are left with patterns which have no vertical domino nor two vertically adjacent monominoes in the second and third rows. This splits the 4×n tiling into two mirror image 2×n tilings. What remains to be done is count the number of 2×n tilings that do not have a monomino in the bottom row.
Let S_n be the number of 2×n tilings without a monomino on the bottom row. The bottom left corner has a domino in it, either vertical or horizontal. If it is vertical, then there are S_n-1 ways of completing the remaining 2×(n-1) rectangle. If it horizontal with a horizontal domino above it then there are S_n-2 ways to complete the tiling. The final possibility is a horizontal domino with a monomino above it. Now the next monomino in the top row can be immediately adjacent to the first (giving S_n-2 completions) or there may be one horizontal domino first (giving S_n-4 completions) or two (S_n-6), three (S_n-8) etc. until there is no more room left. We therefore arrive at:
S_n = S_n-1+2S_n-2+S_n-4+S_n-6+...
To eliminate the tail of this sum, we calculate S_n-S_n-2:
S_n-S_n-2 = (S_n-1+2S_n-2+S_n-4+S_n-6+...) - (S_n-3+2S_n-4+S_n-6+S_n-8+...) = S_n-1+2S_n-2-S_n-3-S_n-4
so that (at least for n>3) S_n=S_n-1+3S_n-2-S_n-3-S_n-4
It is easy to check by hand that S₀ to S₃ are all odd. By repeatedly plugging this into the equation it becomes clear that S_n is even exactly when n is 4 modulo 5 (i.e. when n=4, 9, 14 etc.).
We already found quiet patterns for n=4, and by repeating them we can find quiet patterns for all those 4×(5k+4) rectangles. All other 4×n rectangles have no quiet patterns.

X	X	X				X	X	X		X	X	X
	X		X		X		X				X		X
		X	X		X	X						X	X
			X		X								X

The same techniques don't work well for wider rectangles as it gets messy very quickly. What can be said is that for every fixed m, as n increases the parity of R(m,n) will show a repeating pattern.

Characteristic polynomials.

The following two sections have quite a lot of theory behind them. It would take too much space to go into full detail, so I will skip some proofs and explanations. These sections work up to one of the most important theorems about Lights Out on rectangular boards.

Consider the n×n matrix xI-A , where x is a variable. Its determinant, calculated in the same way as before, is then some polynomial in x. Each row of the matrix has only one item with x in it, so each term in the determinant has degree of at most n, and only the diagonal term in fact does have degree n. The determinant det(xI-A) therefore is a polynomial of degree n. It is called the characteristic polynomial.

If k is a root of that polynomial, then we know that det(kI-A)=0. This matrix therefore is not invertible, and has its own 'quiet pattern', i.e. we can find a non-zero (column)vector v such that (kI-A)v=0 , or equivalently Av=kv . We call k an eigenvalue, and v a right eigenvector or column eigenvector. For the same eigenvalue k we can also find a row eigenvector or left eigenvector w , such that w(A-kI)=0 or wA=kw .

Note that since Av=kv , we get A² v = A(Av) = Akv = k(Av) = k(kv) = k² v , and similarly for higher powers Aⁱ v=kⁱ v . By adding such terms we find that p(A)v=p(k)v for any polynomial p, given that v is an eigenvector and k its eigenvalue.

There are n roots to the characteristic polynomial, though some may be repeated. For each root, i.e. for each eigenvalue we have an eigenvector. If the eigenvalue is a repeated root of the polynomial, then there will be just as many independent eigenvectors associated with it as the number of times that root is repeated. This means that there are in fact exactly n independent column eigenvectors v _i , and similarly exactly n independent row eigenvectors w _i .

An interesting fact about the characteristic polynomial c(x) of matrix A is that A itself satisfies the polynomial, i.e. c(A) is the zero matrix. The reason for this is that c(A)v = c(k)v = 0v=0 for any (column) eigenvector v with eigenvalue k. Every column vector can be written as a linear combination of the eigenvectors (since there are n independent eigenvectors), and so c(A)v=0 for every vector v . This can only mean that c(A) is the zero matrix.

Fibonacci/Chebyshev polynomials.

Let's now look at a special type of matrix, namely the square matrix A_n which has a_ij=1 whenever i=j-1 or j+1, but has zeroes everywhere else. In other words it has ones only at entries adjacent to the diagonal. This type of matrix will be useful later on.

For example, A₅ is:

01000 10100 01010 00101 00010

The characteristic polynomial c_n(x) for matrix A_n is fairly easy to find as there are so many zeroes. The only non-zero terms in the determinant must have a permutation p such that p(1)=1 or 2, and if p(1)=2 then we must have p(2)=1. You can see this in this example for A₅ :

	xI-A5	p(1)=1	p(1)=2, p(2)=1
Matrix with p marked	x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x	x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x	x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x
Determinant terms		x c4(x)	-1·-1·c3(x)

This gives us the recursive rule
c_n(x) = char[A_n](x) = det(xI_n-A_n) = x det(xI_n-1-A_n-1) - -1·-1·det(xI_n-2-A_n-2) = x c_n-1(x) - c_n-2(x)

For the small cases we find that c₁(x)=x, c₂(x)=x²-1. By applying the rule we could even say that c₀(x)=1.

The polynomials in this sequence are similar to Fibonacci polynomials. The Fibonacci polynomials are defined by:
f₀(x)=0
f₁(x)=1
f_n(x)=x f_n-1(x) + f_n-2(x)

If we are working modulo 2, then addition and subtraction are the same thing (since -1=1 modulo 2) and we see that c_n(x) = f_n+1(x). One reason that these are named after Fibonacci is that f_n(1) is the Fibonacci sequence 0,1,1,2,3,5,8,13,... etc. If we are not working modulo 2, then we do have to subtract. Those polynomials are called (normalised) Chebyshev polynomials of the second kind. In the mathematical literature you will see both names used.

Before moving on, we also need another kind of matrix, namely B_n = A_n+I. These matrices B_n are the same as A_n except that they have ones along the diagonal. Its characteristic polynomial is now easy to deduce:

char[B_n](x) = det(xI-(A_n+I)) = det((x-1)I-A_n) = c_n(x-1)

We can now put these special matrices to use. Consider a standard Lights Out game on a rectangular board. Except for light chasing, in all the previous sections we never used the specific shape of the board to simplify matters. We just considered each light/button, and used a whole row or column in a large square matrix for each of them. Light patterns or button patterns on a board were then long vectors without any board shape context. This time we use rectangular matrices of the same shape and size as the board. Such a matrix can represent either a light pattern or a button pattern.

Let X be an m×n rectangular matrix, representing a pattern of button presses on the m×n board. We would like to have some expression for the effect of this pattern on the lights, and the special matrices A_m and B_n will be used for that.

Consider XB_n .
This is still a rectangular m×n matrix, and you will find that every non-zero entry in X affects the same entry in the result as well as those above and below it. It is as if XB_n is the result of the button presses if only vertical neighbours (and the button itself) were affected by each button press.

Similarly, now consider A_mX.
Again this is an m×n rectangular matrix, but now each non-zero entry in X affects only the entries to the left and right of it in the result. Thus A_mX is the result of the button presses is only the horizontal neighbours (and not the button itself) were affected by each button press.

Putting these two together we find that A_mX + XB_n is the pattern of light changes caused by the button pattern X. If C is a rectangular matrix representing the current light pattern, then we want to deduce X from the matrix equation A_mX + XB_n = C. This kind of matrix equation is known as Sylvester's equation.

Of course the question arises of how to solve X, but I will not discuss that here as the previous methods work well enough for rectangular boards, especially if light chasing is done to reduce the size of the matrices. A more interesting question that can be answered from this equation is, when does X have a unique solution?

Suppose AX+XB=C has two solutions for X, say X₁ and X₂ . Let Y be X₁-X₂ , i.e. the button pattern achieved by combining X₁ and X₂ . This should have no effect on the lights, and indeed:
AY+YB = A(X₁-X₂)+(X₁-X₂)B = AX₁+X₁B-(AX₂+X₂B) = C-C = O
If X₁ and X₂ are distinct, then Y is a non-trivial quiet pattern. Therefore if there are no quiet patterns other than the trivial pattern (no buttons pressed), then all solutions are unique. Conversely, if there is a quiet pattern, then any solution X₁ to light pattern C will when, combined with the quiet pattern Y, give another solution X₂ = X₁-Y.

Now the search for quiet patterns has been reduced to finding solutions for Y of matrix equation AY+YB = O. To answer the question of when it has non-trivial solutions, we again need a bit more general matrix theory.

Let k be an eigenvalue of matrix A, and lets suppose that -k is an eigenvalue of B. Then we can find a column eigenvector v of A with that eigenvalue k, and a row eigenvector w of B with the eigenvalue of -k. Note that v is an m×1 matrix, and w is a 1×n matrix, so if we let Y=vw then Y is a non-trivial m×n matrix. We now find that:

AY+YB = A(vw)+(vw)B = (Av)w+v(wB) = (kv)w+v(-kw) = kvw-kvw=O

This started with the assumption that -k is an eigenvalue of B for some k which is already an eigenvalue of A. This means that det(xI-B)=0 has root -k, or equivalently that k is a root of det(-xI-B)=0. So if char[A](x) and char[B](-x) have a root in common, then there is a non-trivial solution to AY+YB=O. Note that the sharing of a common root k means that the polynomials char[A](x) and char[B](-x) have a common factor (x-k).

One thing I glossed over is that in our usual setting the numbers we are working with are all modulo 2. While a polynomial of degree n has n roots in the complex numbers, with the numbers we have now there might not be any roots. If the two polynomials char[A](x) and char[B](-x) share the linear factor x or x-1 then obviously the construction of Y above works, using the eigenvalue of 0 or 1 respectively. However, the two polynomials might share some other irreducible polynomial factor, such as x²+x+1. In such a case they still share a root even though this root lies outside the numbers we are working with. Even then there will be a non-trivial Y that solves the matrix equation. The converse is also true, but I will not prove any of this here. If we put all this together it does lead us to the following theorem:

Theorem 8: A Lights Out game on an m×n grid has quiet patterns exactly when the polynomials c_m(x) and c_n(-x-1) have a common factor. In fact, the number of linearly independent quiet patterns is equal to the degree of the largest common factor.

Sketch of Proof: Click to hide proof.
Suppose c_m(x) and c_n(-x-1) have a common factor of degree d. In other words, char[A_m](x) and char[B_n](-x) have a common factor of degree d. This common factor has d roots, which are eigenvalues of matrix A_m, and their negations are eigenvalues of matrix B_n. Corresponding to these eigenvalues we have d linearly independent column eigenvectors for A, and d row eigenvectors for B. These d pairs of eigenvectors combine (details omitted) to make d independent non-trivial solutions for Y in the matrix equation A_mY + YB_n=O . These solutions correspond to independent quiet patterns on the m×n grid. Proof of converse omitted.

As stated above it applies to all rectangular Lights Out versions, regardless of the number of states that each light can have. A different (but ultimately equivalent) way to prove it for the standard two state game can be found in [GTK1]+[GTK2], and a proof for the general case is in [HMP].

Here are the first few of these polynomials, factorised. I have not reduced them modulo 2, but if you were to do so they would often factorise further.

n	char[A](x)=cn(x)			char[B](-x)=cn(-1-x)
0	1			1
1	x			-x+1
2	x2-1	=	(x+1)(x-1)	x2+2x	=	x(x+2)
3	x3-2x	=	x(x2-2)	-x3-3x2-x+1	=	-(x+1)(x2+2x-1)
4	x4-3x2+1	=	(x2-x-1)(x2+x-1)	x4+4x3+3x2-2x-1	=	(x2+x-1)(x2+3x+1)
5	x5-4x3+3x	=	x(x-1)2(x2+2x+3)	-x5-5x4-6x3+2x2+4x	=	-x(x+1)(x+2)(x2+2x-2)
6	x6-5x4+6x2-1	=	(x3-x2-2x+1)(x3+x2-2x-1)	x6+6x5+10x4-9x2-2x+1	=	(x3+4x2+3x-1)(x3+2x2-x-1)
7	x7-6x5+10x3-4x	=	x(x2-2)(x4-4x2+2)	-x7-7x6-15x5-5x4+15x3+9x2-3x-1	=	-(x+1)(x2+2x-1)(x4+4x3+2x2-4x-1)

The m=n=5 case has a common factor of x. This means that we can construct a quiet pattern simply by multiplying the row and column eigenvectors with eigenvalue 0 as explained before.

          1                     1 -1  0  1 -1  0                     0  0  0  0  0 -1 . 1 -1  0  1 -1 =  -1  1  0 -1  1  0                     0  0  0  0  0  1                     1 -1  0  1 -1

If we instead use the common factor of x-1 and multiply the eigenvectors with eigenvalue 1, then we get the same pattern but rotated. Note that we did not reduce modulo 2, so this same pattern works with any number of light states, such as the Lights Out 2000 with 3 states.

The m=n=4 case also has a common factor, namely x²+x-1. There must therefore be a quiet pattern, again applicable regardless of the number of states of the lights. The shared factor is of degree 2 so we cannot simply multiply out the eigenvectors, but the quiet pattern is easily found by a little trial and error.

          1  0                  0  1 -1  0  0  1 .  0  1 -1  0 = -1  0  0  1  0 -1   -1  0  0  1    1  0  0 -1 -1  0                  0 -1  1  0

I have also shown a decomposition of that matrix into a product of two rectangular matrices. The polynomial factor had degree 2, so the rectangular matrices the pattern decomposes into have width resp. height 2. It is difficult to explain clearly why this is so. The eigenvalues used here involve square roots (since they are roots of a quadratic), and so the eigenvectors would also involve square roots. By taking linear combinations of those vectors we can get two other vectors that span the same space but without the square roots. Those two vectors are used in the columns or rows of the matrices.

In [HMP] the above 5×5 and 4×4 patterns are given. It is proved there that these are the only square grids that always have a general solution, in other words, char[A_n](x) and char[B_n](-x) only have a common factor when n=4 or 5. It is also shown in that paper that for any size square Lights Out board (greater than 1×1) there is a prime number p such that the game with p states for each light has a quiet pattern. In other words, for any n>1 there is a prime p such that char[A_n](x) and char[B_n](-x) have a common factor modulo p. For example in the 6×6 case we find that both polynomials above evaluate to 0 mod 13 for x=5, so modulo 13 they have the linear factor x-5 in common. Therefore the 6×6 board has quiet patterns modulo 13. The particular quiet pattern derived from the eigenvectors is:

          1                         1 -6 -4  4  6  1  5                         5 -4  6 -6  4 -5 -2 . 1 -6 -4  4  6  1  =  -2 -1 -5  5  1  2 -2                        -2 -1 -5  5  1  2  5                         5 -4  6 -6  4 -5  1                         1 -6 -4  4  6  1

It is easily checked that every cross in this pattern adds to 0 modulo 13.

Results for the standard game.

I have calculated the rank of the matrix A for the standard game on a rectangular grid m×n with 1<m,n<26. The table below shows m·n-rank, which is the number of generators of the quiet patterns. For example at 11×5 it shows 4, meaning that the rank is 55-4=51, and that there are 2⁴=16 quiet patterns (of which one is the trivial pattern).

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
1	0
2	1	0
3	0	2	0
4	0	0	0	4
5	1	1	3	0	2
6	0	0	0	0	0	0
7	0	2	0	0	4	0	0
8	1	0	2	0	1	6	2	0
9	0	1	0	4	1	0	0	1	8
10	0	0	0	0	0	0	0	0	0	0
11	1	2	3	0	4	0	7	2	1	0	6
12	0	0	0	0	0	0	0	0	0	0	0	0
13	0	1	0	0	1	0	0	7	0	0	1	0	0
14	1	0	2	4	1	0	2	0	5	0	2	0	1	4
15	0	2	0	0	4	0	0	2	0	0	8	0	0	2	0
16	0	0	0	0	0	0	0	0	0	0	0	0	0	8	0	8
17	1	1	3	0	2	6	4	1	1	0	4	0	13	1	4	0	2
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
19	0	2	0	4	3	0	0	2	8	0	3	0	0	6	0	0	3	0	16
20	1	0	2	0	1	0	2	6	1	0	2	0	1	0	2	0	7	0	2	0
21	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
23	1	2	3	0	5	0	7	2	1	0	10	0	1	2	15	0	5	0	3	2	1	0	14
24	0	0	0	4	0	0	0	0	4	0	0	0	0	4	0	0	0	0	4	0	0	0	0	4
25	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0

It is obvious that due to light chasing an m×n game cannot have more than m (or n) generators of the quiet patterns.

As remarked on before, it is quite easy to generate quiet patterns for larger rectangles by sticking together several copies of a quiet pattern on a smaller rectangle. For example the 4×4 pattern below left will generate quiet patterns for any m×n rectangle with m,n = 4 (modulo 5) as shown below right. Similarly, any 5×5 pattern generates others for rectangles with m,n = 5 (modulo 6). This proves that at least one third (10/30) of the square Lights Out games are not completely solvable.

X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

This way of repeating a quiet pattern (with a strip between them one cell wide) to get a quiet pattern for a larger rectangle works very generally. In the above example the pattern was symmetric. It works just as well for asymmetric patterns provided any two adjacent repeats are mirror images of each other. This ensures that the strip between them is affected equally by the buttons from either side and hence shows no lights as required. From any (m-1)×(n-1) quiet pattern we can get patterns of size (im-1)×(jn-1) for any positive i and j.

The smallest quiet pattern is the 1×2 rectangle, both buttons pressed. Repeating this we find quiet patterns for all grids of size (2i-1)×(3j-1). At least one sixth of all grid sizes therefore have quiet patterns. These are marked red (or orange) in the table above. In fact, doing the same thing with the 2×1 rectangle (patterns marked yellow or orange) nearly doubles this amount to 11/36, not quite a third. The patterns resulting from the 4×4 shape have been marked blue (or green or purple). This accounts for all cases in this range, except for 8×6 (and 17×6, 8×20), 14×16, and 16×16. Here are some of the quiet patterns for these boards:

X X X X X X X X X X X X X X X X X X X X X X

X X X X X X X X X X X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

I have now recalculated the table above (using the polynomial method) up to 1200 by 1200. A 100 by 100 part of it is shown in the picture below. Each black square represents zero quiet patterns, i.e. a completely solvable Lights Out game. The shade of the coloured pixels range from red to blue depending on how many quiet patterns there are relative to the shortest side of the rectangle.

In [GKW] it is proven that the square Lights Out board with edge length 2ⁿ has a quiet pattern, as well as the square of size 2ⁿ-2. You can see in the picture that these sizes do indeed have more than the average number of patterns. The paper also proves that the only n×n board with 2ⁿ quiet patterns is the 4×4 board (i.e. all the 2⁴ possible button patterns on the top row of the 4×4 board can be chased down to create a quiet pattern). The fraction of n×n boards (n<10000) with quiet patterns is 0.423, see again [GKW].

It may seem that some rows/columns of the table consist only of zeroes. In the picture this shows as a completely black line, for example at n=18 or n=22. This is not the case, any such line is eventually broken by the existence of an m×n quiet pattern for some number m.

Theorem 9:
For any positive number n, there is a positive number m such that the m×n Lights Out board has a quiet pattern.

Sketch of Proof: Click to hide proof.

Suppose you have a board that is n squares wide but indefinitely long with nothing lit, and you press some buttons in the top row. You can then chase the lights down. The button pattern you press on some row matches what the lights were on the row above, which in turn is determined only by the button patterns on that row and the previous row. As there are finitely many button patterns for two rows (2²ⁿ in fact), you will repeat yourself eventually, after no more than 2²ⁿ steps.
By working back upwards you can show that the repetitive pattern begins at the top, i.e. it is rows 1 to k that are repeated on rows k+1 to 2k etc. If you imagine a row zero above the top of the board, in which you pressed no buttons, this is the same as row k because of the repeated pattern. Row k-1 therefore needed no button presses on row k to switch it off, and hence rows 1 to k-1 on their own form a quiet pattern for an n×(k-1) board. This proof can be found in more detail in [GTK1].

1200×1200 table image

Click on the link above to see the huge 1200 by 1200 version. From that picture it becomes very clear that something interesting happens around coordinates that are one less than powers of 2. There seem to be diagonal crosses centred at such coordinates. In August 2012 David Beckman sent me a proof for the existence of (some of) these crosses, using properties of Fibonacci polynomials modulo 2.

Theorem 10 (David Beckman):
Let c = 2ⁿ-1, and d = 2^m for some 0<=m<n. Then the four Lights Out boards of size c±d by c±d have on average (c-1)/2 independent quiet patterns.

This means that in the image the four points at (c±d, c±d) are more red than blue (on average), explaining the cross shapes we see on the main diagonal.

Sketch of Proof: Click to hide proof.

Let Q_a,b denote the dimension of the null-space for the matrix of the standard Lights Out game on an a×b grid. In other words, the a×b game has 2^Q_a,b quiet patterns. From Theorem 8, we know that Q_a,b is equal to the degree of the largest common factor of c_m(x) and c_n(-x-1), i.e.
Q_a,b = deg gcd( c_a(x), c_b(-x-1) )
It is easy to prove that for any r, s, t, gcd(r,s)·gcd(r,t) >= gcd(r,st). Using this we find:

Q_c+d,c+d + Q_c+d,c-d + Q_c-d,c+d + Q_c-d,c-d
= deg gcd( c_c+d(x), c_c+d(-x-1) ) + deg gcd( c_c+d(x), c_c-d(-x-1) ) + deg gcd( c_c-d(x), c_c+d(-x-1) ) + deg gcd( c_c-d(x), c_c-d(-x-1) )
= deg ( gcd( c_c+d(x), c_c+d(-x-1) ) · gcd( c_c+d(x), c_c-d(-x-1) ) · gcd( c_c-d(x), c_c+d(-x-1) ) · gcd( c_c-d(x), c_c-d(-x-1) ) )
>= deg ( gcd( c_c+d(x), c_c+d(-x-1) c_c-d(-x-1) ) · gcd( c_c-d(x), c_c+d(-x-1) c_c-d(-x-1) ) )
>= deg ( gcd( c_c+d(x) c_c-d(x), c_c+d(-x-1) c_c-d(-x-1) ) )

It turns out that modulo 2 the product c_c+d(x) c_c-d(x) has a particularly nice form when c = 2ⁿ-1, and d = 2^m for some 0<=m<n, namely c_c+d(x) c_c-d(x) = x^2c + x^2d-2, which can be proved by induction (proof omitted).

It can then be shown (details omitted) that, modulo 2, the common factors of c_c+d(x) c_c-d(x) and c_c+d(x+1) c_c-d(x+1) are:
x^2d-2,
(x+1)^2d-2, and
1 + x^2d + x^4d + x^6d + ... + x^2c+2-4d
The total degree is then 2d-2 + 2d-2 + 2c+2-4d = 2c-2.

Putting this together, we get
Q_c+d,c+d + Q_c+d,c-d + Q_c-d,c+d + Q_c-d,c-d >= 2c-2
The average value of Q_c±d,c±d is at least (2c-2)/4 = (c-1)/2.

The inequality gcd(r,s)·gcd(r,t) >= gcd(r,st) is an equality if all the factors in it are at least as abundant in r than in st. This inequality was used three times in the above, and in all three cases it can be verified that equality holds, so that the average value of Q_c±d,c±d is exactly equal to (c-1)/2.

This theorem shows why the diagonal crosses appear on the main diagonal in the image above. I have no doubt that a slight variation of this will also explain the other diagonal crosses in the picture.

Results for the standard game on a torus.

This is a similar table for the Lights Out game on a torus, i.e. a rectangular grid where the left and right columns are considered to be neighbours, as well as the top and bottom rows.

	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
3	4
4	4	0
5	2	0	8
6	6	8	2	8
7	2	0	0	2	0
8	4	0	0	8	0	0
9	4	4	2	6	14	4	4
10	4	0	8	4	0	0	4	16
11	2	0	0	2	0	0	2	0	0
12	6	8	2	12	2	16	6	4	2	16
13	2	0	0	2	0	0	2	0	0	2	0
14	4	0	0	4	0	0	16	0	0	4	0	0
15	4	4	10	6	2	4	4	12	2	6	2	4	12
16	4	0	0	8	0	0	4	0	0	16	0	0	4	0
17	2	0	0	2	0	0	2	0	0	2	0	0	18	0	16
18	6	8	2	8	14	8	6	4	2	12	2	28	6	8	2	8
19	2	0	0	2	0	0	2	0	0	2	0	0	2	0	0	2	0
20	4	0	8	8	0	0	4	16	0	8	0	0	12	0	0	8	0	32
21	4	4	2	6	2	4	16	4	2	6	2	4	4	4	2	18	2	4	4
22	4	0	0	4	0	0	4	0	0	4	0	0	4	0	0	4	0	0	4	0
23	2	0	0	2	0	0	2	0	0	2	0	0	2	0	0	2	0	0	2	0	0
24	6	8	2	12	2	16	6	4	2	24	2	4	6	32	2	12	2	8	6	4	2	32
25	2	0	8	2	0	0	2	8	0	2	0	0	10	0	0	2	0	8	2	0	0	2	8

Note that I have not included the 2×m case as it is somewhat degenerate - the two rows are neighbours of each other in two ways, and so do not affect each other.

A quiet pattern on an a×b rectangle can be repeated in both directions to form a quiet pattern on any rectangle where the sides are multiples of a and b. The smallest quiet pattern is a 1×3 rectangle of which two buttons are pressed. By repeating it, the game on a m×n torus with m or n divisible by 3 has a quiet pattern whereby everything except every third row/column is pressed. These cases have been coloured yellow (or orange) in the table above.

There are also 5×5 and 17×17 quiet patterns, shown below. The cases derived from the former are coloured red (or orange) in the table above, the latter is coloured blue in the table. The patterns shown here are symmetric quiet patterns on the 4×4 and 16×16 standard game, but with an extra blank row and column added.

X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

The theorem below was proved algebraically in [ST], but here I give an easier to understand proof.

Torus Lemma:
A 2m×n torus has no quiet patterns if and only if the m×n torus has none.

Proof: Click to hide proof.
One direction is easy: If an m×n torus has a quiet pattern, then simply placing two copies side by side gives a quiet pattern for the 2m×n torus.
The other direction is a little less obvious. Suppose you have a quiet pattern for the 2m×n torus. If it happened to consist of two identical halves, then such a half is also a quiet pattern on the half-sized m×n torus.
Suppose then that our 2m×n pattern does not consist of two identical halves. On a torus you can cyclically shift any quiet pattern, and it will remain a quiet pattern. In particular, you can shift it half the length of the board, essentially swapping the two halves of the rectangle. Adding two quiet patterns together also gives a quiet pattern, so we can add the original pattern to the one with its halves swapped, and so create a quiet pattern consisting of two identical halves. This therefore again gives us a quiet pattern on the smaller board, proving the lemma.

Torus Theorem 1:
A torus of size 2^am×2^bn has no quiet patterns if and only if the m×n torus has none. [ST]

Proof: Click to hide proof.
This follows from applying the torus lemma repeatedly (i.e. induction) and the fact that the x×y and y×x boards are equivalent.

Note that this does not depend on the shape of the move. It works with any move shape, as long as it is the same shape for every button on the board. So if you want to find out whether or not a torus board has quiet patterns for any type of move, you can cast out any factors of two in the dimensions to only look at an odd×odd board. For the normal move type, we have already seen quiet patterns that are (multiples of) 1×3, 5×5, and 17×17, but if you were to extend the table further up to 300, you would also find patterns that are (multiples of) 11×31, 31×31, 119×119, 43×127, 127×127, 155×187, 119×221, 85×257, and 257×257.

In [ST], another interesting condition about the dimensions of torus boards with quiet patterns is proved, and I will repeat it here without proof. It uses the concept of the multiplicative order of 2 modulo n, which is defined as the smallest positive exponent e for which 2^e = 1 modulo n.

Torus Theorem 2 ([ST]):
If there are quiet patterns on a torus Lights Out board of size m×n, with m,n odd, then the multiplicative order of 2 mod m and the multiplicative order of 2 mod n must either be equal, or else one is twice the other.

This result does depend on the fact that the move shape fits within a 3×3 area, but not on the exact shape, so it will apply to for example diagonal crosses as well. The reverse of this result is not true, so the condition on the multiplicative orders is necessary, but not sufficient for there to be a quiet pattern. The rectangular patterns I have found so far are easily verified to satisfy the theorem as shown in the following table.

m×n	Ordmod m(2)	Ordmod n(2)
1×3	1	2
11×31	10	5
43×127	14	7
155×187	20	40
119×221	24	24
85×257	16	8

Results for the XL-25 knight's game.

This is a similar table for the XL-25 knight's game.

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	0
3	2	0
4	4	0	0
5	2	2	0	0
6	0	0	4	2	4
7	0	0	0	4	2	4
8	0	2	0	0	4	6	8
9	2	0	4	0	2	0	0	4
10	4	0	4	2	4	0	0	0	0
11	2	2	4	2	0	2	2	6	0	0
12	0	0	0	0	0	2	0	2	4	0	8
13	0	0	0	0	0	2	0	2	2	3	4	4
14	0	2	4	4	0	0	0	0	4	2	4	4	4
15	2	0	0	4	6	5	8	0	0	0	2	0	2	6
16	4	0	0	4	12	6	8	0	4	0	4	0	0	8	12
17	2	2	0	0	6	6	8	0	0	4	4	0	0	8	8	8
18	0	0	4	0	0	0	0	2	0	0	8	0	4	0	4	4	0
19	0	0	0	2	0	0	0	0	10	2	4	6	6	0	0	0	4	0
20	0	2	0	2	0	0	0	4	20	4	0	2	4	0	8	2	4	0	0
21	2	0	4	0	0	0	2	0	10	0	0	0	2	0	2	2	0	0	4	0
22	4	0	8	0	4	0	0	4	0	0	0	2	4	0	4	0	4	0	4	0	0
23	2	2	4	2	2	2	0	0	0	3	4	2	2	2	2	2	2	0	4	2	0	0
24	0	0	0	4	4	2	8	2	4	0	0	0	0	4	8	6	0	2	0	2	4	0	8
25	0	0	0	0	2	4	6	2	0	2	2	0	0	2	8	2	0	3	2	0	0	2	4	4

Below left is a quiet pattern for the 8×8 square. By cutting off blank rows and columns, this same pattern also works for the 6×6 and 7×7 squares. The pattern can also be tiled, so it will work for any m×n rectangle where m,n = 6,7,8 (modulo 9).
Note that in general the quiet patterns for this game cannot be tiled as a pattern usually affects two layers of squares around it, and these are effects are not automatically cancelled by a mirror image of the pattern on the other side of those layers.

X X X X X X X X X X X X X X X X

X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

Lights Out 2000.

The maths of the Lights Out 2000 game is just the same, except that it works modulo 3 instead of modulo 2. Pressing a button now increases the value of the adjacent lights, where a green light has value 1 and a red light value 2 (or if you prefer -1). The solution method is the same.
Unfortunately theorem 1 no longer holds, so there are reflexive symmetric games that are unsolvable, i.e. where it is impossible to solve the position with all lights on (the same colour). The solvability test still holds except that it is a bit more complicated:

1. Start with a running total of 0.
2. Consider a quiet button pattern. If a button is pressed once, then add the value of that light to your running total. If a button is pressed twice, then add the value of that light to your running total twice. Unpressed buttons are ignored. Do this for all buttons.
3. If that total is not a multiple of 3, then the pattern is unsolvable.
4. If the light pattern passes this test for all quiet patterns, then it is solvable.

I have again calculated the rank of each Lights Out 2000 game on a rectangular grid up to 25×25. The table below shows the results. For example at 4×4 it shows 2, which means there are 3² quiet patterns. If a number is marked with *, # or @ it means that the game is not solvable.

	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2	1*
3	1	0
4	0	2#	2
5	2	1	0	3
6	0	0	0	0	0
7	1	0	2	1	0	0
8	1*	1	0	4	0	1	4*
9	1	2	2	1	0	2	1	2
10	0	0	0	0	0	0	0	0	0
11	2	1	2#	3	0	1	4	3	0	3
12	0	0	0	0	3	0	0	0	0	0	6
13	1	0	0	1	3@	0	1	0	0	1	6	6
14	1*	3#	2	2	0	3	1*	3	0	8#	0	1	7*
15	1	0	2	1	0	0	1	2	0	1	0	0	3	0
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
17	2	1	0	5	0	1	8	1	0	5	0	1	2	1	0	12
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
19	1	2	4#	1	0	2	1	4	0	3	0	0	5#	2	0	1	0	6
20	1*	1	0	2	0	1	1*	1	0	2	3	4@	1*	1	0	2	0	1	1*
21	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0	0	1	0
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
23	2	1	2	3	0	1	4	3	0	3	0	1	8	1	0	5	0	3	2	1	0	3
24	0	2#	2	0	0	2	0	2	0	2#	0	0	2	2	0	0	0	4#	0	0	0	2	2
25	1	0	0	1	3	0	1	0	0	1	6	6	1	0	0	1	0	0	4	0	0	1	0	6

The entries marked in red with a * have m,n = 2 (mod 6). These have a quiet pattern with a number of button presses not a multiple of 3, so that the solvability check on the position with all lights on will fail. The quiet pattern looks like this, and can be extended indefinitely horizontally and vertically:

1	1		2	2		1	1
1	1		2	2		1	1
2	2		1	1		2	2
2	2		1	1		2	2
1	1		2	2		1	1
1	1		2	2		1	1

The entries marked in orange with a # have m = 3 (mod 8) and n = 4 (mod 10) or vice versa. The entries marked in yellow with @ have m=13 and n=6(mod 14). The bad quiet patterns are based on the patterns below. They can be extended like a checkerboard in both directions just like the previous case.

1	1	1	1
1			1
1	1	1	1

1	1	1			1		1			1	1	1
1		1	2	2	2	1	2	2	2	1		1
1		2	1			1			1	2		1
1		2	1			1			1	2		1
1		1	2	2	2	1	2	2	2	1		1
1	1	1			1		1			1	1	1

Some other cute facts.

There are some button patterns for which the affected lights are exactly the same as the buttons pressed. This means that:

x A = x
or
x (A - I) = 0

where I is the identity matrix. Such patterns are eigenvectors of the matrix A. It is interesting to note that these patterns can be thought of as the quiet patterns of a Lights Out game with matrix A-I, which is a non-reflexive game where each button changes its neighbours but does not change its own light.

The eigenvectors are actually found more easily by just playing the game. Press any button on the top row, and chase the lights down in such a way that the each row has just those lights on in the buttons that were pressed. You will find that the last row also has that property, so the pattern you created is such an eigenvector. Since this works with any single button press in the top row, it will also work with any combination of buttons on the top row. There are therefore 2ⁿ such patterns on an n×n board. Similar patterns also work on a square board when working modulo 3, such as the Lights Out 2000.

Below are the five eigenvector patterns on the standard board that use one light/button on the top row.

X X X X X

X X X X X X X X

X X X X X X X X X

X X X X X X X X

X X X X X

These patterns can of course be used to tile a rectangular board in the usual way. This gives 2^d patterns for any m×n rectangle with m = a·(d+1)-1, n = b·(d+1)-1. In [GK2] it is proved using Fibbonaci polynomials that these are the only ones on rectangular grids. In that paper these patterns are called "Even Open Dominating Sets".

The 5×5 Knights game also has 2⁵ of these patterns, and they are generated by the five shown here:

X X X X

X X X X X X X X

X X X X X

X X X X

X X X X X

The Orbix (game type 1) also has eigenpatterns. There are 2⁶ of them, generated by six of the patterns in which one hemisphere is lit.

Lets also consider button patterns for the standard Lights Out game where the affected lights are exactly those that you did NOT press. This means that:

x A = 1 - x
or
x (A + I) = 1

If we are working modulo 2, the matrix A+I is the same as A-I, so x is also a button pattern that lights up everything in the non-reflexive game, where each button only changes its neighbours and not its own light. The buttons along one diagonal form a quiet pattern in this non-reflexive game, so the solvability test shows that this game is not solvable when n is odd. When n is even it turns out to be solvable, and from the 2ⁿ quiet patterns we then find that there are 2ⁿ such button patterns that in the normal square Lights-Out change only the lights that are not pressed. One general solution is shown below, and it is easily seen that it can be extended indefinitely to any even square by adding more L-shaped pieces.

X			X	X			X
X							X
		X			X
		X			X
X							X
X			X	X			X
	X	X			X	X

In [GK2] it is proved that most rectangular boards have these patterns too (called Odd Open Dominating Sets). The only rectangles that don't are of the form (2^ta+1)×(2^tb+1) for some t>0 and odd a, b.

The Orbix is non-reflexive, so there A+I is the matrix for the reflexive game. The patterns that light up everything are generated by opposite pairs of buttons. Thus the patterns on the Orbix that change exactly the unpressed lights are the 2⁶ patterns consisting of antipodal button pairs.

Other variants.

There are some Lights Out variants that as far as I know only exist in software form. Some of these offer some interesting insights.

Tile Toggle

In Lights Out variants with more than two colours, repeated button presses usually cycle the affected lights through all possible states. One unusual variant that does not is TileToggle which has 4 colours and two types of move. Move type 1 swaps white with red, and black with blue. Move type 2 swaps white with blue, and black with red. These two move types still commute, it does not matter which order they are done.

It turns out that this variant is equivalent to solving standard lights out twice. First treat white and black as if they were one colour, with red and blue being the second colour. You can then solve this like the standard 2-state game until all the lights are white or black. By doing a type 1 move combined with a type 2 move you swap the colours white and black. Using this combined move, you can then solve the black and white board. This is very similar to how a standard 4-colour Lights Out game could be solved, by first using single moves to eliminate colours 1 and 3, and then using double moves to change any lights of colour 2 to colour 0.

Alien Tiles

A common Lights Out type of game has moves where pressing a light on a rectangular grid changes all the lights in the same column and all the lights in the same row, including the light that was pushed. The best known of these is Alien Tiles, which uses 4 colours and this move shape. Often the goal is to try to make all the lights the same colour, without actually prescribing which colour that should be.

Let s be the number of colours that the game has. If you choose four lights that lie in a rectangle shape (i.e. they all lie in two columns and in two rows) and press two diagonally opposite lights s-1 times, and the other two once each, then only those four lights are changed. This allows us to do a kind of light chasing on all but the first row and column. Other useful combinations are to press all the buttons in a row (or column), which changes every light in that row/column k times, where k is the length of that row/column, and every other light changes once.

Here is a solution to Alien Tiles.

1. Choose any of the s colours of the puzzle.
2. For any light that lies not in the first row or column and which is not yet your chosen colour,
   1. press that light s-1 times.
   2. press the light in the first row that lies in the same column as that light, and
   3. press the light in the first column and the same row that light.
   Apart from the first row/column, this should only have affected your chosen light.
3. Repeat step b, until all the lights apart from the first row/column are the same.
4. Choose any row (other than the top row) where its first light does not match the rest of the row. Then
   1. press each light in that row except for the first one, and then
   2. press the top left corner.
   3. Repeat steps 1 and 2 above until the row is a single colour.
   Note that this row need not match the other rows any more, but that does not matter for now.
5. Repeat step d until each row (except the top row) is a single colour.
6. Choose any row (other than the top row) that is of a different colour than the bottom row. Then:
   1. Press all the lights in that row.
   2. Repeat step 1 until that row and the bottom row have the same colour.
   At this point everything but the top row is a single colour.
7. Repeat step f until all the rows (except the top row) have the same colour.
8. If the first column is not a single colour (the top light does not match the rest), then
   1. Press every light in the top row once.
   2. Repeat step 1 until the first column is of a single colour.
9. Choose any column where its top light does not match the rest of the column. Then
   1. press each light in that column except for the top one.
   2. Re-solve the first column as in step h above.
   3. If the chosen column is not yet a single colour, then try steps 1-2 again.
10. Repeat step i until each column is a single colour.
11. Choose any column that is of a different colour than the first column. Then:
    1. Press all the lights in that column.
    2. Repeat step 1 until that column and the first column have the same colour.
12. Now all the lights are the same colour. If you want all of them to be a different colour then press all the lights on the board once. Repeat until it is the colour you want.

This solution does not always work for every pattern on every board. In particular, if w is the width of the board then in step d1 we need w-1 to be coprime to s, so that repeating that step will eventually make the first light of the row equal to the rest regardless of their initial state. Step f also depends on this. Similarly h-1 (where h is the height of the board) must be coprime to s for step h (and steps i2 and k) to always work. If any of these steps do not work (i.e. you end up where you started after one or more tries without getting the colours to match), then the pattern is unsolvable.
For the puzzle to be solvable in any colour, we need the last step to cycle through all possibilities. This happens if w+h-1 (which is the amount all the lights change by) is coprime to s.

There is another way to look at this problem. If a board is always solvable then there is a unique way to change only a single light. Suppose you have this unique button pattern that changes only a single light. You can permute the rows not containing that changing light and it still has the same effect, so these rows of the button pattern must be the same. Similarly the columns other than the one containing the changing light must all be the same.
Let A denote the light itself.
Let B denote all the other lights in the same row as A.
Let C denote all the other lights in the same column as A.
Let D denote all the remaining lights not in A, B, or C.
The argument above shows that in each of these four sets of lights, all the lights need to be pushed the same number of times. Let a, b, c, and d be those numbers. For simplicity, we would like d=0. We can do this by combining the button pattern with the press-everything-pattern s-d times. This simplified pattern no longer only changes a single light, but instead it just changes that light relative to the rest of the board. Let's now work out the effect of these button pushes on each set of lights:
D: The lights change b+c times.
C: The lights change a + (h-1)c times.
B: The lights change a + (w-1)b times.
A: The light changes a + (w-1)b + (h-1)c times.
For this to be the kind of pattern we are looking for, the effects on D, C, and B must be the same (modulo s). A little algebra then gives us that the pattern must be some multiple of:
c = (h-1)^-1
b = (w-1)^-1
a = b+c-1
The effect of this move is that the light in A is changed b+c+1 times, and all the other lights only b+c times. As mentioned before, this only works if h-1 and w-1 are coprime to s, so that they have inverses.

The above analysis heavily relies on it being played on a rectangular board. It can also be played on other boards, for example Tacoyaki is played on the diagonals of a square. As these diagonal columns/rows are not all the same length, all the analysis in this section does not apply here. It may be that the only way to fully solve it is to use the standard matrix techniques, i.e. set up the full move matrix and invert it.

• Home
• Links
• Guestbook

The Mathematics Of Lights Out Pdf

Source: https://www.jaapsch.net/puzzles/lomath.htm

Posted by: oneallaremas.blogspot.com

Share this post