Characterizing switch-setting problems∗

DOI10.1080/03081089708818520MaRDI QIDQ4376554zbMATH OpenOpenAlexFDO

Authors William F. Klostermeyer, John Goldwasser, George E. Trapp

Publication date 29 June 1998

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03081089708818520

zbMATH Keywords

binary matrixFibonacci polynomialsfinite field representationgreatest common divisorswitches

Mathematics Subject Classification ID

Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Theory of matrix inversion and generalized inverses (15A09) Analysis of algorithms and problem complexity (68Q25)

Review text

Consider an \(m\times n\) rectangular configuration of switches, each of which can be in the on or off position. When any switch is toggled, it and its rectilinear neighbors change state. Algebraic and algorithmic procedures are given to determine whether an \(m\times n\) configuration can be transformed so that all switches are in the off position, regardless of the initial configuration. Using linear algebra, a finite field representation of the problem, and an analysis of Fibonacci polynomials, conditions on \(m\) and \(n\) are given which characterize when the \(m\times n\) problem can be solved.

Recommendations

• On a switch-setting problem arising from a variation of the `Lights Out' game
• The solution to Berlekamp's switching game
• scientific article; zbMATH DE number 1161323
• How to turn all the lights out

Cited in

(17)

• Maximum orbit weights in the -game and lit-only -game on grids and graphs
• The density of ones in Pascal's rhombus
• Lights Out on graphs
• On the complexity of dominating set problems related to the minimum all-ones problem
• A Survey of the Game “Lights Out!”
• Cyclic mutually unbiased bases, Fibonacci polynomials and Wiedemann's conjecture
• Random Lights Out processes on graphs
• ``Lights Out and variants
• A non-geometric switch toggling problem
• Chasing the lights in Lights Out
• Parity Dimension for Graphs - A Linear Algebraic Approach
• Lights Out! On graph products over the ring of integers modulo \(k\)
• Lights Out On A Random Graph
• Note on the lamp lighting problem
• A recursive approach to a multi-state cylindrical lights out game
• Residue domination in bounded-treewidth graphs
• Minimum light number of lit-only \(\sigma\)-game on a tree

This page was built for publication: Characterizing switch-setting problems^∗

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376554)