Characterizing switch-setting problems<sup>∗</sup> (Q4376554)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1117575
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Characterizing switch-setting problems<sup>∗</sup> |
scientific article; zbMATH DE number 1117575 |
Statements
Characterizing switch-setting problems<sup>∗</sup> (English)
0 references
29 June 1998
0 references
binary matrix
0 references
greatest common divisor
0 references
switches
0 references
finite field representation
0 references
Fibonacci polynomials
0 references
0.759219765663147
0 references
0.7358806133270264
0 references
0.7200005650520325
0 references
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.
0 references
