Characterizing switch-setting problems^∗

Abstract

Algebraic conditions and algorithmic procedures are given to determine whether an m × n rectangular configuration of switches can be transformed so that all switches are in the off position, regardless of initial configuration. However, when any switch is toggled, it and its rectilinearly adjacent neighbors change state. 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 × n problem can be solved.