A difficult integer matrix problem

89 Views Asked by At

$A$ is an integer matrix with size $m \times n$ and $p$ is a prime. Suppose for any non-zero vector $x_{n \times 1}$ with $x_i= 0 \text{ or } 1$, $Ax \neq 0_{m \times 1} \text{ mod } p$. Prove there exists a vector $y_{m \times 1}$ satisfying that: for $z=A^Ty $, all $z_i \neq 0 \text{ mod }p$ $(i =1,...,n)$.

1

There are 1 best solutions below

3
On

These are my thoughts so far, it's not a complete answer.

We look at $A\mod p$ instead of $A$ without loss of generality. This makes sure every element of $A$ is in $\{0,1,\cdots,p-1\}$.

First of all, note that, if not every row of $A$ contains a $0$, then not every column of $A^T$ contains a $0$ (let's say that's the $i$th column), and as such, we pick $y$ to be the $m\times 1$ zero-matrix, but with a $1$ at the the $i$th index. It is clear that then all elements of $A^Ty$ are nonzero.

Thus, we may assume every row of $A$ contains a $0$.