Is this problem NP-complete?

Question

Let matrix $M \in \{0,1\}^{r \times (c+1)r}$ for some $c \in \Bbb Z_{+}$ be given.

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ $:$$\prod_i v_i \in 2\Bbb Z+1$ where $v=uM$?

Answer 1

The problem is in $P$, and hence not $NP$-complete unless $P=NP$.

Because we are only concerned with parity, we can treat the matrices and vectors as having entries lying in $\mathbb{F}_2$. Then the condition just becomes $uM=j$, where $j$ is the all-ones row vector. This can be solved with Gaussian elimination.