Let $p$ be a prime and let $M$ be an $n \times m$ matrix with integer entries such that $M\vec{v} \not\equiv \vec{0} \text{ (mod }p\text{)}$ for any column vector $\vec{v} \neq \vec{0}$ whose entries are $0$ or $1$.


Is there a row vector $\vec{x}$ with integer entries such that no entry of $\vec{x}M$ is $0 \text{ (mod }p\text{)}$?



Is there a row vector $x$ with integer entries such that no entry of $xM$ is $0 \text{ (mod }p\text{)}$?
It seems that my previous answer was completely wrong, and that the fact is **true** for all nonzero integer (not necessarily prime) $p$.


Let $M=[m\_{ij}]\_{i\leq n,\;j\leq m}$. If there is no $x$ satisfying the requirements (we regard all entries as integers, not residues!), then one of the sums of the form $\sum\_{i\leq n} m\_{ij}x\_i$, $j\leq m$, is divisible by $p$ for every integer vector $x$. Equivalently,
$$ 
 \prod\_{j\leq m}\left(1-\exp\left(\frac{2\pi i}p\sum\_{i\leq n} m\_{ij}x\_i\right)\right)=0
$$
for every integral vector $x$.


After expanding all the brackets, we get the equality of the form
$$
 \sum\_k c\_k\xi\_{1k}^{x\_1}\dots \xi\_{nk}^{x\_n}=0,
$$
where $c\_i$ are some (integer) numbers, and $\xi\_{ik}$ are some nonzero complex numbers; after collecting terms, we may assume that all the $n$-tuples $(\xi\_{1k},\dots,\xi\_{nk})$ are distinct. Due to the usual Vandermonde argument, this may happen only if $c\_k=0$ for all $k$. This means, in particulat, that the term $1^m$ cancels with some other term, which has the form
$$
 (-1)^t\prod\_{j\in T}\exp\left(\frac{2\pi i}p\sum\_{i\leq n} m\_{ij}x\_i\right)
 =(-1)^t\prod\_{i\leq n}\left(\exp\left(\frac{2\pi i}p\sum\_{j\in T}m\_{ij}\right)\right)^{x\_i}.
$$
for some $\varnothing\neq T\subseteq \{1,2,\dots,m\}$ with $t=|T|$. This yields that $\sum\_{j\in T}m\_{ij}$ is divisible by $p$ for all $i\leq n$, so the characteristic column of $T$ (taken as $v$) violates the condition imposed on $M$. 


Moreover, one may notice that there is such $T$ with odd cardinality; so we have proved that $v$ may be chosen with odd number of ones in it. 


**ADDENDUM.** The `usual Vandermonde argument' I meant consists in the following. Assume that $(\xi\_{1,k},\dots,\xi\_{n,k})$, $k=1,\dots,K$, are distinct tuples of complex numbers. Then the arrangements $(\xi\_{1,k}^{x\_1}\cdots\xi\_{n,k}^{x\_n})\_{x\_i\in\mathbb Z}$ are linearly independent. The proof goes by the induction on $n$; the base case $n=1$ is classical Vandermonde. For the step of induction, assume the linear dependence, collect the terms with identical $\xi\_{1,k}$ and apply first the hypothesis (to prove that one of the coefficients of $\xi\_{1,k}^{x\_i}$ does not vanish for some choice of $x\_2,\dots,x\_n$) and then the base to finish the step.


