The game

We are given a finite graph, with a light at each vertex that can be on or off. Pressing the button at a vertex switches the state of the lights at that vertex and its neighbours. The question is whether all lights can be switched off given an arbitrary starting position.

This is really the question whether the matrix I+A (where A is the adjacency matrix of the graph) has full 2-rank. The cases of rectangular grids with or without boundary are about the graphs that are the direct product of two paths ("Lights Out") or two cycles ("Button Madness"), respectively. Other shapes occur. The XL-25 used a knight's jump pattern.

Switching all lights

The row space of any symmetric binary matrix contains the diagonal. (Proof: if A is the matrix, with diagonal d, and x is orthogonal to the rows of A, so that Ax = 0, then also x'Ax = 0. But in that latter equation nondiagonal terms cancel by symmetry, and d'x = 0.)

It follows that this game played on any graph allows switching all lights.

(This is often attributed to Sutner (1989). An earlier source is Bagchi & Narasimha Sastry (1987), Theorem 3, who write "This result should be of independent interest because of its striking generality". This is Problem 798, Nieuw Archief voor Wiskunde 9 (1991) 117-118, solved by Wilbrink & Blokhuis. Also problem 10197, Am. Math. Monthly 100 (1993) 806-807.)

Tilings

Arbitrary patterns are solvable when I+A is nonsingular mod 2, i.e., when its determinant is nonzero mod 2, i.e., when the number of tilings of the graph by singletons and adjacent pairs is odd. (In the expansion of the determinant some terms are zero, and some terms cancel in pairs because of symmetry, and these are the terms left.)

Perfect parity patterns

A parity pattern is a binary pattern such that each position is the (mod 2) sum of its neighbours. That is, is a vector in the kernel of I+A. In the case of a rectangular grid with boundary, a parity pattern is called perfect if it does not have a row or column that consists of all 0's. Knuth's TAOCP 7.1.3 (Exercises 190-194) has a discussion of parity patterns that translates into a discussion of Button Madness and Lights Out.

A description of the commercial (5x5) versions is given on Jaap's puzzle page, and the very nice companion page gives related mathematics.

As it turns out, this game is quite popular among mathematicians. Some links:

• Bhaskar Bagchi & N. S. Narasimha Sastry, Even order inversive planes, generalized quadrangles and codes, Geometriae Dedicata 22 (1987) 137-147.
• K. Sutner, Linear cellular automata and the Garden-of-Eden, Math. Intelligencer 11 (2) (1989) 49–53.
• John Goldwasser, W. F. Klostermeyer, G. E. Trapp & C. Q. Zhang, Setting switches in a grid, Technical Report TR-95-20, Dept. of Statistics and Computer Science, West Virginia University. preprint,
• Y. Caro, Simple proofs to three parity theorems, Ars Combin. 42 (1996) 175-180.
• R. Barua & S. Ramakrishnan, σ-game, σ+-game, and two-dimensional cellular automata. Theor. Comput. Sci. 154 (1996) 349-366.
• J. Goldwasser, W. F. Klostermeyer & G. E. Trapp, Characterizing switch-setting problems, Linear and Multilinear Algebra 43 (1997) 121-135. preprint.
• J. Goldwasser & W. F. Klostermeyer, Maximization versions of "Lights Out" games in grids and graphs, Congressus Numerantium 126 (1997) 99-111. preprint.
• Marlow Anderson & Todd Feil, Turning Lights Out with Linear Algebra, Mathematics Magazine 71 (1998) 300-303.
• R. Cowen, S. H. Hechler, J. W. Kennedy & A. Ryba, Inversion and neighborhood inversion in graphs, Graph Theory Notes New York 37 (1999) 37-41.
• M. M. Conlon, M. Falidas, M. J. Forde, J. W. Kennedy, S. McIlwaine & J. Stern, Inversion numbers of graphs, Graph Theory Notes New York 37 (1999) 42-48.
• Klaus Sutner, σ-Automata and Chebyshev-Polynomials, Theor. Comput. Sci. 230 (2000) 49-73. preprint.
• William Klostermeyer, Lights Out!: A survey of parity domination in grid graphs, 2001. preprint.
• Henrik Eriksson, Kimmo Eriksson & Jonas Sjöstrand, Note on the Lamp Lighting Problem, Advances in Applied Math. 27 (2001) 357-366. preprint.
• John Goldwasser, William Klostermeyer & Henry Ware, Fibonacci Polynomials and Parity Domination in Grid Graphs, Graphs and Combinatorics 18 (2002) 271-283. preprint.
• Sylvain Gravier, Medhi Mhalla & Eric Tannier, On a modular domination game, Les cahiers du laboratoire Leibniz 39, Jan. 2002. preprint.
• Markus Hunziker, António Machiavelo & Jihun Park, Chebyshev polynomials over finite fields and two-dimensional additive cellular automata, Theor. Comput. Sci. 320 (2004) 465-483. preprint.
• D. E. Knuth, TAOCP 7.1.3 preprint, Exercises 190-194.
• Wolfram,

This is the case without boundary (that is, on a torus). There may be some ambiguity about the definition of the graph when m or n are small. Here I'll take the point of view that a point and its 4 neighbours (up, down, left, right) are flipped, and if e.g. m=2 then up and down coincide, so that that neighbour is flipped twice and does not change. (Thus, the game on a 2×n board is the disjoint sum of two copies of the 1×n board.)

A table of codimensions of I+A for the m × n grid without boundary (i.e., on a torus) for m,n ranging between 1 and 30.

``` 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4
2 4 4 4 2 6 2 4 4 4 2 6 2 4 4 4 2 6 2 4 4 4 2 6 2 4 4 4 2 6
0 0 4 0 0 8 0 0 4 0 0 8 0 0 4 0 0 8 0 0 4 0 0 8 0 0 4 0 0 8
0 0 2 0 8 2 0 0 2 8 0 2 0 010 0 0 2 0 8 2 0 0 2 8 0 2 0 010
2 4 6 8 2 8 2 8 6 4 212 2 4 6 8 2 8 2 8 6 4 212 2 4 6 8 2 8
0 0 2 0 0 2 0 014 0 0 2 0 0 2 0 014 0 0 2 0 0 2 0 014 0 0 2
0 0 4 0 0 8 0 0 4 0 016 0 0 4 0 0 8 0 0 4 0 016 0 0 4 0 0 8
2 4 4 4 2 614 4 4 4 2 6 216 4 4 2 6 2 416 4 2 6 2 4 416 2 6
0 0 4 0 8 4 0 0 416 0 4 0 012 0 0 4 016 4 0 0 4 8 0 4 0 020
0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
2 4 6 8 212 216 6 4 216 2 4 616 212 2 8 6 4 224 2 4 6 8 212
0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
0 0 4 0 0 4 0 016 0 0 4 0 0 4 0 028 0 0 4 0 0 4 0 016 0 0 4
2 4 4 410 6 2 4 412 2 6 2 412 418 6 212 4 4 2 610 4 4 4 214
0 0 4 0 0 8 0 0 4 0 016 0 0 4 0 0 8 0 0 4 0 032 0 0 4 0 0 8
0 0 2 0 0 2 0 0 2 0 0 2 0 018 016 2 0 0 2 0 0 2 0 0 2 0 018
2 4 6 8 2 814 8 6 4 212 228 6 8 2 8 2 818 4 212 2 4 632 2 8
0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
0 0 4 0 8 8 0 0 416 0 8 0 012 0 0 8 032 4 0 0 8 8 0 4 0 024
2 4 4 4 2 6 2 416 4 2 6 2 4 4 4 218 2 4 4 4 2 6 2 416 4 2 6
0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4
0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
2 4 6 8 212 216 6 4 224 2 4 632 212 2 8 6 4 232 2 4 6 8 212
0 0 2 0 8 2 0 0 2 8 0 2 0 010 0 0 2 0 8 2 0 0 2 8 0 2 0 010
0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4 0 0 4
2 4 4 4 2 614 4 4 4 2 6 216 4 4 2 6 2 416 4 2 6 2 4 416 2 6
0 0 4 0 0 8 0 016 0 0 8 0 0 4 0 032 0 0 4 0 0 8 0 016 0 0 8
0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2 0 0 2
2 4 6 810 8 2 8 620 212 2 414 818 8 224 6 4 21210 4 6 8 224
```
It is always possible to find a coset representative with support contained in two successive rows or columns, so codimensions will lie between 0 and min(2m,2n).

Propagation is via (v,w) -> (w+v+v+v+,v), which is linear and 1-1, so the rows and columns will be periodic. If d is the order of this transformation T (acting on pairs of vectors of length n), then column n has period d, and for n a multiple of d the full codimension occurs. Since T is element of the symplectic group, we have good information on its order - see also below. (The transformation here is not the same as that in the next section: the v and v+ involve cyclic shifts here.)

More generally, the codimension is nonzero precisely when Tn−I is singular. But then it will be nonzero also for multiples of n.

Period lengths:
 0 1 2 3 4 5 6 7 8 9 0-9 322–1 322–1 62(22–1) 62(22–1) 1524–1 1222(22–1) 923+1 1222(22–1) 422(26–1)/3 10-19 302(24–1) 933(25–1) 2423(22–1) 6326–1 182(23+1) 5102(28–1) 2423(22–1) 25528–1 8422(26–1)/3 51329+1 20-29 6022(24–1) 11702(212–1)/7 1866(25–1) 61413(211–1) 4824(22–1) 30753(210+1) 1262(26–1) 30666(29–1) 3622(23+1) 98313(214+1)/5 30-39 102022(28–1) 1023210–1 4824(22–1) 20462(210–1) 5102(28–1) 4095212–1 16823(26–1)/3 35917(29+1) 10262(29+1) 81902(212–1) 40-49 12023(24–1) 1048575220–1 234022(212–1)/7 16383214–1 37212(25–1) 464102.17(212–1)/3 122826(211–1) 251658213(223–1) 9625(22–1) 2097153221+1 50-59 61506(210+1) 1310702(216–1) 25222(26–1) 2013265953(226+1) 613212(29–1) 25575(220–1)/41 7223(23+1) 5242862(218–1) 196626(214+1)/5 16106127333(229–1) 60-69 204023(28–1) 1073741823230–1 20462(210–1) 81902(212–1) 9625(22–1) 4095212–1 409222(210–1) 8589934593233+1 102022(28–1) 83886062(222–1) 70-79 81902(212–1) 1030792151013(235–1) 33624(26–1)/3 262143218–1 718214(29+1) 64487485506(210+1)(220+1) 205222(29+1) 1073741823230–1 1638022(212–1) 549755813889239+1 80-89 24024(24–1) 8053063626(227–1) 20971502(220–1) 65970697666533(241-1) 468023(212-1)/7 65535216-1 327662(214-1) 52779779555346(256–1)/5(214–1) 74423(210–1)/11 4194303222–1 90-99 9282022.17(212–1)/3 16777215224–1 2456412(211–1) 20971502(220–1) 503316426(223–1) 68719476735236–1 19226(22–1) 503316513(224+1) 41943062(221+1) 21626222(230–1)/(210–25+1)

There is a natural embedding of the case n=1 into the general case. It follows that all periods are divisible by 3.

The period for 2n is twice the period for n, for n>1. (The bounded case is less regular.)

These period lengths for n differ only a small factor (1/2, 1, 3/2, 3) from those in the bounded case for n–1. One should really compare the bounded case of order m with the unbounded of order 2m+2: there is an obvious embedding. Now the latter is larger by a small factor (1, 2, 3, 6). A factor 3 or 6 occurs precisely when the period in the bounded case was not divisible by 3.

The diagonal entries are: 0, 0, 4, 0, 8, 8, 0, 0, 4, 16, 0, 16, 0, 0, 12, 0, 16, 8, 0, 32, 4, 0, 0, 32, 8, 0, 4, 0, 0, 24, 40, 0, 44, 32, 8, 16, 0, 0, 4, 64, 0, 8, 0, 0, 12, 0, 0, 64, 0, 16, 20, 0, 0, 8, 8, 0, 4, 0, 0, 48, 0, 80, 52, 0, 56, 88, 0, 64, 4, 16, 0, 32, 0, 0, 12, 0, 0, 8, 0, 128, 4, 0, 0, 16, 24, 0, 4, 0, 0, 24, 0, 0, 44, 0, 8, 128, 0, 0, 44, 32, 0, 40, 0, 0, 12, 0, 0, 16, 0, 16, 4, 0, 0, 8, 8, 0, 4, 0, 16, 96, 0, 0, 4, 160, 8, 104, 112, 0, 116, 112, 0, 176, 0, 0, 12, 128, 0, 8, 0, 32, 4, 0, 0, 64, 8, 0, 4, 0, 0, 24, 0, 0, 20, 0, 48, 16, 0, 0, 4, 256, 0, 8, 0, 0, 52, 0, 0, 32, 0, 48, 76, 0, 0, 8, 8, 0, 4, 0, 0, 48, 0, 0, 4, 0, 8, 88, 16, 0, 52, 16, 0, 256, 0, 0, 60, 0, 0, 88, 0, 64, 4, 0, 0, 80, 48, 0, 4, 0, 0, 24, 0, 0, 4, 0, 8, 32, 40, 0, 4, 32, 16, 8, 0, 0, 12, 0, 0, 16, 0, 16, 44, 0, 0, 8, 8, 0, 4, 32, 0, 192, 0, 0, 4, 0, 8, 8, 0, 320, 4, 16, 0, 208, 0, 224, 284, 0, 288, 232, 0, 224, 4, 0, 0, 352, 8, 0, 4, 0, 0, 24, 0, 256, 4, 0, 8, 16, 0, 0, 44, 64, 0, 8, 0, 0, 12, 0, 0, 128, 16, 16, 4, 0, 0, 8, 8, 0, 44, 0, 0, 48, 0, 0, 4, 0, 8, 40, 0, 0, 4, 96, 0, 32, 0, 0, 60, 0, 0, 8, 0, 512, 4, 0, 16, 16, 56, 0, 4, 0, 0, 104, 0, 0, 4, 0, 8, 64, 0, 0, 4, 96, 80, 152, 0, 0, 12, 0, 0, 16, 0, 16, 4, 0, 0, 8, 8, 0, 20, 0, 0, 96, 0, 0, 44, 0, 8, 8, 0, 0, 4, 16, 0, 176, 0, 32, 12, 0, 0, 104, 0, 32, 116, 0, 0, 512, 8, 0, 116, 0, 0, 120, 16, 0, 4, 0, 8, 176, 0, 0, 4, 128, 0, 8, 40, 0, 12, 0, 0, 160, 0, 96, 4, 0, 0, 8, 8, 0, 4, 0, 0, 48, 0, 0, 4, 0, 24, 8, 0, 0, 44, 16, 0, 64, 0, 80, 12, 0, 0, 8, 0, 64, 52, 32, 0, 16, 8, 0, 4, 0, 0, 24, 0, 0, 4, 0, 152, 32, 0, 0, 20, 32, 0, 88, 0, 0, 52, 0, 0, 16, 0, 16, 4, 0, 0, 8, 8, 64, 4, 0, 0, 384, 0, 0, 4, 0, 8, 8, 0, 0, 4, 16, 0, 16, 16, 0, 52, 640, 0, 8, 0, 32, 4, 0, 0, 416, 8, 0, 4, 448, 0, 568, 504, 0, 508, 576, 8, 464, 0, 0, 4, 448, 0, 8, 0, 0, 12, 0, 56, 704, 0, 16, 4, 0, 0, 8, 8, 0, 4, 0, 0, 48, 0, 0, 4, 512, 8, 8, 0, 0, 4, 16, 0, 32, 0, 0, 12, 0, 0, 88, 0, 128, 60, 0, 0, 16, 8, 0, 52, 0, 0, 24, 0, 0, 4, 0, 8, 256, 0, 32, 4, 32, 0, 8, 0, 0, 252, 0, 0, 16, 40, 16, 4, 0, 0, 88, 24, 0, 4, 0, 0, 96, 0, 0, 4, 0, 8, 8, 0, 0, 4, 16, 0, 80, 0, 0, 52, 0, 0, 8, 0, 192, 4, 0, 0, 64, 8, 0, 44, 0, 16, 120, 0, 0, 4, 0, 120, 16, 0, 0, 4, 1024, 0, 8, 0, 0, 124, 32, 0, 32, 0, 112, 44, 0, 0, 8, 8, 0, 4, 0, 0, 208, 0, 0, 20, 0, 8, 8, 0, 0, 4, 16, 0, 128, 0, 0, 12, 0, 0, 8, 0, 192, 4, 160, 264, 304, 8, 0, 4, 0, 0, 24, 0, 0, 92, 0, 8, 32, 16, 0, 4, 32, 0, 8, 0, 0, 12, 0, 0, 16, 0, 16, 4, 0, 40, 40, 56, 0, 4, 0, 0, 192, 0, 0, 4, 0, 8, 88, 0, 0, 4, 16, 16, 16, 0, 0, 12, 0, 0, 8, 0, 32, 4, 0, 0, 352, 8, 0, 4, 64, 0, 24, 0, 0, 4, 0, 8, 208, 0, 0, 44, 64, 0, 232, 0, 0, 284, 0, 0, 1024, 0, 16, 292, 0, 0, 232, 48, 0, 4, 0, 0, 240, 0, 32, 4, 0, 8, 8, 0, 0, 4, 16, 0, 352, 0, 0, 12, 0, 0, 8, 16, 256, 4, 0, 0, 16, 8, 80, 4, 0, 0, 24, 0, 0, 4, 0, 8, 320, 0, 0, 196, 192, 0, 8, 0, 0, 52, 0, 0, 16, 0, 16, 4, 0, 16, 8, 8, 0, 44, 0, 0, 96, 0, 0, 4, 0, 56, 8, 0, 0, 4, 48, 0, 16, 0, 0, 84, 0, 0, 88, 0, 32, 4, 0, 0, 128, 8, 0, 20, 160, 0, 24, 0, 0, 4, 0, 8, 16, 0, 0, 4, 128, 0, 104, 0, 64, 12, 0, 0, 32, 112, 16, 44, 0, 0, 8, 8, 0, 4, 0, 40, 48, 16, 0, 116, 0, 8, 8, 0, 0, 4, 304, 0, 64, 0, 0, 12, 0, 0, 40, 0, 64, 4, 0, 0, 176, 8, 0, 4, 0, 0, 104, 0, 0, 4, 0, 24, 32, 0, 0, 4, 32, 0, 8, 0, 0, 60, 0, 0, 16, 0, 16, 4, 128, 0, 8, 8, 0, 44, 0, 0, 768, 40, 0, 4, 0, 8, 8, 0, 0, 20, 16, 0, 16, 0, 0, 60, 0, 0, 8, 0, 32, 4, 0, 0, 32, 8, 32, 4, 0, 0, 104, 0, 1280, 4, 0, 8, 16, 0, 0, 4, 64, ...

These are all multiples of 4. One has codim(2n) = 2codim(n). If codim' is the codimension in the case with boundary, then codim(n+1) = 2codim'(n)+4 if n is 2 (mod 3) and codim(n+1) = 2codim'(n) otherwise.

We called a number n MAD, when the square grid of order n (without boundary) has nonzero codimension, while all proper divisors of n have zero codimension. (The mad numbers are the indices 3, 5, 6, 9, 10, 12, 15, 17, ... for which the codimension is nonzero, and the MAD numbers are the mad numbers 3, 5, 17, ... that are not divisible by a smaller mad number.)

Lights Out

This is the case with boundary.

A table of 2-coranks of I+A for the m × n grid with boundary for m,n ranging between 1 and 30.

``` 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 1 0 0 1 0
1 0 2 0 1 0 2 0 1 0 2 0 1 0 2 0 1 0 2 0 1 0 2 0 1 0 2 0 1 0
0 2 0 0 3 0 0 2 0 0 3 0 0 2 0 0 3 0 0 2 0 0 3 0 0 2 0 0 3 0
0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0
1 1 3 0 2 0 4 1 1 0 4 0 1 1 4 0 2 0 3 1 1 0 5 0 1 1 3 0 2 0
0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 6 0 0 0 0
0 2 0 0 4 0 0 2 0 0 7 0 0 2 0 0 4 0 0 2 0 0 7 0 0 2 0 0 4 0
1 0 2 0 1 6 2 0 1 0 2 0 7 0 2 0 1 0 2 6 1 0 2 0 1 0 8 0 1 0
0 1 0 4 1 0 0 1 8 0 1 0 0 5 0 0 1 0 8 1 0 0 1 4 0 1 0 0 9 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 010
1 2 3 0 4 0 7 2 1 0 6 0 1 2 8 0 4 0 3 2 1 010 0 1 2 3 0 4 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 7 0 0 1 0 0 1 0 013 0 0 1 0 0 1 0 0 7 0 0 1 0
1 0 2 4 1 0 2 0 5 0 2 0 1 4 2 8 1 0 6 0 1 0 2 4 1 0 2 0 5 0
0 2 0 0 4 0 0 2 0 0 8 0 0 2 0 0 4 0 0 2 0 015 0 0 2 0 0 4 0
0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 8 0 0 0 0 0 0 0 0 0 0 0 0 8 0
1 1 3 0 2 6 4 1 1 0 4 013 1 4 0 2 0 3 7 1 0 5 0 1 115 0 2 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 4 3 0 0 2 8 0 3 0 0 6 0 0 3 016 2 0 0 3 4 0 2 0 011 0
1 0 2 0 1 0 2 6 1 0 2 0 1 0 2 0 7 0 2 0 1 0 2 0 1 6 2 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 1 0 0 1 0 0 110
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 2 3 0 5 0 7 2 1 010 0 1 215 0 5 0 3 2 1 014 0 1 2 3 0 5 0
0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0 0 0 0 4 0
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 1 0 0 1 0
1 0 2 0 1 6 2 0 1 0 2 0 7 0 2 0 1 0 2 6 1 0 2 0 1 0 8 0 1 0
0 2 0 0 3 0 0 8 0 0 3 0 0 2 0 015 0 0 2 0 0 3 0 0 8 0 0 3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 3 4 2 0 4 1 9 0 4 0 1 5 4 8 2 011 1 1 0 5 4 1 1 3 010 0
0 0 0 0 0 0 0 0 010 0 0 0 0 0 0 0 0 0 010 0 0 0 0 0 0 0 020
```
The entries 0 here correspond to pairs (m,n) for which I+A has full 2-rank, so that an arbitrary position can be brought into the "all lights out" position.

Let C be the row space of I+A. It is the subspace of patterns that can be switched off. Given an arbitrary vector, it is always possible to find a coset representative with support contained in a single row or column, so codim(C) will lie between 0 and min(m,n). (Indeed, given an arbitrary pattern, one can sweep all of the board clean except for the bottom row, by starting at the top row and always pressing the button below any "on" position.)

Remains to investigate what effect pressing buttons on the top row and sweeping has on the bottom row. Look at a window (v,w) of two successive rows. Propagation is via the transformation T: (v,w) -> (w+v+v+v+,v), which is linear and 1-1, so the rows and columns will be periodic. We start with a virtual (0,w), and if d is the smallest power of the the transformation that maps the subspace (0,*) to itself, and m+1 is divisible by d, then after m steps we are back at (0,*), which is projected into 0 because of the bottom boundary, so that for these m the codimension is a full m (and the preceding and following m will have codimension 0). Conversely, if m is the smallest for which full codimension occurs, then the row/column is periodic with period d = m+1. In order to find the period, one only needs to consider the starting vector 0...01 with a single 1 at the end. Since the rows following an all-zero row are the same as the rows preceding, the period of the transformation T is either d or 2d. For a table listing the periods for n at most 1200, see below.

The above transformation preserves the natural symplectic form for which (0,*) and (*,0) are maximal totally isotropic subspaces, so is element of the symplectic group Sp(2n,2). The order of this group is 2n2Π(4i−1) (product from i=1 to n) and the periods will be divisors of this number. This explains the affinity for powers of two of the periods (see below).

The diagonal entries are 0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 6, 0, 0, 4, 0, 8, 2, 0, 16, 0, 0, 0, 14, 4, 0, 0, 0, 0, 10, 20, 0, 20, 16, 4, 6, 0, 0, 0, 32, 0, 2, 0, 0, 4, 0, 0, 30, 0, 8, 8, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 40, 24, 0, 28, 42, 0, 32, 0, 8, 0, 14, 0, 0, 4, 0, 0, 2, 0, 64, 0, 0, 0, 6, 12, 0, 0, 0, 0, 10, 0, 0, 20, 0, 4, 62, 0, 0, 20, 16, 0, 18, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 0, 0, 0, 8, 46, 0, 0, 0, 80, 4, 50, 56, 0, 56, 56, 0, 86, 0, 0, 4, 64, 0, 2, 0, 16, 0, 0, 0, 30, 4, 0, 0, 0, 0, 10, 0, 0, 8, 0, 24, 6, 0, 0, 0, 128, 0, 2, 0, 0, 24, 0, 0, 14, 0, 24, 36, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 0, 0, 0, 4, 42, 8, 0, 24, 8, 0, 126, 0, 0, 28, 0, 0, 42, 0, 32, 0, 0, 0, 38, 24, 0, 0, 0, 0, 10, 0, 0, 0, 0, 4, 14, 20, 0, 0, 16, 8, 2, 0, 0, 4, 0, 0, 6, 0, 8, 20, 0, 0, 2, 4, 0, 0, 16, 0, 94, 0, 0, 0, 0, 4, 2, 0, 160, 0, 8, 0, 102, 0, 112, 140, 0, 144, 114, 0, 112, 0, 0, 0, 174, 4, 0, 0, 0, 0, 10, 0, 128, 0, 0, 4, 6, 0, 0, 20, 32, 0, 2, 0, 0, 4, 0, 0, 62, 8, 8, 0, 0, 0, 2, 4, 0, 20, 0, 0, 22, 0, 0, 0, 0, 4, 18, 0, 0, 0, 48, 0, 14, 0, 0, 28, 0, 0, 2, 0, 256, 0, 0, 8, 6, 28, 0, 0, 0, 0, 50, 0, 0, 0, 0, 4, 30, 0, 0, 0, 48, 40, 74, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 0, 8, 0, 0, 46, 0, 0, 20, 0, 4, 2, 0, 0, 0, 8, 0, 86, 0, 16, 4, 0, 0, 50, 0, 16, 56, 0, 0, 254, 4, 0, 56, 0, 0, 58, 8, 0, 0, 0, 4, 86, 0, 0, 0, 64, 0, 2, 20, 0, 4, 0, 0, 78, 0, 48, 0, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 0, 0, 0, 12, 2, 0, 0, 20, 8, 0, 30, 0, 40, 4, 0, 0, 2, 0, 32, 24, 16, 0, 6, 4, 0, 0, 0, 0, 10, 0, 0, 0, 0, 76, 14, 0, 0, 8, 16, 0, 42, 0, 0, 24, 0, 0, 6, 0, 8, 0, 0, 0, 2, 4, 32, 0, 0, 0, 190, 0, 0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 6, 8, 0, 24, 320, 0, 2, 0, 16, 0, 0, 0, 206, 4, 0, 0, 224, 0, 282, 252, 0, 252, 288, 4, 230, 0, 0, 0, 224, 0, 2, 0, 0, 4, 0, 28, 350, 0, 8, 0, 0, 0, 2, 4, 0, 0, 0, 0, 22, 0, 0, 0, 256, 4, 2, 0, 0, 0, 8, 0, 14, 0, 0, 4, 0, 0, 42, 0, 64, 28, 0, 0, 6, 4, 0, 24, 0, 0, 10, 0, 0, 0, 0, 4, 126, 0, 16, 0, 16, 0, 2, 0, 0, 124, 0, 0, 6, 20, 8, 0, 0, 0, 42, 12, 0, 0, 0, 0, 46, 0, 0, 0, 0, 4, 2, 0, 0, 0, 8, 0, 38, 0, 0, 24, 0, 0, 2, 0, 96, 0, 0, 0, 30, 4, 0, 20, 0, 8, 58, 0, 0, 0, 0, 60, 6, 0, 0, 0, 512, 0, 2, 0, 0, 60, 16, 0, 14, 0, 56, 20, 0, 0, 2, 4, 0, 0, 0, 0, 102, 0, 0, 8, 0, 4, 2, 0, 0, 0, 8, 0, 62, 0, 0, 4, 0, 0, 2, 0, 96, 0, 80, 132, 150, 4, 0, 0, 0, 0, 10, 0, 0, 44, 0, 4, 14, 8, 0, 0, 16, 0, 2, 0, 0, 4, 0, 0, 6, 0, 8, 0, 0, 20, 18, 28, 0, 0, 0, 0, 94, 0, 0, 0, 0, 4, 42, 0, 0, 0, 8, 8, 6, 0, 0, 4, 0, 0, 2, 0, 16, 0, 0, 0, 174, 4, 0, 0, 32, 0, 10, 0, 0, 0, 0, 4, 102, 0, 0, 20, 32, 0, 114, 0, 0, 140, 0, 0, 510, 0, 8, 144, 0, 0, 114, 24, 0, 0, 0, 0, 118, 0, 16, 0, 0, 4, 2, 0, 0, 0, 8, 0, 174, 0, 0, 4, 0, 0, 2, 8, 128, 0, 0, 0, 6, 4, 40, 0, 0, 0, 10, 0, 0, 0, 0, 4, 158, 0, 0, 96, 96, 0, 2, 0, 0, 24, 0, 0, 6, 0, 8, 0, 0, 8, 2, 4, 0, 20, 0, 0, 46, 0, 0, 0, 0, 28, 2, 0, 0, 0, 24, 0, 6, 0, 0, 40, 0, 0, 42, 0, 16, 0, 0, 0, 62, 4, 0, 8, 80, 0, 10, 0, 0, 0, 0, 4, 6, 0, 0, 0, 64, 0, 50, 0, 32, 4, 0, 0, 14, 56, 8, 20, 0, 0, 2, 4, 0, 0, 0, 20, 22, 8, 0, 56, 0, 4, 2, 0, 0, 0, 152, 0, 30, 0, 0, 4, 0, 0, 18, 0, 32, 0, 0, 0, 86, 4, 0, 0, 0, 0, 50, 0, 0, 0, 0, 12, 14, 0, 0, 0, 16, 0, 2, 0, 0, 28, 0, 0, 6, 0, 8, 0, 64, 0, 2, 4, 0, 20, 0, 0, 382, 20, 0, 0, 0, 4, 2, 0, 0, 8, 8, 0, 6, 0, 0, 28, 0, 0, 2, 0, 16, 0, 0, 0, 14, 4, 16, 0, 0, 0, 50, 0, 640, 0, 0, 4, 6, 0, 0, 0, 32, 0, ...

(The first 100 of these were given in Sutner (1989).) These are all even. Regularities are easier to understand by comparing with the case without boundary. This is the sequence of 2-logarithms of Sloane's sequence A075462. The positions of the zeros in this sequence form Sloane's sequence A076436. The positions of the nonzeros form Sloane's sequence A117870, which is one less than A093614. The primitive elements (5, 6, 17, 31, 33, 63, 127, 129, 171, 257, 511, 683, 2047, 2731, 2979, 3277, 3641, 8191, 28197, 43691, 48771, 52429, 61681, 65537, 85489, 131071, ...) of that latter sequence, the analogues of the MAD numbers below) form A094425, and are discussed in [Hunziker et al. (2004)].

Let pn(x) be the mod 2 characteristic polynomial of the path of length n. The table has a zero in position (m,n) if and only if gcd(pm(x), pn(x+1)) = 1 [Barua & Ramakrishnan (1996)]. More generally, codim(m,n) = degr(gcd(pm(x), pn(x+1))) [Sutner (2000)]. The period of column n is the smallest t such that pn(x+1) | pt-1(x).

The pn(x) can be simply computed via p0(x) = 1, p1(x) = x, pn+1(x) = xpn(x) + pn-1(x). More generally one has the relation pn+m = pm pn + pm-1 pn-1.

Period lengths for Lights Out

The function 2-corank(m,n) is periodic. The tables below give the period in m for fixed n.

Period lengths for 0 ≤ n ≤ 99:
 n 0 1 2 3 4 5 6 7 8 9 0-9 11 322–1 422 62(22–1) 522+1 2423(22–1) 923+1 1222(22–1) 2822(23–1) 302(24–1) 10-19 3125–1 4824(22–1) 6326–1 182(23+1) 34022(28–1)/3 2423(22–1) 25528–1 16823(26–1)/3 51329+1 6022(24–1) 20-29 234022(212–1)/7 1866(25–1) 2047211–1 9625(22–1) 1025210+1 1262(26–1) 204422(29–1) 3622(23+1) 3277(214+1)/5 204023(28–1) 30-39 341(210–1)/3 4824(22–1) 409222(210–1) 5102(28–1) 4095212–1 33624(26–1)/3 35917(29+1) 10262(29+1) 1638022(212–1) 12023(24–1) 40-49 1048575220–1 468023(212–1)/7 16383214–1 37212(25–1) 9282022.17(212–1)/3 122826(211–1) 8388607223–1 19226(22–1) 2097153221+1 61506(210+1) 50-59 26214022(216–1) 25222(26–1) 67108865226+1 1226424(29–1) 25575(220–1)/41 7223(23+1) 104857222(218–1) 196626(214+1)/5 536870911229–1 408024(28–1) 60-69 1073741823230–1 20462(210–1) 1638022(212–1) 9625(22–1) 4095212–1 818423(210–1) 8589934593233+1 102022(28–1) 559240422(222–1)/3 81902(212–1) 70-79 34359738367235–1 67225(26–1)/3 262143218–1 718214(29+1) 429916570022(240–1)/(210–1) 205222(29+1) 1073741823230–1 3276023(212–1) 549755813889239+1 24024(24–1) 80-89 53687090822(227–1) 20971502(220–1) 2199023255551241–1 936024(212–1)/7 65535216–1 327662(214–1) 351865197035622(256–1)/5(214–1) 74423(210–1)/11 4194303222–1 18564023.17(212–1)/3 90-99 16777215224–1 2456412(211–1) 419430022(220–1) 503316426(223–1) 68719476735236–1 38427(22–1) 16777217224+1 41943062(221+1) 432524422(230–1)/(210–25+1) 1230012(210+1)

These numbers are one more than those in Sloane's sequence A118141 that gives the sizes of perfect parity patterns.

For a much longer table, see this separate page. The numbers quickly get large. For example, for n=1186 one finds period
 3.24181e+178