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.)

[Blokhuis (unpub.), Eriksson² & Sjöstrand (2001). See also the Grey Labyrinth.]

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.

Links and references

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,

Button Madness

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 Tⁿ−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 3
2²–1 3
2²–1 6
2(2²–1) 6
2(2²–1) 15
2⁴–1 12
2²(2²–1) 9
2³+1 12
2²(2²–1) 42
2(2⁶–1)/3

10-19 30
2(2⁴–1) 93
3(2⁵–1) 24
2³(2²–1) 63
2⁶–1 18
2(2³+1) 510
2(2⁸–1) 24
2³(2²–1) 255
2⁸–1 84
2²(2⁶–1)/3 513
2⁹+1

20-29 60
2²(2⁴–1) 1170
2(2¹²–1)/7 186
6(2⁵–1) 6141
3(2¹¹–1) 48
2⁴(2²–1) 3075
3(2¹⁰+1) 126
2(2⁶–1) 3066
6(2⁹–1) 36
2²(2³+1) 9831
3(2¹⁴+1)/5

30-39 1020
2²(2⁸–1) 1023
2¹⁰–1 48
2⁴(2²–1) 2046
2(2¹⁰–1) 510
2(2⁸–1) 4095
2¹²–1 168
2³(2⁶–1)/3 3591
7(2⁹+1) 1026
2(2⁹+1) 8190
2(2¹²–1)

40-49 120
2³(2⁴–1) 1048575
2²⁰–1 2340
2²(2¹²–1)/7 16383
2¹⁴–1 372
12(2⁵–1) 46410
2.17(2¹²–1)/3 12282
6(2¹¹–1) 25165821
3(2²³–1) 96
2⁵(2²–1) 2097153
2²¹+1

50-59 6150
6(2¹⁰+1) 131070
2(2¹⁶–1) 252
2²(2⁶–1) 201326595
3(2²⁶+1) 6132
12(2⁹–1) 25575
(2²⁰–1)/41 72
2³(2³+1) 524286
2(2¹⁸–1) 19662
6(2¹⁴+1)/5 1610612733
3(2²⁹–1)

60-69 2040
2³(2⁸–1) 1073741823
2³⁰–1 2046
2(2¹⁰–1) 8190
2(2¹²–1) 96
2⁵(2²–1) 4095
2¹²–1 4092
2²(2¹⁰–1) 8589934593
2³³+1 1020
2²(2⁸–1) 8388606
2(2²²–1)

70-79 8190
2(2¹²–1) 103079215101
3(2³⁵–1) 336
2⁴(2⁶–1)/3 262143
2¹⁸–1 7182
14(2⁹+1) 6448748550
6(2¹⁰+1)(2²⁰+1) 2052
2²(2⁹+1) 1073741823
2³⁰–1 16380
2²(2¹²–1) 549755813889
2³⁹+1

80-89 240
2⁴(2⁴–1) 805306362
6(2²⁷–1) 2097150
2(2²⁰–1) 6597069766653
3(2⁴¹-1) 4680
2³(2¹²-1)/7 65535
2¹⁶-1 32766
2(2¹⁴-1) 5277977955534
6(2⁵⁶–1)/5(2¹⁴–1) 744
2³(2¹⁰–1)/11 4194303
2²²–1

90-99 92820
2².17(2¹²–1)/3 16777215
2²⁴–1 24564
12(2¹¹–1) 2097150
2(2²⁰–1) 50331642
6(2²³–1) 68719476735
2³⁶–1 192
2⁶(2²–1) 50331651
3(2²⁴+1) 4194306
2(2²¹+1) 2162622
2(2³⁰–1)/(2¹⁰–2⁵+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 2^n²Π(4ⁱ−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 p_n(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(p_m(x), p_n(x+1)) = 1 [Barua & Ramakrishnan (1996)]. More generally, codim(m,n) = degr(gcd(p_m(x), p_n(x+1))) [Sutner (2000)]. The period of column n is the smallest t such that p_n(x+1) | p_t-1(x).

The p_n(x) can be simply computed via p₀(x) = 1, p₁(x) = x, p_n+1(x) = xp_n(x) + p_n-1(x). More generally one has the relation p_n+m = p_m p_n + p_m-1 p_n-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 1
1 3
2²–1 4
2² 6
2(2²–1) 5
2²+1 24
2³(2²–1) 9
2³+1 12
2²(2²–1) 28
2²(2³–1) 30
2(2⁴–1)

10-19 31
2⁵–1 48
2⁴(2²–1) 63
2⁶–1 18
2(2³+1) 340
2²(2⁸–1)/3 24
2³(2²–1) 255
2⁸–1 168
2³(2⁶–1)/3 513
2⁹+1 60
2²(2⁴–1)

20-29 2340
2²(2¹²–1)/7 186
6(2⁵–1) 2047
2¹¹–1 96
2⁵(2²–1) 1025
2¹⁰+1 126
2(2⁶–1) 2044
2²(2⁹–1) 36
2²(2³+1) 3277
(2¹⁴+1)/5 2040
2³(2⁸–1)

30-39 341
(2¹⁰–1)/3 48
2⁴(2²–1) 4092
2²(2¹⁰–1) 510
2(2⁸–1) 4095
2¹²–1 336
2⁴(2⁶–1)/3 3591
7(2⁹+1) 1026
2(2⁹+1) 16380
2²(2¹²–1) 120
2³(2⁴–1)

40-49 1048575
2²⁰–1 4680
2³(2¹²–1)/7 16383
2¹⁴–1 372
12(2⁵–1) 92820
2².17(2¹²–1)/3 12282
6(2¹¹–1) 8388607
2²³–1 192
2⁶(2²–1) 2097153
2²¹+1 6150
6(2¹⁰+1)

50-59 262140
2²(2¹⁶–1) 252
2²(2⁶–1) 67108865
2²⁶+1 12264
24(2⁹–1) 25575
(2²⁰–1)/41 72
2³(2³+1) 1048572
2²(2¹⁸–1) 19662
6(2¹⁴+1)/5 536870911
2²⁹–1 4080
2⁴(2⁸–1)

60-69 1073741823
2³⁰–1 2046
2(2¹⁰–1) 16380
2²(2¹²–1) 96
2⁵(2²–1) 4095
2¹²–1 8184
2³(2¹⁰–1) 8589934593
2³³+1 1020
2²(2⁸–1) 5592404
2²(2²²–1)/3 8190
2(2¹²–1)

70-79 34359738367
2³⁵–1 672
2⁵(2⁶–1)/3 262143
2¹⁸–1 7182
14(2⁹+1) 4299165700
2²(2⁴⁰–1)/(2¹⁰–1) 2052
2²(2⁹+1) 1073741823
2³⁰–1 32760
2³(2¹²–1) 549755813889
2³⁹+1 240
2⁴(2⁴–1)

80-89 536870908
2²(2²⁷–1) 2097150
2(2²⁰–1) 2199023255551
2⁴¹–1 9360
2⁴(2¹²–1)/7 65535
2¹⁶–1 32766
2(2¹⁴–1) 3518651970356
2²(2⁵⁶–1)/5(2¹⁴–1) 744
2³(2¹⁰–1)/11 4194303
2²²–1 185640
2³.17(2¹²–1)/3

90-99 16777215
2²⁴–1 24564
12(2¹¹–1) 4194300
2²(2²⁰–1) 50331642
6(2²³–1) 68719476735
2³⁶–1 384
2⁷(2²–1) 16777217
2²⁴+1 4194306
2(2²¹+1) 4325244
2²(2³⁰–1)/(2¹⁰–2⁵+1) 12300
12(2¹⁰+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
32418090381882757488378186435087196492284736189394038281216072888208225089163344893747711319899248392876545989150787415487462117776654494592866209641515341305165482839074293153791.

aeb

	0	1	2	3	4	5	6	7	8	9
0-9		3 2²–1	3 2²–1	6 2(2²–1)	6 2(2²–1)	15 2⁴–1	12 2²(2²–1)	9 2³+1	12 2²(2²–1)	42 2(2⁶–1)/3
10-19	30 2(2⁴–1)	93 3(2⁵–1)	24 2³(2²–1)	63 2⁶–1	18 2(2³+1)	510 2(2⁸–1)	24 2³(2²–1)	255 2⁸–1	84 2²(2⁶–1)/3	513 2⁹+1
20-29	60 2²(2⁴–1)	1170 2(2¹²–1)/7	186 6(2⁵–1)	6141 3(2¹¹–1)	48 2⁴(2²–1)	3075 3(2¹⁰+1)	126 2(2⁶–1)	3066 6(2⁹–1)	36 2²(2³+1)	9831 3(2¹⁴+1)/5
30-39	1020 2²(2⁸–1)	1023 2¹⁰–1	48 2⁴(2²–1)	2046 2(2¹⁰–1)	510 2(2⁸–1)	4095 2¹²–1	168 2³(2⁶–1)/3	3591 7(2⁹+1)	1026 2(2⁹+1)	8190 2(2¹²–1)
40-49	120 2³(2⁴–1)	1048575 2²⁰–1	2340 2²(2¹²–1)/7	16383 2¹⁴–1	372 12(2⁵–1)	46410 2.17(2¹²–1)/3	12282 6(2¹¹–1)	25165821 3(2²³–1)	96 2⁵(2²–1)	2097153 2²¹+1
50-59	6150 6(2¹⁰+1)	131070 2(2¹⁶–1)	252 2²(2⁶–1)	201326595 3(2²⁶+1)	6132 12(2⁹–1)	25575 (2²⁰–1)/41	72 2³(2³+1)	524286 2(2¹⁸–1)	19662 6(2¹⁴+1)/5	1610612733 3(2²⁹–1)
60-69	2040 2³(2⁸–1)	1073741823 2³⁰–1	2046 2(2¹⁰–1)	8190 2(2¹²–1)	96 2⁵(2²–1)	4095 2¹²–1	4092 2²(2¹⁰–1)	8589934593 2³³+1	1020 2²(2⁸–1)	8388606 2(2²²–1)
70-79	8190 2(2¹²–1)	103079215101 3(2³⁵–1)	336 2⁴(2⁶–1)/3	262143 2¹⁸–1	7182 14(2⁹+1)	6448748550 6(2¹⁰+1)(2²⁰+1)	2052 2²(2⁹+1)	1073741823 2³⁰–1	16380 2²(2¹²–1)	549755813889 2³⁹+1
80-89	240 2⁴(2⁴–1)	805306362 6(2²⁷–1)	2097150 2(2²⁰–1)	6597069766653 3(2⁴¹-1)	4680 2³(2¹²-1)/7	65535 2¹⁶-1	32766 2(2¹⁴-1)	5277977955534 6(2⁵⁶–1)/5(2¹⁴–1)	744 2³(2¹⁰–1)/11	4194303 2²²–1
90-99	92820 2².17(2¹²–1)/3	16777215 2²⁴–1	24564 12(2¹¹–1)	2097150 2(2²⁰–1)	50331642 6(2²³–1)	68719476735 2³⁶–1	192 2⁶(2²–1)	50331651 3(2²⁴+1)	4194306 2(2²¹+1)	2162622 2(2³⁰–1)/(2¹⁰–2⁵+1)

n	0	1	2	3	4	5	6	7	8	9
0-9	1 1	3 2²–1	4 2²	6 2(2²–1)	5 2²+1	24 2³(2²–1)	9 2³+1	12 2²(2²–1)	28 2²(2³–1)	30 2(2⁴–1)
10-19	31 2⁵–1	48 2⁴(2²–1)	63 2⁶–1	18 2(2³+1)	340 2²(2⁸–1)/3	24 2³(2²–1)	255 2⁸–1	168 2³(2⁶–1)/3	513 2⁹+1	60 2²(2⁴–1)
20-29	2340 2²(2¹²–1)/7	186 6(2⁵–1)	2047 2¹¹–1	96 2⁵(2²–1)	1025 2¹⁰+1	126 2(2⁶–1)	2044 2²(2⁹–1)	36 2²(2³+1)	3277 (2¹⁴+1)/5	2040 2³(2⁸–1)
30-39	341 (2¹⁰–1)/3	48 2⁴(2²–1)	4092 2²(2¹⁰–1)	510 2(2⁸–1)	4095 2¹²–1	336 2⁴(2⁶–1)/3	3591 7(2⁹+1)	1026 2(2⁹+1)	16380 2²(2¹²–1)	120 2³(2⁴–1)
40-49	1048575 2²⁰–1	4680 2³(2¹²–1)/7	16383 2¹⁴–1	372 12(2⁵–1)	92820 2².17(2¹²–1)/3	12282 6(2¹¹–1)	8388607 2²³–1	192 2⁶(2²–1)	2097153 2²¹+1	6150 6(2¹⁰+1)
50-59	262140 2²(2¹⁶–1)	252 2²(2⁶–1)	67108865 2²⁶+1	12264 24(2⁹–1)	25575 (2²⁰–1)/41	72 2³(2³+1)	1048572 2²(2¹⁸–1)	19662 6(2¹⁴+1)/5	536870911 2²⁹–1	4080 2⁴(2⁸–1)
60-69	1073741823 2³⁰–1	2046 2(2¹⁰–1)	16380 2²(2¹²–1)	96 2⁵(2²–1)	4095 2¹²–1	8184 2³(2¹⁰–1)	8589934593 2³³+1	1020 2²(2⁸–1)	5592404 2²(2²²–1)/3	8190 2(2¹²–1)
70-79	34359738367 2³⁵–1	672 2⁵(2⁶–1)/3	262143 2¹⁸–1	7182 14(2⁹+1)	4299165700 2²(2⁴⁰–1)/(2¹⁰–1)	2052 2²(2⁹+1)	1073741823 2³⁰–1	32760 2³(2¹²–1)	549755813889 2³⁹+1	240 2⁴(2⁴–1)
80-89	536870908 2²(2²⁷–1)	2097150 2(2²⁰–1)	2199023255551 2⁴¹–1	9360 2⁴(2¹²–1)/7	65535 2¹⁶–1	32766 2(2¹⁴–1)	3518651970356 2²(2⁵⁶–1)/5(2¹⁴–1)	744 2³(2¹⁰–1)/11	4194303 2²²–1	185640 2³.17(2¹²–1)/3
90-99	16777215 2²⁴–1	24564 12(2¹¹–1)	4194300 2²(2²⁰–1)	50331642 6(2²³–1)	68719476735 2³⁶–1	384 2⁷(2²–1)	16777217 2²⁴+1	4194306 2(2²¹+1)	4325244 2²(2³⁰–1)/(2¹⁰–2⁵+1)	12300 12(2¹⁰+1)