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 '16 at 20:38
  • $\begingroup$ @LucGuyot I think it is true. $\endgroup$ – Sungjin Kim Oct 10 '16 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$ – Gjergji Zaimi Oct 11 '16 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 '16 at 21:34
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 '16 at 19:20
  • $\begingroup$ @IlyaBogdanov It seems that your remark about $T$ having odd cardinality may not hold for $p=2$. $\endgroup$ – Sungjin Kim Oct 11 '16 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$ – Ilya Bogdanov Oct 11 '16 at 19:40
  • $\begingroup$ @FanZheng: See addendum. $\endgroup$ – Ilya Bogdanov Oct 11 '16 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$ – Fedor Petrov Oct 12 '16 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$ – Joao Costalonga Oct 10 '16 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 '16 at 21:17
  • $\begingroup$ Oh, yes! Sorry! I'll fix it. Ended going to the same place as the other answer. $\endgroup$ – Joao Costalonga Oct 10 '16 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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