Jaap's Puzzle Page

The Mathematics of Lights Out

Maths Page

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. To appear in Clay mathematics Proceedings, vol. 18, (2013).
[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 aji is 1 if light i is changed by button j, or 0 otherwise.
Let p be starting position vector, i.e. pi is 1 if light i is on at the start, 0 otherwise.
Let x be the button pattern we press, i.e. xj is 1 if we press button j, or 0 if not.
Let r be the end position vector, i.e. ri 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

ri = pi + Sumj xjaji
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 bij, and examine them more closely. Suppose we try to only change light k, so ck=1 and all other ci=0. This isolates one row of the matrix:

xj = Sumi ci bij = bkj
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:

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.

cbabc
adada
bbdbb
adada
cbabc

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!2 · 8!/4!2 · 4!/2!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. aij=aji. 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. aii = 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 view proof.

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 view proof.

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 view proof.

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

Proof 2 of theorem 1: Click to view proof.

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 view proof.

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.

This is actually remarkably hard to prove. Several of my earlier attempts at proof had holes in them, so I hope that the proof below holds water.

Proof of theorem 3: Click to view proof.

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 3c:
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 3c: Click to view proof.
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 view proof.

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 view proof.

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 view proof.

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 view proof.

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 A2=I. This means that A=A-1, i.e. that the matrix is its own inverse. In this case 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 A2=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 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 A2=I or A2=O. In fact, the entries on the diagonal will be a+b+c+d, so we have A2=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 A2=I or A2=O, and again we have A2=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 if 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 {aij} is as follows. Let p be a permutation of the numbers 1 to n (i.e. p is an element of the symmetric group Sn). Calculate the product sgn(p)·a1 p(1)·a2 p(2)·a3 p(3)·...·an 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 view proof.

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

Proof: Click to view proof.

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 view proof.

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

Proof: Click to view proof.

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

Proof: Click to view proof.

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:

123
45

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 term1·1·0·1·1 = 01·1·1·1·1 = 11·1·1·1·1 = 11·1·1·1·1 = 1

The first permutation is (123). As you can see a3 p(3) = a31 = 0, because squares 3 and 1 are not adjacent. The resulting term of the determinant also 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:

123
45

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:

XX XX XX XX XX

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+15 × 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
XX XX XX XX
XX XX XX XX
XX XX XX XX

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 view proof.

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
XXX
X
XX X
XXX
X X
XX
X
XX
X X
X X
XX
X X
XXXX
XXXX
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 Sn 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 Sn-1 ways of completing the remaining 2×(n-1) rectangle. If it horizontal with a horizontal domino above it then there are Sn-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 Sn-2 completions) or there may be one horizontal domino first (giving Sn-4 completions) or two (Sn-6), three (Sn-8) etc. until there is no more room left. We therefore arrive at:
Sn = Sn-1+2Sn-2+Sn-4+Sn-6+...
To eliminate the tail of this sum, we calculate Sn-Sn-2:
Sn-Sn-2 = (Sn-1+2Sn-2+Sn-4+Sn-6+...) - (Sn-3+2Sn-4+Sn-6+Sn-8+...) = Sn-1+2Sn-2-Sn-3-Sn-4
so that (at least for n>3) Sn=Sn-1+3Sn-2-Sn-3-Sn-4
It is easy to find check by hand that S0 to S3 are all odd. By repeatedly plugging this into the equation it becomes clear that Sn 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.

XXX XXX XXX
X X X X X X
XX XX XX
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 A2v = A(Av) = Akv = k(Av) = k(kv) = k2v, and similarly for higher powers Aiv=kiv. 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 vi, and similarly exactly n row eigenvectors wi.

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 An which has aij=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, A5 is:

01000
10100
01010
00101
00010

The characteristic polynomial cn(x) for matrix An 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 A5:

xI-A5p(1)=1p(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 termsx c4(x)-1·-1·c3(x)

This gives us the recursive rule
cn(x) = char[An](x) = det(xIn-An) = x det(xIn-1-An-1) - -1·-1·det(xIn-2-An-2) = x cn-1(x) - cn-2(x)

For the small cases we find that c1(x)=x, c2(x)=x2-1. By applying the rule we could even say that c0(x)=1.

The polynomials in this sequence are similar to Fibonacci polynomials. The Fibonacci polynomials are defined by:
f0(x)=0
f1(x)=1
fn(x)=x fn-1(x) + fn-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 cn(x) = fn+1(x). One reason that these are named after Fibonacci is that fn(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 Bn = An+I. These matrices Bn are the same as An except that they have ones along the diagonal. Its characteristic polynomial is now easy to deduce:

char[Bn](x) = det(xI-(An+I)) = det((x-1)I-An) = cn(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 Am and Bn will be used for that.

Consider XBn.
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 XBn is the result of the button presses if only vertical neighbours (and the button itself) were affected by each button press.

Similarly, now consider AmX.
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 AmX 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 AmX + XBn 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 AmX + XBn = 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 X1 and X2. Let Y be X1-X2, i.e. the button pattern achieved by combining X1 and X2. This should have no effect on the lights, and indeed:
AY+YB = A(X1-X2)+(X1-X2)B = AX1+X1B-(AX2+X2B) = C-C = O
If X1 and X2 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 X1 to light pattern C will when, combined with the quiet pattern Y, give another solution X2 = X1-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 x2+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 cm(x) and cn(-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 view proof.

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)
011
1xx+1
2x2-1=(x+1)(x-1)x2-2x=x(x-2)
3x3-2x=x(x2-2)x3-3x2+x+1=(x-1)(x2-2x-1)
4x4-3x2+1=(x2-x-1)(x2+x-1)x4-4x3+3x2+2x-1=(x2-x-1)(x2-3x+1)
5x5-4x3+3x=x(x-1)2(x2+2x+3)x5-5x4+6x3+2x2-4x=x(x-1)(x-2)(x2-2x-2)
6x6-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)
7x7-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 x2-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[An](x) and char[Bn](-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[An](x) and char[Bn](-x) have a common factor modulo p. For example in the 6×6 case with p=5 we see in the table of polynomials above that the factors x3+x2-2x-1 in the left column is equal to x3-4x2+3x+1 in the right column modulo 5.

 

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 24=16 quiet patterns (of which one is the trivial pattern).
12345678910111213141516171819202122232425
10
210
3020
40004
511302
6000000
70200400
810201620
9010410018
100000000000
1112304072106
12000000000000
130100100700100
1410241020502014
15020040020080020
160000000000000808
17113026411040131402
18000000000000000000
1902043002803006003016
2010201026102010207020
21010010010010010010010
220000000000000000000000
2312305072101001215050321014
24000400004000040000400004
250100100100100100100100100

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.

XX
X X
X X
XX
XX XX
X X X X
X X X X
XX XX
XX XX
X X X X
X X X X
XX XX

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
XXX
X
XX XX
X X
XXX XX
X X X
XXX
X
XX
X X
XXX
X
XX XX
X X
X XX
X X
XX XXX
X X X X
XXX XX X XX
X X X X X
XX X XX
X X X X
X X XX XX XX
X X X X
XX XXX XXX
X X X
X XX XXX XXX
X X X X
XXX XXX
X X X X X
X X X XX XXX
X X
XXX XXX
X X X
XX X X X XX
X X X
XX X XX XXX
X X
XXX XXX XX X
X X X X X
XXX XX X X X
X X X X
XX XX XXX
X X X X X
XX XX XXX XX
X X X X
XX X XX XXX
XX X X X XX XX
X X X X X
XXX XX X X X
X X X
XXX XX X XX
X X X
XX X XX XXX XXX
X X X X X
XX XX XXX XX
X X X
XX X XX XX XX
X X X X
XX XX XXX
X X X X
XXX XX XX
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.

100 by 100 Lights Out table

In [GKW] it is proven that the square Lights Out board with edge length 2n has a quiet pattern, as well as the square of size 2n-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 2n quiet patterns is the 4×4 board (i.e. all the 24 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.

Proof: Click to view proof.

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 = 2n-1, and d = 2m 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 view proof.

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.
345678910111213141516171819202122232425
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 614 4 4
10 4 0 8 4 0 0 416
11 2 0 0 2 0 0 2 0 0
12 6 8 212 216 6 4 216
13 2 0 0 2 0 0 2 0 0 2 0
14 4 0 0 4 0 016 0 0 4 0 0
15 4 410 6 2 4 412 2 6 2 412
16 4 0 0 8 0 0 4 0 016 0 0 4 0
17 2 0 0 2 0 0 2 0 0 2 0 018 016
18 6 8 2 814 8 6 4 212 228 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 416 0 8 0 012 0 0 8 032
21 4 4 2 6 2 416 4 2 6 2 4 4 4 218 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 212 216 6 4 224 2 4 632 212 2 8 6 4 232
25 2 0 8 2 0 0 2 8 0 2 0 010 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.

XX
X X
X X
XX
X XXXX X
XXXX XX XXXX
X X XXXX X X
XX X X XX
XX X XX X XX
X XX XX X
X X XX X X
XXX X X X X XXX
XXX X X X X XXX
X X XX X X
X XX XX X
XX X XX X XX
XX X X XX
X X XXXX X X
XXXX XX XXXX
X XXXX 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 view proof.
Torus Theorem 1:
A torus of size 2am×2bn has no quiet patterns if and only if the m×n torus has none. [ST]
Proof: Click to view proof.

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 2e = 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×nOrdmod m(2)Ordmod n(2)
1×312
11×31105
43×127147
155×1872040
119×2212424
85×257168

 

Results for the XL-25 knight's game.

This is a similar table for the XL-25 knight's game.
2345678910111213141516171819202122232425
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 412 6 8 0 4 0 4 0 0 812
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 010 2 4 6 6 0 0 0 4 0
20 0 2 0 2 0 0 0 420 4 0 2 4 0 8 2 4 0 0
21 2 0 4 0 0 0 2 010 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 XX X
X X
X X
X XX X
X X
X X X X
X XX X X XX X
X X X X
X X X X
X XX X X XX X
X X X X
X X X X
X XX X X XX X
X X X X
X X X X
X XX X X XX 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 32 quiet patterns. If a number is marked with *, # or @ it means that the game is not solvable.
2345678910111213141516171819202122232425
21*
310
402#2
52103
600000
7102100
81*104014*
912210212
10000000000
11212#3014303
1200003000006
1310013@0100166
141*3#22031*308#017*
1510210012010030
16000000000000000
1721050181050121012
1800000000000000000
19124#1021403005#20106
201*102011*10234@1*102011*
2110010010010010010010
22000000000000000000000
232123014303018105032103
2402#20020202#00220004#00022
25100130100166100100400106

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:

11 22 11
11 22 11
22 11 22
22 11 22
11 22 11
11 22 11

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.

1111
1 1
1111
111 1 1 111
1 122212221 1
1 21 1 12 1
1 21 1 12 1
1 122212221 1
111 1 1 111

 

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 2n 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 2d 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 25 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 26 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 2n quiet patterns we then find that there are 2n 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 XX X
X X
X X
X X
X X
X XX X
XX XX

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 (2ta+1)×(2tb+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 26 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 form 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.