13
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Isn't it true for $p = 2$ (independently of $m$ and $n$) and true if $p > m$ (independently of $n$)? $\endgroup$
    – Luc Guyot
    Commented Oct 10, 2016 at 20:38
  • $\begingroup$ @LucGuyot I think it is true. $\endgroup$ Commented Oct 10, 2016 at 20:53
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Oct 11, 2016 at 16:11
  • 1
    $\begingroup$ @GjergjiZaimi so it's an open-book ten-day math competition in the Internet era when we have mathoverflow? $\endgroup$
    – Fan Zheng
    Commented Oct 11, 2016 at 21:34

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Sorry, but now I find myself can't quite understand the "usual Vandermonde argument". Could you explain it more? $\endgroup$
    – Fan Zheng
    Commented Oct 11, 2016 at 19:20
  • $\begingroup$ @IlyaBogdanov It seems that your remark about $T$ having odd cardinality may not hold for $p=2$. $\endgroup$ Commented Oct 11, 2016 at 19:32
  • $\begingroup$ @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$? $\endgroup$ Commented Oct 11, 2016 at 19:40
  • $\begingroup$ @FanZheng: See addendum. $\endgroup$ Commented Oct 11, 2016 at 19:49
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 12, 2016 at 6:07
4
$\begingroup$

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. $$

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 10, 2016 at 21:43
2
$\begingroup$

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$).

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .