Note on the lamp lighting problem

We answer some questions concerning the so-called sigma -game of Sutner [Li near cellular automata and the Garden of Eden, Math. Intelligencer 11 (1989 ), 49-53]. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lam p. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the speci al case of an orthogonal grid one gets a criterion for whether the number o f monomer-dimer tilings of an m x n grid is odd or even. (C) 2001 Academic Press.