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

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

x = c A^-1

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

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.

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.

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.

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:

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.

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

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.

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.

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.

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:

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.

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.

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-1a_ka_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.

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.

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.

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.

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.

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:

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.

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

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:

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:

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.

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.

We can generalise the last example a bit to get:

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.

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.

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₅:

 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

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:

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.

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.

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:

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.

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.

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.

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.

The theorem below was proved algebraically in [ST], but here I give an easier to understand 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 2^e = 1 modulo n.

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.

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.

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:

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.

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

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.

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:

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.

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.