Anti-Codes in Terms of Berlekamp's Switching Game

We view a linear code (subspace) C <= F-q(n) as a light pattern on the n-dimensional Berlekamp Board F-q(n) with q(n) light bulbs. The lights corresponding to elements of C are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns. etc. We show that the dual code C-perpendicular to contains a vector v of full weight, i.e. v(1), v(2),...,v(n) not equal 0 if and only if the light pattern C cannot be switched off. Generalizations of this allow us to describe anti-codes with maximal weight delta in a similar way, or, alternatively, in terms of a switching game in projective space. We provide convenient bases and normal forms to the modules of all light patterns of the generalized games. All our proofs are purely combinatorial and simpler than the algebraic ones used for similar results about anti-codes in Z(k)(n). Aside from coding theory, the game is also of interest in the study of nowhere-zero points of matrices and nowhere-zero flows and colorings of