A good simple reference for the mathematics is Issue 7/8 of Cubic Circular (David Singmaster, Summer 1985) which has an analysis of the XL25, 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. 300303.
[CG]
Loop Deletion for the Lamp Lighting Problem, by William Y. C. Chen and Nancy S. S. Gu.
[DW]
Universal Configurations in LightFlipping Games, by Yevgeniy Dodis and Peter Winkler (2001). Proceedings of 12th Annual ACM/SIAM Symposium on Discrete Algorithms, January 2001, pp. 926927.
[EES]
Note on the lamp lighting problem, by Henrik Eriksson, Kimmo Eriksson and Jonas Sjöstrand (2001). Adv. Appl. Math., vol. 27, pp. 357366.
[GTK1]
Setting Switches in a Grid, by John Goldwasser, William F. Klostermeyer, George E. Trapp, and C. Q. Zhang (1995). Technical Report TR9520, Dept. of Statistics and Computer Science, West Virginia University.
[GTK2]
Characterizing SwitchSetting Problems, by John Goldwasser, William F. Klostermeyer, and George E. Trapp (1997). Linear and Multilinear Algebra, vol. 43, pp. 121135.
[GK1]
Maximization Versions of "Lights Out" Games in Grids and Graphs, by John Goldwasser and William F. Klostermeyer (2002). Congressus Numerantium, vol. 126, pp. 99111.
[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. 271283.
[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 litonly 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ínSánchez and Cristóbal ParejaFlores (1998). Math Magazine, vol 74 (2001), pp. 295304.
[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 ChebyshevPolynomials, by Klaus Sutner (1996). Theoretical Computer Science, vol. 230, (2000), no. 12, pp. 4973.
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_{j}a_{ji}or in matrix form (using row vectors):
r = p + x AHere c=rp 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:
or
x A = r  p = c
x = c A^{1}This makes it a lot simpler; to solve any position, all we have to do is plug in the numbers, and out comes the button pattern we need. Each light pattern will directly give a unique button pattern needed to solve it. Such a game is completely solvable, i.e. every light pattern can be solved.
Lets call the entries of the A^{1} matrix b_{ij}, and examine them more closely. Suppose we try to only change light k, so c_{k}=1 and all other c_{i}=0. This isolates one row of the matrix:
x_{j} = Sum_{i} c_{i} b_{ij} = b_{kj}This means that the rows of A^{1} are the button patterns that change each light individually. Calculating A^{1} from A is fairly straightforward, and can be found in any linear algebra book. We will do this later.
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 pseudoinverse B we get in that case has as a submatrix 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 pseudoinverse 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.
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 ad, separating the squares into four sets.
c  b  a  b  c 
a  d  a  d  a 
b  b  d  b  b 
a  d  a  d  a 
c  b  a  b  c 
The three nontrivial 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 (8A)+(8B)+C+D. Since we have assumed that we had an optimal solution, this solution cannot be better. This means that (8A)+(8B)>=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.
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.
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 pseudoinverse, the last two columns are nearly the same as the quiet patterns. All this is not necessarily the case in nonsymmetric games.
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 nonreflexive. Some lights act reflexively, meaning that it changes its own state when pressed, while others act nonreflexively. 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 nonsymmetric effects form a bipartite graph, a property that symmetric games certainly have (since they don't have any nonsymmetric 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 nonsymmetric 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.
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.
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.
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 litonly 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 allon position. I will copy their proof here. It relies on the following lemma.
Although theorem 3 shows regular solvable positions can always be solved in the litonly 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 litonly games without extra moves.
On the right you see an example of a position for which the litonly solution uses exactly the same button presses as the regular solution. The twelve buttons that form the solution fall apart into three regions:
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 litonly 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 litonly game, as pressing the only lit button in the solution leads to a position that fails the conditions.
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 litonly 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 k1, the number of button presses is 2k, and then the theorem requires k+1 and k1 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.
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^{2}=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 A^{2}=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 5fold symmetry. This 5fold 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 nondiagonal entry occurs an even number of times, so modulo 2 there will automatically be only zeroes in all nondiagonal entries. Thus the symmetry of the Orbix forces A^{2}=I or A^{2}=O. In fact, the entries on the diagonal will be a+b+c+d, so we have A^{2}=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^{2}=I or A^{2}=O, and again we have A^{2}=I if and only if the light pattern of a move changes an odd number of lights.
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 {a_{ij}} is as follows. Let p be a permutation of the numbers 1 to n (i.e. p is an element of the symmetric group S_{n}). Calculate the product sgn(p)·a_{1 p(1)}·a_{2 p(2)}·a_{3 p(3)}·...·a_{n p(n)}, where the sgn(p) is +1 if p is an even permutation, or 1 if p is an odd permutation. Do this for all n! possible permutations, and add these numbers together. The result is the determinant. This is generally a rather labour intensive way to calculate the determinant but as we shall see later, it is useful in this setting.
Before going on, I shall prove a few useful properties of the determinant.
Property 1: If two rows of a matrix are swapped, the determinant changes sign, but not its magnitude.
Property 2: If a matrix has two equal rows, then the determinant is zero.
Property 3: If we multiply a whole row of a matrix by some number r, then the determinant is also multiplied by r.
Property 4: If a row of a matrix has only zeroes, then the determinant is zero.
Property 5: If a multiple of one row of the matrix is added to another, the determinant remains the same.
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 nonzero throughout. A noninvertible 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. nonzero). This proves the following:
Corollary: The determinant of a matrix is nonzero if, and only if, the matrix has an inverse.
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 Ppentomino:
1  2  3 
4  5 
The five squares have been labelled with the numbers 1 to 5. If we use the usual type of move, i.e. each button changes its own light as well as its neighbours, then the associated matrix is:
1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1
Lets consider some permutations p, and see what their corresponding terms are in the determinant calculation.
Permutation p  (123)  (1254)  (1452)  (23)(45) 

Matrix entries i,p(i) marked  1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1  1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1  1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1  1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1 
determinant term  1·1·0·1·1 = 0  1·1·1·1·1 = 1  1·1·1·1·1 = 1  1·1·1·1·1 = 1 
The first permutation is (123). As you can see a_{3 p(3)} = a_{31} = 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 nonzero. 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 2cycles. 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:
1  2  3 
4  5 
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 nonzero 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 nonzero 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 gridlike 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.
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×(n1) rectangle in any one of
R(1,n1) ways. If we start with a domino on he other hand, then the remainder is a 1×(n2)
rectangle that can be filled in R(1,n2) ways. Therefore, R(1,n)=R(1,n1)+R(1,n2).
It is trivial to check that R(1,1)=1 and R(1,2)=2, we find that R(1,n) are the Fibonacci numbers,
1, 2, 3, 5, 8, 13, 21, ...
It is easily checked that this is even exactly when n=2 modulo 3. In other
words, rectangles of size 1×(3k+2) have quiet patterns, whereas other 1×n
rectangles have none. The quiet pattern looks like this:
X  X  X  X  X  X  X  X  X  X 
Example 2: 2×n: Suppose we have a domino/monomino tiling of this board.
If it is asymmetric along its long axis, then we can skip it because it will
be cancelled out by its mirror image. After all, we only need to know whether
the total number of tilings is even or odd. Therefore we only need to look at
tilings that are symmetric about the long axis. In the tilings that remain,
every monomino in the top row has a matching monomino in the bottom row.
We can now do a similar trick, not by pairing a tiling with its mirror
image, but another kind of pairing. Given a pattern, exchange every vertical
domino by two monominoes, and vice versa. Two tilings related to each other by
such an exchange can be skipped. This leaves only tilings which have no monominoes
and no vertical dominoes, i.e. only tilings with horizontal dominoes.
If n is even, then there is exactly one such tiling left. Therefore, R(2,2k)
is odd, and in any 2×2k rectangle all light patterns are solvable.
If n is odd, then there are no tilings with only horizontal dominos, so
then R(2,2k+1) is even, and there must be quiet patterns, such as the one shown
below.
X  X  X  X  X  X  
X  X  X  X  X  X 
Example 3: 5×n: Consider a horizontal line through the middle of the board. Like before, any tiling that is not symmetric about this line can  together with its mirror image  be ignored, since we only need the parity of the number of tilings. We only need symmetric tilings. As the line of symmetry goes through a row of squares, there can be no vertical dominoes on this row (that would be asymmetric). The row is then only monominoes and horizontal dominoes, and therefore the symmetric tilings can be split into a tiling of the top 2×n board, a tiling of the 1×n middle row, and a tiling of the bottom 2×n board that is a mirror image of the top part. The number of these tilings is therefore R(5,n)=R(2,n)·R(1,n). For this to be odd both factors must be odd, so from the previous examples we see that n must be even and also not 2 modulo 3. The number of tilings is therefore odd exactly when n is 0 or 4 modulo 6. In other words all light patterns in 5×6k or 5×(6k+4) rectangles are solvable, but on other 5×n rectangles there are quiet patterns.
5 × 2k+1  5 × 3k+2  


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.
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_{n1} ways of completing
the remaining 2×(n1) rectangle. If it horizontal with a horizontal domino
above it then there are S_{n2} 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_{n2}
completions) or there may be one horizontal domino first (giving S_{n4}
completions) or two (S_{n6}), three (S_{n8}) etc. until there
is no more room left. We therefore arrive at:
S_{n} = S_{n1}+2S_{n2}+S_{n4}+S_{n6}+...
To eliminate the tail of this sum, we calculate S_{n}S_{n2}:
S_{n}S_{n2} =
(S_{n1}+2S_{n2}+S_{n4}+S_{n6}+...) 
(S_{n3}+2S_{n4}+S_{n6}+S_{n8}+...) =
S_{n1}+2S_{n2}S_{n3}S_{n4}
so that (at least for n>3)
S_{n}=S_{n1}+3S_{n2}S_{n3}S_{n4}
It is easy to find check by hand that S_{0} to S_{3} are all odd.
By repeatedly plugging this into the equation it becomes clear that S_{n} is
even exactly when n is 4 modulo 5 (i.e. when n=4, 9, 14 etc.).
We already found quiet patterns for n=4, and by repeating them we can find
quiet patterns for all those 4×(5k+4) rectangles. All other 4×n
rectangles have no quiet patterns.
X  X  X  X  X  X  X  X  X  
X  X  X  X  X  X  
X  X  X  X  X  X  
X  X  X 
The same techniques don't work well for wider rectangles as it gets messy very quickly. What can be said is that for every fixed m, as n increases the parity of R(m,n) will show a repeating pattern.
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 xIA, 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(xIA) 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(kIA)=0. This matrix therefore is not invertible, and has its own 'quiet pattern', i.e. we can find a nonzero (column)vector v such that (kIA)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(AkI)=0 or wA=kw.
Note that since Av=kv, we get A^{2}v = A(Av) = Akv = k(Av) = k(kv) = k^{2}v, and similarly for higher powers A^{i}v=k^{i}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 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.
Let's now look at a special type of matrix, namely the square matrix A_{n} which has a_{ij}=1 whenever i=j1 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_{5} 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 nonzero 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_{5}:
xIA_{5}  p(1)=1  p(1)=2, p(2)=1  
Matrix with p marked  x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 
x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 
x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 
Determinant terms  x c_{4}(x)  1·1·c_{3}(x) 
This gives us the recursive rule
c_{n}(x) = char[A_{n}](x) =
det(xI_{n}A_{n}) =
x det(xI_{n1}A_{n1}) 
1·1·det(xI_{n2}A_{n2}) =
x c_{n1}(x)  c_{n2}(x)
For the small cases we find that c_{1}(x)=x, c_{2}(x)=x^{2}1. By applying the rule we could even say that c_{0}(x)=1.
The polynomials in this sequence are similar to Fibonacci polynomials. The
Fibonacci polynomials are defined by:
f_{0}(x)=0
f_{1}(x)=1
f_{n}(x)=x f_{n1}(x) + f_{n2}(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((x1)IA_{n}) = c_{n}(x1)
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
nonzero 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_{m}X.
Again this is an m×n rectangular matrix, but now each nonzero entry
in X affects only the entries to the left and right of it in the result.
Thus A_{m}X 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_{m}X + 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_{m}X + 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_{1}
and X_{2}. Let Y be X_{1}X_{2},
i.e. the button pattern achieved by combining X_{1} and
X_{2}. This should have no effect on the lights, and indeed:
AY+YB =
A(X_{1}X_{2})+(X_{1}X_{2})B =
AX_{1}+X_{1}B(AX_{2}+X_{2}B) =
CC = O
If X_{1} and X_{2} are distinct, then Y
is a nontrivial 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_{1}
to light pattern C will when, combined with the quiet pattern Y,
give another solution X_{2} = X_{1}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 nontrivial 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 nontrivial m×n matrix. We now find that:
AY+YB = A(vw)+(vw)B = (Av)w+v(wB) = (kv)w+v(kw) = kvwkvw=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(xIB)=0 has root k, or equivalently that k is a root of det(xIB)=0. So if char[A](x) and char[B](x) have a root in common, then there is a nontrivial 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 (xk).
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 x1 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^{2}+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 nontrivial Y that solves the matrix equation. The converse is also true, but I will not prove any of this here. If we put all this together it does lead us to the following theorem:
Theorem 8: A Lights Out game on an m×n grid has quiet patterns exactly when the polynomials c_{m}(x) and c_{n}(x1) have a common factor. In fact, the number of linearly independent quiet patterns is equal to the degree of the largest common factor.
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)=c_{n}(x)  char[B](x)=c_{n}(1x)  

0  1  1  
1  x  x+1  
2  x^{2}1  =  (x+1)(x1)  x^{2}2x  =  x(x2) 
3  x^{3}2x  =  x(x^{2}2)  x^{3}3x^{2}+x+1  =  (x1)(x^{2}2x1) 
4  x^{4}3x^{2}+1  =  (x^{2}x1)(x^{2}+x1)  x^{4}4x^{3}+3x^{2}+2x1  =  (x^{2}x1)(x^{2}3x+1) 
5  x^{5}4x^{3}+3x  =  x(x1)^{2}(x^{2}+2x+3)  x^{5}5x^{4}+6x^{3}+2x^{2}4x  =  x(x1)(x2)(x^{2}2x2) 
6  x^{6}5x^{4}+6x^{2}1  =  (x^{3}x^{2}2x+1)(x^{3}+x^{2}2x1)  x^{6}6x^{5}+10x^{4}9x^{2}+2x+1  =  (x^{3}4x^{2}+3x+1)(x^{3}2x^{2}x+1) 
7  x^{7}6x^{5}+10x^{3}4x  =  x(x^{2}2)(x^{4}4x^{2}+2)  x^{7}7x^{6}+15x^{5}5x^{4}15x^{3}+9x^{2}+3x1  =  (x1)(x^{2}2x1)(x^{4}4x^{3}+2x^{2}+4x1) 
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 x1 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^{2}x1. 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 with p=5 we see in the table of polynomials above that the factors x^{3}+x^{2}2x1 in the left column is equal to x^{3}4x^{2}+3x+1 in the right column modulo 5.
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·nrank, which is the number of generators of the quiet patterns. For example at 11×5 it shows 4, meaning that the rank is 554=51, and that there are 2^{4}=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 (m1)×(n1) quiet pattern we can get patterns of size (im1)×(jn1) 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 (2i1)×(3j1). 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^{n} has a quiet pattern, as well as the square of size 2^{n}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^{n} quiet patterns is the 4×4 board (i.e. all the 2^{4} 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.
Click on the link above to see the huge 1200 by 1200 version. From that picture it becomes very clear that something interesting happens around coordinates that are one less than powers of 2. There seem to be diagonal crosses centred at such coordinates. In August 2012 David Beckman sent me a proof for the existence of (some of) these crosses, using properties of Fibonacci polynomials modulo 2.
Theorem 10 (David Beckman):
Let c = 2^{n}1, and d = 2^{m} for some 0<=m<n.
Then the four Lights Out boards of size c±d by c±d have on average
(c1)/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.
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.
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.
m×n  Ord_{mod m}(2)  Ord_{mod n}(2) 

1×3  1  2 
11×31  10  5 
43×127  14  7 
155×187  20  40 
119×221  24  24 
85×257  16  8 
This is a similar table for the XL25 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.


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:
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^{2} quiet patterns. If a number is marked with *, # or @ it means that the game is not solvable.
2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  

2  1*  
3  1  0  
4  0  2#  2  
5  2  1  0  3  
6  0  0  0  0  0  
7  1  0  2  1  0  0  
8  1*  1  0  4  0  1  4*  
9  1  2  2  1  0  2  1  2  
10  0  0  0  0  0  0  0  0  0  
11  2  1  2#  3  0  1  4  3  0  3  
12  0  0  0  0  3  0  0  0  0  0  6  
13  1  0  0  1  3@  0  1  0  0  1  6  6  
14  1*  3#  2  2  0  3  1*  3  0  8#  0  1  7*  
15  1  0  2  1  0  0  1  2  0  1  0  0  3  0  
16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
17  2  1  0  5  0  1  8  1  0  5  0  1  2  1  0  12  
18  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
19  1  2  4#  1  0  2  1  4  0  3  0  0  5#  2  0  1  0  6  
20  1*  1  0  2  0  1  1*  1  0  2  3  4@  1*  1  0  2  0  1  1*  
21  1  0  0  1  0  0  1  0  0  1  0  0  1  0  0  1  0  0  1  0  
22  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  
23  2  1  2  3  0  1  4  3  0  3  0  1  8  1  0  5  0  3  2  1  0  3  
24  0  2#  2  0  0  2  0  2  0  2#  0  0  2  2  0  0  0  4#  0  0  0  2  2  
25  1  0  0  1  3  0  1  0  0  1  6  6  1  0  0  1  0  0  4  0  0  1  0  6 
The entries marked in red with a * have m,n = 2 (mod 6). These have a quiet pattern with a number of button presses not a multiple of 3, so that the solvability check on the position with all lights on will fail. The quiet pattern looks like this, and can be extended indefinitely horizontally and vertically:
1  1  2  2  1  1  
1  1  2  2  1  1  
2  2  1  1  2  2  
2  2  1  1  2  2  
1  1  2  2  1  1  
1  1  2  2  1  1 
The entries marked in orange with a # have m = 3 (mod 8) and n = 4 (mod 10) or vice versa. The entries marked in yellow with @ have m=13 and n=6(mod 14). The bad quiet patterns are based on the patterns below. They can be extended like a checkerboard in both directions just like the previous case.
1  1  1  1 
1  1  
1  1  1  1 
1  1  1  1  1  1  1  1  
1  1  2  2  2  1  2  2  2  1  1  
1  2  1  1  1  2  1  
1  2  1  1  1  2  1  
1  1  2  2  2  1  2  2  2  1  1  
1  1  1  1  1  1  1  1 
There are some button patterns for which the affected lights are exactly the same as the buttons pressed. This means that:
x A = xwhere 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 AI, which is a nonreflexive game where each button changes its neighbours but does not change its own light.
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^{n} 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^{5} of these patterns, and they are generated by the five shown here:





The Orbix (game type 1) also has eigenpatterns. There are 2^{6} 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 AI, so x is also a button pattern that lights up everything in the nonreflexive game, where each button only changes its neighbours and not its own light. The buttons along one diagonal form a quiet pattern in this nonreflexive 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^{n} quiet patterns we then find that there are 2^{n} such button patterns that in the normal square LightsOut 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 Lshaped pieces.
X  X  X  X  
X  X  
X  X  
X  X  
X  X  
X  X  X  X  
X  X  X  X 
In [GK2] it is proved that most rectangular boards have these patterns too (called Odd Open Dominating Sets). The only rectangles that don't are of the form (2^{t}a+1)×(2^{t}b+1) for some t>0 and odd a, b.
The Orbix is nonreflexive, 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^{6} patterns consisting of antipodal button pairs.
There are some Lights Out variants that as far as I know only exist in software form. Some of these offer some interesting insights.
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 2state 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 4colour 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.
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 s1 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.
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 w1 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 h1 (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+h1 (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 presseverythingpattern sd 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 + (h1)c times.
B: The lights change a + (w1)b times.
A: The light changes a + (w1)b + (h1)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 = (h1)^{1}
b = (w1)^{1}
a = b+c1
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 h1 and w1 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.