Colorings and Nowhere-Zero Flows of Graphs in Terms of Berlekamp's Switching Game

We work with a unifying linear algebra formulation for nowhere-zero flows and colorings of graphs and matrices. Given a subspace (code) U <= Z(k)(n) - e.g. the bond or the cycle space over Z(k) of an oriented graph we call a nowhere-zero tuple integral is an element of Z(k)(n) a flow of U if integral is orthogonal to U. In order to detect flows, we view the subspace U as a light pattern on the n-dimensional Berlekamp Board Z(k)(n) With k(n) light bulbs. The lights corresponding to elements of U are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns, etc. The core result of this paper is that the subspace U has a flow if and only if the light pattern U cannot be switched off. In particular, a graph C has a nowhere-zero k-flow if and only if the Z(k)-bond space of (7 cannot be switched off. It has a vertex coloring with k colors if and only if a certain corresponding code over Z(k) cannot be switched off. Similar statements hold for Tait colorings,