Prime Nullspace Matrices and Even Dominating Sets

Abstract

A non-zero $m\times n$ (0, 1)-matrix $A$ is called a {\em nullspace matrix} if each entry $(i,j)$ of $A$ has an even number of $1^{\prime }s$ in the set of entries consisting of $(i,j)$ and its rectilinear neighbors. These matrices correspond to even dominating sets of $m\times n$ grid graphs. We study these matrices and consider those that cannot be constructed from smaller nullspace matrices.