|
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:
[An]
Turning Lights Out with Linear Algebra, by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4, October 1998, pp. 300-303.
[Ch]
Loop Deletion for the Lamp Lighting Problem, by William Y. C. Chen and Nancy S. S. Gu.
[Do]
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.
[Er]
Note on the lamp lighting problem, by Henrik Eriksson, Kimmo Eriksson and Jonas Sjöstrand (2001). Adv. Appl. Math., vol. 27, pp. 357-366.
[Go1]
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.
[Go2]
Characterizing Switch-Setting Problems, by John Goldwasser, William F. Klostermeyer, and George E. Trapp (1997). Linear and Multilinear Algebra, vol. 43, pp. 121-135.
[Go3]
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.
[Go4]
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.
[Go5]
Odd and Even Dominating Sets with Open Neighborhoods, by John L. Goldwasser and William F. Klostermeyer. To appear in Ars Combinatoria.
[Hu]
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.
[Sa]
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.
[Su]
σ-Automata and Chebyshev-Polynomials, by Klaus Sutner (1996). Theoretical Computer Science, vol. 230, (2000), no. 1-2, pp. 49-73.
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 aij is 1 if light i is changed by button j, or 0 otherwise.
Let p be starting position vector, i.e. pi is 1 if light i
is on at the start, 0 otherwise.
Let x be the button pattern we press, i.e. xj is 1 if we
press button j, or 0 if not.
Let r be the end position vector, i.e. ri is 1 if light i
should be on at the end, 0 otherwise.
The state of light i afterwards is then given by its state at the beginning, plus the effects of all the button presses have on it. Algebraically this is
ri = pi + Sumj xjaijor in matrix form (using row vectors):
r = p + x AHere c=r-p is the difference between the start and end position, or in other words the pattern of lights that have to be changed. Normally we know A and c (we know what the buttons do, and which lights we want to change), and want to find out x (the buttons we have to press to do it). This essentially boils down to solving 25 equations in 25 unknowns, which is a lot of work to do by hand, each time you want to solve the puzzle. If however we can invert the matrix A, we get:
or
x A = r - p = c
x = c A-1This makes it a lot simpler; to solve any position, all we have to do is plug in the numbers, and out comes the button pattern we need. Each light pattern will directly give a unique button pattern needed to solve it. Such a game is completely solvable, i.e. every light pattern can be solved.
Lets call the entries of the A-1 matrix bij, and examine them more closely. Suppose we try to only change light k, so ck=1 and all other ci=0. This isolates one row of the matrix:
xj = Sumi ci bij = bkjThis 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 pseudo-inverse B we get in that case has as a sub-matrix the inverse of the smaller matrix, together with rows containing (generators of) the quiet button patterns, i.e. those button patterns that have no effect on the lights at all.
Below on the left is the full 25×25 matrix A, and on the right is an identity matrix of the same size:
1100010000000000000000000 1000000000000000000000000 1110001000000000000000000 0100000000000000000000000 0111000100000000000000000 0010000000000000000000000 0011100010000000000000000 0001000000000000000000000 0001100001000000000000000 0000100000000000000000000 1000011000100000000000000 0000010000000000000000000 0100011100010000000000000 0000001000000000000000000 0010001110001000000000000 0000000100000000000000000 0001000111000100000000000 0000000010000000000000000 0000100011000010000000000 0000000001000000000000000 0000010000110001000000000 0000000000100000000000000 0000001000111000100000000 0000000000010000000000000 0000000100011100010000000 0000000000001000000000000 0000000010001110001000000 0000000000000100000000000 0000000001000110000100000 0000000000000010000000000 0000000000100001100010000 0000000000000001000000000 0000000000010001110001000 0000000000000000100000000 0000000000001000111000100 0000000000000000010000000 0000000000000100011100010 0000000000000000001000000 0000000000000010001100001 0000000000000000000100000 0000000000000001000011000 0000000000000000000010000 0000000000000000100011100 0000000000000000000001000 0000000000000000010001110 0000000000000000000000100 0000000000000000001000111 0000000000000000000000010 0000000000000000000100011 0000000000000000000000001
Note that each row of the right matrix is a button pattern (with only one button press), and when that pattern is pressed the light pattern is given by the same row in the left matrix. To find the (pseudo) inverse, we use row operations on this combined 25×50 matrix (i.e. swap any two rows, or add one row to another) until the left half has become the identity (or as close to the identity as we can get). During this process, we always have light patterns and corresponding button patterns on each row. After doing this process, called Gaussian elimination, we get this result:
1000000000000000000000001 0111000101000110000100000 0100000000000000000000010 1101101000001110001000000 0010000000000000000000011 1011110110001101111101000 0001000000000000000000010 1110001000000000100011100 0000100000000000000000001 0110110000101010010111000 0000010000000000000000011 0010101101001000001100000 0000001000000000000000000 0101011011000101110001000 0000000100000000000000011 1010010110000011010110100 0000000010000000000000000 0010001110100111001001100 0000000001000000000000011 1000011000101010110100100 0000000000100000000000010 0000100011001011111001000 0000000000010000000000010 0000000000000000100011100 0000000000001000000000000 0110110001101100010011000 0000000000000100000000010 1110001010001110001000000 0000000000000010000000010 1100100111100111101010000 0000000000000001000000011 0010001110100011010110100 0000000000000000100000000 0011001001110010111000100 0000000000000000010000011 0010101101101001101110000 0000000000000000001000000 0110010010100110111000100 0000000000000000000100011 1010110101000001010110100 0000000000000000000010001 0001100100011011010111000 0000000000000000000001010 0011101010111000000011100 0000000000000000000000111 0001000111010001101101000 0000000000000000000000000 0111010101110111010101110 0000000000000000000000000 1010110101000001010110101
The square matrix on the right is the pseudo-inverse of the matrix A.
Here are some neat facts that can be deduced from these matrices:
Note that if you want to analyse a game by hand, these matrices are all far too large. In the standard game, it is easier to use the fact that you can chase the lights. Press a button on the top row, chase the lights down, and see the effect on the bottom row. This way there are 5 possible button presses (the top row) with their effect on 5 lights (the bottom row). This leads to a much smaller matrix, only 5×5 on the standard game. It looks like this:
01101 10000 11100 01000 11011 00100 00111 00010 10110 00001
This reduces to:
10001 11000 01010 11100 00111 01100 00000 01110 00000 10101
From this, nearly all the facts listed before can be deduced.
On the main page I have already explained how to solve a particular position in the minimal number of moves, by finding any solution and then combining it with any quiet pattern to reduce the number of moves as much as possible. What is the worst position to solve, and how many moves does that take?
Below I have marked the 5×5 grid with the letters a-d, separating the squares into four sets.
| c | b | a | b | c |
|---|---|---|---|---|
| a | d | a | d | a |
| b | b | d | b | b |
| a | d | a | d | a |
| c | b | a | b | c |
The three non-trivial quiet patterns of the game are given by the squares a and b, b and c, or a and c. The squares d are not part of any quiet pattern. Suppose we have a position that is most difficult to solve, and have an optimal solution to it. We can assume the solution uses A+B+C+D button presses, where A,B,C,D are the number of buttons of each set that were pressed (so 0<=A,B<=8, 0<=C<=4, 0<=D<=5). If we apply to our solution the quiet pattern formed by a and b, the number of buttons used in the solution becomes (8-A)+(8-B)+C+D. Since we have assumed that we had an optimal solution, this solution cannot be better. This means that (8-A)+(8-B)>=A+B, or A+B<=8. The other quiet patterns give A+C<=6 and B+C<=6. If we maximise A+B+C+D within these constraints, we reach a maximum of 15 when A=B=4, C=2, D=5.
All the worst positions, those that need at least 15 moves to solve, will use 4 button presses in each of the sets a and b, 2 of the buttons in c, and all of the buttons in d. There are 8!/4!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. Only later did I extend the computer program I used to generate the table 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. aij=aji. In terms of the game itself, this means that if pressing one light changes a second light, then pressing that second light will also change the first. This is a very common feature of these games, but it is not necessary. The Merlin Magic Square game for example is not symmetric (i.e. does not have a symmetric matrix).
Another property of the standard Lights Out matrix is that it is reflexive (i.e. aii = 1). In terms of the game itself, this means that pressing a light will always change its own state. The Orbix is not a reflexive game for example, and also the 5×5 matrix above that we got when chasing lights was not reflexive.
In a symmetric game there is an easy way to test if a pattern of lights can be solved. Well, it is easy once you know the quiet patterns that the game has. I will therefore assume that you have calculated the (pseudo)inverse and therefore have some quiet patterns as given by the bottom few rows of that matrix. Every quiet pattern of the game is the sum of one or more of those rows.
Solvability test:
In a symmetric game a light pattern is solvable if, and only if, the number of
lights in common with each quiet button pattern is even.
Proof:
By definition, pressing the buttons of a quiet pattern will change each light an even number of times so that in the end nothing has changed. Therefore each and every light is affected by an even number of the buttons in the quiet pattern. The game is symmetrical, so the converse also holds: each and every button will affect an even number of lights in the quiet pattern. A solvable position must have an even number of lights switched on in each quiet pattern arrangement for it to be possible to bring this number down to zero.
All solvable light patterns will certainly satisfy this test. By counting how many patterns pass this test, it can be shown that only solvable patterns qualify because there is no room for any others.
It follows from this test that the only lights that can be switched on or off independently of the others are those that are not in any of the quiet patterns. In the classic 5×5 game there are 5 such squares (in a previous table the ones marked by letter d), the centre and the diagonally adjacent ones. This also shows why, in the 25×25 simplified matrix we got when calculating the psuedo-inverse, the last two columns are nearly the same as the quiet patterns. All this is not necessarily the case in non-symmetric 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.
Theorem 1:
Every reflexive, symmetric variant of the Lights Out game is solvable,
i.e. it is possible to switch all the lights off when starting with all the
lights on.
In Cubic Circular it says that László Mérõ has proved this result, but the proof is not given. The shortest way to prove it is probably as follows:
Proof 1 of theorem 1:
If A is a reflexive symmetric matrix, then modulo 2 we getx A xT = x I xT = xxTbecause all cross terms occur twice and hence cancel modulo 2, leaving only all the diagonal terms (which are all 1 because of reflexivity). If x is a quiet pattern, i.e. xA=0, thenxxT = x A xT = 0 xT = 0which means that x must use an even number of buttons. From the solvability check we can then deduce that in every reflexive symmetric Lights Out game we can solve the position with all lights on.
Q.E.D.
It is possible to generalise the theorem a bit. Suppose you have a Lights Out game that is a mix of reflexive and non-reflexive. Some lights act reflexively, meaning that it changes its own state when pressed, while others act non-reflexively. The proof above then shows that a position with only the reflexive lights on will be solvable. See also [Do].
I originally proved theorem 1 in a very different way, not relying on the algebra at all. I prefer this proof, despite the fact that it is much longer. To prove the theorem, I will need to prove a simpler result first.
Lemma:
In a symmetric Lights Out game with an odd number of buttons, there is always some
button that affects an even number of other lights. This can also be stated in an
equivalent way which is easier to understand: At a gathering of an odd number of
people, there is always someone who shakes hands an even number of times.
Proof of lemma:
Suppose there are n people at the gathering, with n odd. Let mi be the number of times that person i shakes hands. The total number of handshakes must therefore be (m1+m2+...+mn)/2, because each handshake has two people taking part. This is a proper integer only if the sum is even, which can only mean that not all mi can be odd. Therefore at least one person shakes hands an even number of times.
With that lemma, we can get the following proof for theorem 1.
Proof 2 of theorem 1:
If there were unsolvable ones, then there would have to be one with the smallest possible number of lights, say n. In other words, any game with n-1 buttons is solvable, but we have a particular game with n buttons that is not.For any light/button i, the other n-1 buttons and lights form a smaller game and are therefore solvable. Changing all those n-1 lights will however not change light i because we have assumed this game was unsolvable. We can therefore find n patterns which each change everything except for a single light.
Suppose we perform these n patterns which each change all but one light. Every light will now have changed n-1 times. If n were even, this would mean that every light has changed state which would make our game solvable. Therefore our unsolvable game must have n odd.
Suppose there were some button pattern we could press which changes the state of an odd number of lights. For each light that was changed, perform the pattern which changes everything except that light. Now every light will have changed an odd number of times, which again would make the game solvable. Therefore all button patterns in an unsolvable game change an even number of lights.
So far I have proved that the smallest unsolvable game must have an odd number of lights/buttons, and that every button pattern changes an even number of lights. However, if the game is reflexive and symmetric, then from the previous lemma there must be some button which changes an odd number of lights (itself and an even number of others). Therefore there can be no unsolvable reflexive symmetric Lights Out game.
Q.E.D.
It turns out that a very similar proof was found and published a few months before this one (see [Er]). It does not assume the game is symmetric, but assumes its non-symmetric effects form a bipartite graph, a property that symmetric games certainly have (since they don't have any non-symmetric effects). It also applies to Merlin's Magic Square, or in fact to any reflexive game on a rectangular grid where each button affects only some or all of the four neighbouring lights, due to the fact that the grid can be given a checkerboard colouring. Suppose you push all the buttons. This changes every light except those that are affected by an odd number of other buttons. In a symmetric game (and non-symmetric bipartite games) this will leave an even number of lights unchanged, and this is used in the last step of the proof instead of applying the lemma I used.
Corollary:
Every quiet pattern in a symmetric reflexive game has an even number of buttons.
This follows directly from the solvability check of the position with all lights
on. (Note - In proof 1 we proved this first in order to prove the theorem. In proof
2 it is done the other way round, the theorem proves this result.)
The Lights Out Deluxe has a variation of the game were you are only allowed to press lit buttons. This makes things a little more complicated.
Theorem 2:
A standard Lights Out game on a rectangular grid which starts completely lit can
be switched off by pressing only lit buttons. [Er]
Proof of theorem 2:
From theorem 1 it is clear that the pattern with all lights on can be solved. It remains only to be shown that the button presses in this solution can be done in such an order that only lit buttons are pressed. Imagine the grid of buttons marked like a chess board, alternating black and white. First press all the buttons in the solution that are marked black, and then all the buttons that are marked white. Pressing a black button will never change any other black one (because no two black ones are adjacent), so when pressing the black buttons you will always be pressing lit buttons. After pressing the remaining white buttons they will all be off, so before you press them they must have been alight. This is therefore a solution (only one of many).
Q.E.D.
In fact, any pattern that can be solved normally can also be solved by pressing only lit buttons. It may take a few extra button presses however.
Theorem 3:
Any solvable pattern of any reflexive symmetric game can be solved by pressing
only lit buttons.
This is actually remarkably hard to prove. Several of my earlier attempts at proof had holes in them, so I hope that the proof below holds water.
Proof of theorem 3:
Consider the button pattern that solves the position if it were a regular game. If any of the buttons in the solution are lit, then press them. Eventually you reach a position in which all remaining buttons of the solution are unlit. If any such button b is adjacent to a light l then press l,b,l. This has the same effect as pressing b alone would have had if it were allowed. Thus we can assume we arrive at a position in which all the remaining buttons of the solution are unlit as well as all their neighbours.If at this point there are no lights left on, then we are finished. Suppose therefore that there are still lights left on. We can move a light around through an unlit area in the following manner. Suppose there is a path of buttons, a0, a1, ..., ak where a0 is lit, a1, ..., ak are unlit. We can assume that this is the shortest such path between a0 and ak, so that each ai is adjacent to ai-1 and ai+1 but not to any others in the path. We can press the move sequence a0, a1, ..., ak-1 to light up ak. We can later undo this by pressing the sequence ak-2,ak-1,ak-2, ak-3,ak-2,ak-3, ..., a1,a2,a1, a0,a1. In this way we can bring a light to where it is needed, to allow a move sequence to be performed.
If b is one of the (unlit) buttons of the solution then we know that it has at least one neighbouring button c also part of the solution. If there weren't such a neighbour then pressing all the buttons in the solution would make button b lit, contrary to the fact that it is a solution. So we have two adjacent unlit buttons b and c which are part of the solution.
It must be possible to bring a light to some neighbour of b or c in such a way that neither b nor c is changed, as the shortest path from a light to b or c must pass some neighbour of b or c first. Let n be that neighbour. There are now two cases to consider - n is a neighbour of only one of b or c, or n is a neighbour of both b and c.
Case 1: n is a neighbour of b, but not of c. Let l be the button that was pressed to light up n (so it is a neighbour of n, and is currently unlit). Do the move sequence n b c b l n b. In effect this presses b and c, and undoes the previous press of l. Bring the light of l back to where it came from, and the net effect is that only b and c have been pressed as required. Clearly if n is a neighbour of c but not of b, then the same method applies with b and c interchanged.
Before we do the second case, consider what would happen if b and c had exactly the same neighbours. Pressing both b and c would then leave all their neighbours and themselves unaffected. Thus it is a quiet pattern, and the button presses b and c need not be part of the solution. We can therefore assume that there is at least one button, say m, that is a neighbour of c but not of b (or vice versa).
Case 2: n is a neighbour of both b and c. Let l be the button that was pressed to light up n (so it is a neighbour of n, and is currently unlit). We also have m which is a neighbour of c but not of b. If m and n are not themselves neighbours, then do nlcmcbcncmc, but if n and m are adjacent then do nlbmnmc. In either case the effect is that this presses b and c, and undoes the previous press of l. Bring the light of l back to where it came from, and the net effect is that only b and c have been pressed as required. Clearly if m is a neighbour of b but not of c, then the same method applies with b and c interchanged.
The previous argument has shown that in a lit-only game the buttons that are part of the regular solution to a position can be pressed in some way regardless of whether they are lit or not. Thus the position can still be solved in the lit-only game provided it is solvable in the normal game.
Q.E.D.
Although this theorem shows regular solvable positions can always be solved in the lit-only game, it is not guaranteed that it can be done in the same (minimal) number of moves. In other words there may be buttons that need to be pressed twice. The following theorem goes some way to characterize which positions can be solved as lit-only games without extra moves.
Theorem 4:
Given a solvable position in a reflexive symmetric game for which there is a
lit-only solution that has the same number of moves as the regular solution.
The buttons of the solution consists of one or more connected clumps which each
satisfy the following two conditions:
1. Some button in the clump is lit.
2. The number of unlit buttons in the clump has the same parity as the number
of neighbouring pairs of buttons.
Proof:
This is fairly trivial. Eventually some button in the clump will be pressed, so if there aren't any extraneous moves at least one of its buttons must be lit. If you consider playing the solution in reverse, starting from the solved position, then it is easy to verify that any move in the solution always preserves the parity condition. It follows that the parity condition is a necessary condition for a position to be solvable in the lit-only game.
Q.E.D.
On the right you see an example of a position for which the lit-only solution
uses exactly the same button presses as the regular solution. The twelve buttons
that form the solution fall apart into three clumps:
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 connected clumps of 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 clump
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.
This is yet another variation that is found in the Lights Out Deluxe. Here you must alternately press lit and unlit buttons to solve it. This is quite a bit more difficult to solve than the lit-only game.
The first thing to realise with the Toggle game is that the last move must always be pressing a lit button to switch it off. Therefore, if the regular solution has an even number of moves, the first move in the Toggle game is pressing an unlit button, and if the solution has an odd number of moves it starts by pressing a lit button.
Theorem 5:
Suppose a solvable position in a symmetric reflexive game requires an even number
of button presses, and that the position is solvable in the Toggle game. Consider
for a moment only those buttons that are part of the regular solution. These satisfy
the following parity conditions:
1. The number of currently lit buttons is even.
2. The number of the currently unlit buttons is even also.
Note this is about the state of all the buttons at one moment, not the state of
the individual buttons at the moment you press them during the solving of the position.
3. Half the total number of solution buttons plus the number of neighbouring
pairs amongst them, is also even.
On the right you see an example of a position solvable in the toggle game. There
are six buttons in the solution, two lit and four unlit. There are three adjacent
pairs of buttons, half the number of buttons is also three, and together this makes
six. All three numbers are even.
Proof:
The solved position clearly satisfies the parity conditions since zero is even.
Let's start with any position that satisfies the parity conditions, and then press an unlit button that is not already one of the solution buttons. As it is unlit, it must have an even number of neighbours (possibly none) that are part of the regular solution. The change in state of these neighbours will therefore not affect conditions 1 and 2, nor the parity of the number of neighbouring pairs. The button itself does however change things, namely it either adds one (now lit) button to the solution.
Now we press a lit button that is not yet one of the solution buttons. As it is lit, it must have an odd number of neighbours that are part of the regular solution already. The change in state of these neighbours will therefore change the parity of the number of lit buttons as well as the number of unlit solution buttons, and also the parity of the number of neighbouring pairs. The button itself also changes, namely adds one (now unlit) button to the solution.
Combining all these changes together, we see that the number of lit buttons was incremented by the first press, and then the neighbours of the second button press changed the parity again, so condition 1 still holds. Similarly for condition 2. The total number of solution buttons was increased by two, and an odd number of new neighbouring pairs was formed, so condition 3 also still holds.
It is easy to check the conditions still hold if one or both the buttons are already part of the regular solution.
Q.E.D.
The reverse of the theorem is also true, at least for games that don't have too few buttons. I will describe a solving strategy below. It is useful however to first find some move sequences which have no effect but which involve more lit buttons than unlit buttons or vice versa.
Suppose you have two adjacent buttons, a and b, where a is lit and b is unlit. The sequence baba presses four unlit buttons but does not have any effect on the lights. If you have three adjacent buttons a,b,c (c is not adjacent to a) all unlit then the sequence acbacb also involves four more unlit presses than lit ones. The sequence bcabca works if all three buttons are lit. Sequences such as these allow you some leeway with the alternating lit/unlit presses, because you can generate a surplus of one or the other.
Note however that all of these have a surplus of four. It is in fact impossible to have a sequence that generates a surplus of two in a symmetric reflexive game.
Theorem 6:
In a reflexive symmetric game, any move sequence in which every button involved
is pressed an even number of times, the number of lit button presses and the
number of unlit button presses both have the same parity as half the total number
of button presses.
Proof:
This is clearly true for a sequence where each button is pressed an even number of in succession without being interrupted by other moves. Suppose it is true for some move sequence, then it is also true if a pair of successive moves in that sequence are interchanged. This is obvious if the swap involves buttons that do not influence each other, but equally true when they do. The only change is that the two moves change from lit to unlit or vice versa. The result then follows since any move sequence can be rearranged by such swaps to that sequence where each button is pressed an even number of times in succession.
Q.E.D.
This theorem shows that a surplus of 2 is not possible because then the number of lit and unlit buttons would be say k+1 and k-1, the number of button presses is 2k, and then the theorem requires k+1 and k-1 to have the same parity as k. This is clearly not the case.
The solving strategy is now as follows. Find out the buttons in the regular solution to the position, and then solve the toggle game as far as possible, pressing only the buttons in that regular solution. Eventually there is no direct move left, either because it is solved or because there are no buttons in the regular solution that have the correct state. Thus you must have an odd number of buttons in regular solution, all unlit, or an even number, all lit. The first case is impossible since each button must have an odd number of neighbours in the solution for it to be unlit, and this contradicts lemma 1.
So you must reach a position with only lit buttons in the regular solution, and the next move is pressing an unlit button. If any two buttons in the regular solution are adjacent, then you can change them if you first press any unlit button not adjacent to them (*) so that you can now do the right kind of moves to press the adjacent buttons. Then continue on as normal.
You may end up with an even number of lit buttons to press which are all separated. From theorem 5, half the number of buttons is even so the number of buttons must be a multiple of four. Now the move sequences that generate surplus moves come in handy. If a,b,c are adjacent unlit buttons, then the sequence axcxbxaxcb will do the trick where each x is a press of a lit solution button. If you cannot find three adjacent unlit buttons, then you can usually (**) make room by 'moving' a solution button (i.e. switch one new button on, switch a solution button off).
The above strategy is not a rigorous proof of the converse of theorem 5. In other words it does not prove that all positions that satisfy the parity restrictions in the theorem are solvable in the Toggle game. This is because there are assumptions made at * and ** that certain buttons can be found. In small games this is not necessarily the case, but I do think the converse of theorem 5 holds for all games as long as there remain some unlit buttons.
Let's consider the matrix of the Mini Lights Out:
1101100000001000 1110010000000100 0111001000000010 1011000100000001 1000110110000000 0100111001000000 0010011100100000 0001101100010000 0000100011011000 0000010011100100 0000001001110010 0000000110110001 1000000010001101 0100000001001110 0010000000100111 0001000000011011
This matrix A is a little bit special because A2=I. This means that A=A-1, i.e. that the matrix is its own inverse. In this case you can change any single light by pressing those lights that would be changed if you pressed it, in other words press the light itself and its four neighbours.
The Orbix (game type 1) has the same property, that A2=I. To change a single light press those lights that would be changed if you pressed it, in other words just press its five neighbours.
Both puzzles have a relatively small number of lights, and a lot of symmetry. There are 60 ways to rotate the Orbix. It clearly should not matter which way the puzzle is held, so this means that the 12 buttons should give the same kind of light pattern, and that the light pattern should have 5-fold symmetry. This 5-fold symmetry around a light/button gives rise to 4 orbits - the light itself, the ring of 5 adjacent lights, the opposite light, and the ring of the remaining 5 lights. If you mark in the matrix of the game which orbit each element represents, you will find that when you evaluate the square of the matrix every term in a non-diagonal entry occurs twice, so modulo 2 there will automatically be only zeroes in all non-diagonal entries. Thus the symmetry of the Orbix forces A2=I or A2=O. In fact, we have A2=I if and only if the light pattern of a move changes an odd number of lights.
The Mini Lights Out also has a lot of symmetry. You can move the top row to the bottom or vice versa, or the left column to the right hand side and vice versa, and you can rotate the board a quarter turn. This gives 16·4=64 symmetries. As with the Orbix, if you insist that the lights affected by a button also follow these symmetries, then they force A2=I or A2=O, and again we have A2=I if and only if the light pattern of a move changes an odd number of lights.
Let's now examine when a normal lights out game has quiet patterns or not, i.e. when the matrix if the game is invertible or not. There is a way to determine whether a square matrix is invertible without actually trying to invert it, and that is by determining a number called the determinant of the matrix. If this number is 0 then it is not invertible.
One way of calculating the determinant of an n×n matrix {aij}
is as follows. Let p be a permutation of the numbers 1 to n (i.e. p is
an element of the symmetric group Sn). Calculate the product
Before going on, I shall prove a few useful properties of the determinant.
Property 1: If two rows of a matrix are swapped, the determinant changes sign, but not its magnitude.
Proof: Let x and y be the numbers of the rows that we will swap, and let p be a permutation. Define a permutation q as q(x)=p(y), q(y)=p(x), and q(i)=p(i) when i is not equal to x or y. Then q is clearly also a permutation, as it is simply the transposition (x y) composed with p, and furthermore q will be of opposite parity to p. As p ranges over all possible permutations, so does q, and vice versa. Consider one of the terms in the determinant calculation:
sgn(p)·a1 p(1)·a2 p(2)·...·ax p(x)·...·ay p(y)·...·an p(n)
The row swap turns it into:
sgn(p)·a1 p(1)·a2 p(2)·...·ay p(x)·...·ax p(y)·...·an p(n)
This is equal to:
-sgn(q)·a1 q(1)·a2 q(2)·...·ay q(y)·...·ax q(x)·...·an q(n)
Each term in the determinant after the swap has become the negation of some term before the swap. The determinant is therefore the same apart from the changed sign.
Property 2: If a matrix has two equal rows, then the determinant is zero.
Proof: Swap the two equal rows. According to property 1, the determinant changes sign. The matrix is unchanged by the swap, so the determinant cannot have changed either. Therefore the determinant is 0.
Property 3: If we multiply a whole row of a matrix by some number r, then the determinant is also multiplied by r.
Proof: Each term in the determinant calculation will have exactly one factor from that row, so each term is multiplied by r. The determinant is then also multiplied by r.
Property 4: If a row of a matrix has only zeroes, then the determinant is zero.
Proof: Each term in the determinant calculation will have one factor from the zero row, so each term is 0. The determinant is then also 0. Alternatively, multiply the zero row by r. According to property 3, the determinant is also multiplied by r, but as the matrix has not been changed, the determinant is not changed by multiplication by any r. Therefore the determinant is 0.
Property 5: If a multiple of one row of the matrix is added to another, the determinant remains the same.
Proof: Lets suppose that we add r times row 2 to row 1. Consider one of the terms in the determinant calculation:sgn(p)·a1 p(1)·a2 p(2)·...·an p(n),
After the row addition this term becomes:sgn(p)·(a1 p(1)+r·a2 p(1))·a2 p(2)·...·an p(n),
This is equal to:sgn(p)·a1 p(1)·a2 p(2)·...·an p(n) +r·sgn(p)·a2 p(1)·a2 p(2)·...·an p(n),
The first term summed over p is just the original determinant. The other term summed over p can be seen as (r times) the determinant of a matrix with the first and second row equal. This is zero by property 2, so the value of the determinant has not changed.
Armed with these properties we can see why a matrix that is invertible must have non zero determinant. If we use Gaussian elimination then (from properties 1, 3, 5) the determinant of a matrix will either remain zero throughout, or remain non-zero throughout. A non-invertible matrix results in a zero row, so (by property 4) its determinant is zero. An invertible matrix on the other hand results in the identity matrix, which has determinant 1 (i.e. non-zero). This proves the following:
Corollary: The determinant of a matrix is non-zero if, and only if, the matrix has an inverse.
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:
| 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
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:
| 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 non-zero term to the determinant. Our aim throughout all of this is to determine whether the determinant is 0, but as we are working modulo 2, we really only need to see whether the number of the non-zero terms is even or odd. Therefore, we just need to find out how many ways there are to tile the game board with dominoes and monominoes. If that number is odd then the matrix is invertible, and if it is even then it is not invertible. This proves the following:
Theorem 7: If standard Lights Out is played on a grid-like board, then all light patterns 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×(n-1) rectangle in any one of
R(1,n-1) ways. If we start with a domino on he other hand, then the remainder is a 1×(n-2)
rectangle that can be filled in R(1,n-2) ways. Therefore, R(1,n)=R(1,n-1)+R(1,n-2).
It is trivial to check that R(1,1)=1 and R(1,2)=2, we find that R(1,n) are the Fibonacci numbers,
1, 2, 3, 5, 8, 13, 21, ...
It is easily checked that this is even exactly when n=2 modulo 3. In other
words, rectangles of size 1×(3k+2) have quiet patterns, whereas other 1×n
rectangles have none. The quiet pattern looks like this:
| X | X | X | X | X | X | X | X | X | X |
Example 2: 2×n: Suppose we have a domino/monomino tiling of this board.
If it is asymmetric along its long axis, then we can skip it because it will
be cancelled out by its mirror image. After all, we only need to know whether
the total number of tilings is even or odd. Therefore we only need to look at
tilings that are symmetric about the long axis. In the tilings that remain,
every monomino in the top row has a matching monomino in the bottom row.
We can now do a similar trick, not by pairing a tiling with its mirror
image, but another kind of pairing. Given a pattern, exchange every vertical
domino by two monominoes, and vice versa. Two tilings related to each other by
such an exchange can be skipped. This leaves only tilings which have no monominoes
and no vertical dominoes, i.e. only tilings with horizontal dominoes.
If n is even, then there is exactly one such tiling left. Therefore, R(2,2k)
is odd, and in any 2×2k rectangle all light patterns are solvable.
If n is odd, then there are no tilings with only horizontal dominos, so
then R(2,2k+1) is even, and there must be quiet patterns, such as the one shown
below.
| X | X | X | X | X | X | |||||
| X | X | X | X | X | X |
Example 3: 5×n: Consider a horizontal line through the middle of the board. Like before, any tiling that is not symmetric about this line can - together with its mirror image - be ignored, since we only need the parity of the number of tilings. We only need symmetric tilings. As the line of symmetry goes through a row of squares, there can be no vertical dominoes on this row (that would be asymmetric). The row is then only monominoes and horizontal dominoes, and therefore the symmetric tilings can be split into a tiling of the top 2×n board, a tiling of the 1×n middle row, and a tiling of the bottom 2×n board that is a mirror image of the top part. The number of these tilings is therefore R(5,n)=R(2,n)·R(1,n). For this to be odd both factors must be odd, so from the previous examples we see that n must be even and also not 2 modulo 3. The number of tilings is therefore odd exactly when n is 0 or 4 modulo 6. In other words all light patterns in 5×6k or 5×(6k+4) rectangles are solvable, but on other 5×n rectangles there are quiet patterns.
| 5 × 2k+1 | 5 × 3k+2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
We can generalise the last example a bit to get:
Lemma: On an (2k+1)×n rectangle there are quiet patterns when
n is 2 modulo 3. If n is not 2 modulo 3, then there are quiet patterns if and
only if there are quiet patterns on the k×n rectangle.
Proof: The same reasoning as in the previous example shows that
R(2k+1,n) = R(k,n)·R(1,n). If n is 2 modulo 3 then R(1,n) is even and
then so is R(2k+1,n). This gives the patterns below left. Otherwise, R(2k+1,n)
is even exactly when R(k,n) is even. This case leads to the kind of pattern
below right - a quiet pattern on a k×n rectangle is used in the top
half and repeated in mirror image in the bottom half.
| 2k+1 × 3k+2 | 2k+1 × n, given a pattern on k×n | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
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 Sn be the number of 2×n tilings without a monomino on the
bottom row. The bottom left corner has a domino in it, either vertical or
horizontal. If it is vertical, then there are Sn-1 ways of completing
the remaining 2×(n-1) rectangle. If it horizontal with a horizontal domino
above it then there are Sn-2 ways to complete the tiling. The final
possibility is a horizontal domino with a monomino above it. Now the next monomino
in the top row can be immediately adjacent to the first (giving Sn-2
completions) or there may be one horizontal domino first (giving Sn-4
completions) or two (Sn-6), three (Sn-8) etc. until there
is no more room left. We therefore arrive at:
To eliminate the tail of this sum, we calculate Sn-Sn-2:
so that (at least for n>3)
It is easy to find check by hand that S0 to S3 are all odd.
By repeatedly plugging this into the equation it becomes clear that Sn is
even exactly when n is 4 modulo 5 (i.e. when n=4, 9, 14 etc.).
We already found quiet patterns for n=4, and by repeating them we can find
quiet patterns for all those 4×(5k+4) rectangles. All other 4×n
rectangles have no quiet patterns.
| 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
If k is a root of that polynomial, then we know that
Note that since
There are n roots to the characteristic polynomial, though some may be repeated. For each root, i.e. for each eigenvalue we have an eigenvector. If the eigenvalue is a repeated root of the polynomial, then there will be just as many independent eigenvectors associated with it as the number of times that root is repeated. This means that there are in fact exactly n independent column eigenvectors vi, and similarly exactly n row eigenvectors wi.
An interesting fact about the characteristic polynomial c(x) of matrix A
is that A itself satisfies the polynomial, i.e. c(A) is the zero
matrix. The reason for this is that
Let's now look at a special type of matrix, namely the square matrix An which has aij=1 whenever i=j-1 or j+1, but has zeroes everywhere else. In other words it has ones only at entries adjacent to the diagonal. This type of matrix will be useful later on.
For example, A5 is:
01000 10100 01010 00101 00010
The characteristic polynomial cn(x) for matrix An is fairly easy to find as there are so many zeroes. The only non-zero terms in the determinant must have a permutation p such that p(1)=1 or 2, and if p(1)=2 then we must have p(2)=1. You can see this in this example for A5:
| xI-A5 | p(1)=1 | p(1)=3, p(2)=1 | |
| Matrix with p marked | x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x |
x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x |
x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x -1 0 0 0 -1 x |
| Determinant terms | x c4(x) | -1·-1·c3(x) |
This gives us the recursive rule
For the small cases we find that
The polynomials in this sequence are similar to Fibonacci polynomials. The
Fibonacci polynomials are defined by:
f0(x)=0
f1(x)=1
fn(x)=x fn-1(x) + fn-2(x)
If we are working modulo 2, then addition and subtraction are the same thing
(since -1=1 modulo 2) and we see that
Before moving on, we also need another kind of matrix, namely
We can now put these special matrices to use. Consider a standard Lights Out game on a rectangular board. Except for light chasing, in all the previous sections we never used the specific shape of the board to simplify matters. We just considered each light/button, and used a whole row or column in a large square matrix for each of them. Light patterns or button patterns on a board were then long vectors without any board shape context. This time we use rectangular matrices of the same shape and size as the board. Such a matrix can represent either a light pattern or a button pattern.
Let X be an m×n rectangular matrix, representing a pattern of button presses on the m×n board. We would like to have some expression for the effect of this pattern on the lights, and the special matrices Am and Bn will be used for that.
Consider XBn.
This is still a rectangular m×n matrix, and you will find that every
non-zero entry in X affects the same entry in the result as well as those
above and below it. It is as if XBn is the result of the button
presses if only vertical neighbours (and the button itself) were affected
by each button press.
Similarly, now consider AmX.
Again this is an m×n rectangular matrix, but now each non-zero entry
in X affects only the entries to the left and right of it in the result.
Thus AmX is the result of the button presses is only the horizontal
neighbours (and not the button itself) were affected by each button press.
Putting these two together we find that
Of course the question arises of how to solve X, but I will not discuss that here as the previous methods work well enough for rectangular boards, especially if light chasing is done to reduce the size of the matrices. A more interesting question that can be answered from this equation is, when does X have a unique solution?
Suppose AX+XB=C has two solutions for X, say X1
and X2. Let Y be X1-X2,
i.e. the button pattern achieved by combining X1 and
X2. This should have no effect on the lights, and indeed:
If X1 and X2 are distinct, then Y
is a non-trivial quiet pattern. Therefore if there are no quiet patterns other
than the trivial pattern (no buttons pressed), then all solutions are unique.
Conversely, if there is a quiet pattern, then any solution X1
to light pattern C will when, combined with the quiet pattern Y,
give another solution
Now the search for quiet patterns has been reduced to finding solutions
for Y of matrix equation
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
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
Theorem 8: A Lights Out game on an m×n grid has quiet patterns
exactly when the polynomials cm(x) and cn(-x-1) have
a common factor.
Sketch of Proof: The game has a quiet pattern if and only if
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 equivalent) way to prove it for the standard two state game can be found in [Go1]+[Go2], and a proof for the general case is in [Hu].
Here are the first few of these polynomials, factorised. I have not reduced them modulo 2, but if you were to do so they would often factorise further.
| n | char[A](x)=cn(x) | char[B](-x)=cn(-1-x) | ||||
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||
| 1 | x | x+1 | ||||
| 2 | x2-1 | = | (x+1)(x-1) | x2-2x | = | x(x-2) |
| 3 | x3-2x | = | x(x2-2) | x3-3x2+x+1 | = | (x-1)(x2-2x-1) |
| 4 | x4-3x2+1 | = | (x2-x-1)(x2+x-1) | x4-4x3+3x2+2x-1 | = | (x2-x-1)(x2-3x+1) |
| 5 | x5-4x3+3x | = | x(x-1)2(x2+2x+3) | x5-5x4+6x3+2x2-4x | = | x(x-1)(x-2)(x2-2x-2) |
| 6 | x6-5x4+6x2-1 | = | (x3-x2-2x+1)(x3+x2-2x-1) | x6-6x5+10x4-9x2+2x+1 | = | (x3-4x2+3x+1)(x3-2x2-x+1) |
| 7 | x7-6x5+10x3-4x | = | x(x2-2)(x4-4x2+2) | x7-7x6+15x5-5x4-15x3+9x2+3x-1 | = | (x-1)(x2-2x-1)(x4-4x3+2x2+4x-1) |
The m=n=5 case has a common factor of x. This means that we can construct a quiet pattern simply by multiplying the row and column eigenvectors with eigenvalue 0 as explained before.
1 1 -1 0 1 -1 0 0 0 0 0 0 -1 . 1 -1 0 1 -1 = -1 1 0 -1 1 0 0 0 0 0 0 1 1 -1 0 1 -1
If we instead use the common factor of x-1 and multiply the eigenvectors with eigenvalue 1, then we get the same pattern but rotated. Note that we did not reduce modulo 2, so this same pattern works with any number of light states, such as the Lights Out 2000 with 3 states.
The m=n=4 case also has a common factor, namely x2-x-1. There must therefore be a quiet pattern, again applicable regardless of the number of states of the lights. The shared factor is of degree 2 so we cannot simply multiply out the eigenvectors, but the quiet pattern is easily found by a little trial and error.
1 0 0 1 -1 0 0 1 . 0 1 -1 0 = -1 0 0 1 0 -1 -1 0 0 1 1 0 0 -1 -1 0 0 -1 1 0
I have also shown a decomposition of that matrix into a product of two rectangular matrices. The polynomial factor had degree 2, so the rectangular matrices the pattern decomposes into have width resp. height 2. It is difficult to explain clearly why this is so. The eigenvalues used here involve square roots (since they are roots of a quadratic), and so the eigenvectors would also involve square roots. By taking linear combinations of those vectors we can get two other vectors that span the same space but without the square roots. Those two vectors are used in the columns or rows of the matrices.
In [Hu] the above 5×5 and 4×4 patterns are given. It is proved there that these are the only square grids that always have a general solution, in other words, char[An](x) and char[Bn](-x) only have a common factor when n=4 or 5. It is also shown in that paper that for any size square Lights Out board (greater than 1×1) there is a prime number p such that the game with p states for each light has a quiet pattern. In other words, for any n>1 there is a prime p such that char[An](x) and char[Bn](-x) have a common factor modulo p. For example in the 6×6 case with p=5 we see in the table of polynomials above that the factors x3+x2-2x-1 in the left column is equal to x3-4x2+3x+1 in the right column modulo 5.
I have calculated the rank of the matrix A for the standard game on a rectangular grid m×n with 1<m,n<26. The table below shows m·n-rank, which is the number of generators of the quiet patterns. For example at 11×5 it shows 4, meaning that the rank is 55-4=51, and that there are 24=16 quiet patterns (of which one is the trivial pattern).
| 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</ |