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
    Oct 10, 2016 at 20:38
  • $\begingroup$ @LucGuyot I think it is true. $\endgroup$ 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$ 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
    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
    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$ 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$ Oct 11, 2016 at 19:40
  • $\begingroup$ @FanZheng: See addendum. $\endgroup$ 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$ 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$ 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
    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$ Oct 10, 2016 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.