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

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{)}$?

• Isn't it true for $p = 2$ (independently of $m$ and $n$) and true if $p > m$ (independently of $n$)? – Luc Guyot Oct 10 '16 at 20:38
• @LucGuyot I think it is true. – Sungjin Kim Oct 10 '16 at 20:53
• I just remembered where this question is from: Problem 2 in the 2003 Miklos Schweitzer exam. The official solution is essentially the same as Ilya's. – Gjergji Zaimi Oct 11 '16 at 16:11
• @GjergjiZaimi so it's an open-book ten-day math competition in the Internet era when we have mathoverflow? – Fan Zheng Oct 11 '16 at 21:34

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.

• Sorry, but now I find myself can't quite understand the "usual Vandermonde argument". Could you explain it more? – Fan Zheng Oct 11 '16 at 19:20
• @IlyaBogdanov It seems that your remark about $T$ having odd cardinality may not hold for $p=2$. – Sungjin Kim Oct 11 '16 at 19:32
• @i707107: I do not see why. The exponents may cancel only if the $n$-tuples $(\xi_1,\dots,\xi_n)$ coincide, and this cancellation happens in $\mathbb C$, not anywhere else. So what's special for $p=2$? – Ilya Bogdanov Oct 11 '16 at 19:40
• @FanZheng: See addendum. – Ilya Bogdanov Oct 11 '16 at 19:49
• We could finish also as follows: sum up our identity over the grid $\{0\leqslant x_1,\dots,x_n\leqslant p-1\}$. Each non-constant monomial sums up to 0, thus the total sum is not 0, a contradiction. – Fedor Petrov Oct 12 '16 at 6:07

This is a proof of @LucGuyot 's statement:

For $p=2$, the assumption is linear independence of $m$ columns. Thus, $M$ has column rank $m$. Also, it has row rank $m$. In particular $n\geq m$, otherwise $\mathrm{rank}M=m$ is impossible. For any nonzero $w\in\mathbb{F}_2^m$, there is $x\in\mathbb{F}_2^n$ such that $x M = w$.

For $p>m$, consider the vectors $v_1=Me_1$, $\ldots$, $v_m=Me_m$, where $e_i$ is a column vector which has $1$ on $i$-th entry and $0$ otherwise. By assumption, these vectors $v_1, \ldots, v_m$ are nonzero. Thus, their orthogonal complement $(\mathbb{F}_p v_i)^{\perp}$ is $n-1$-dimensional over $\mathbb{F}_p$. But, we have $$|\cup_{i=1}^m (\mathbb{F}_p v_i)^{\perp}|\leq m p^{n-1}.$$ If we choose $x\in \mathbb{F}_p^n - \cup_{i=1}^m (\mathbb{F}_p v_i)^{\perp}$, then for each $1\leq i\leq m$, $$xMe_i \neq 0.$$ Choosing $x$ is possible in case $p>m$ because $$p^n - mp^{n-1} = p^{n-1}(p-m) >0.$$

• The first bound may be improved to prove it also in the case that $p=m$. I'll call by $H_i$ the othogonal complement, of v_i. $$|H_1\cup\dots\cup H_m|=|H_1\cup(H_2-H_1)\cup\dots\cup(H_m-H_1)|\le p^{n-1}+(m-1)(p^{n-1}-p^{n-2})$$ From this point, the proof goes analogously. – Joao Costalonga Oct 10 '16 at 21:43

It can be reduced to the case that $m\ge p+1$.

I think it is more natural to think about the filed $F$ with $p$ elements instead of the integers. Let $H_i$ be the orthogonal complement of the comlumn $i$ relativelly to the dot product. As each column must be different from zero, then each $H_i$ is an hyperplane of $F^n$. If $xM$ has a zero entry for all $x\in F^n$, then $F^n=H_1\cup\cdots\cup H_m$ and, therefore, $m\ge p+1$ (Indeed, pick an affine line $L$ parallel to $H_m$, we have for each $i$, $|H_i\cap L|\le 1$ and $|H_1\cap L|+\cdots|H_{m-1}\cap L|\ge |L|=p$).

• Isn't the cardinal of a line in $F_p^n$ equal to $p$? – Luc Guyot Oct 10 '16 at 21:17
• Oh, yes! Sorry! I'll fix it. Ended going to the same place as the other answer. – Joao Costalonga Oct 10 '16 at 21:23