Problem 5

Consider the system of

p

equations in

q=2p

unknowns

x_1,\ldots,x_q

, with every coefficient

a_{ij}

\{-1,0,1\}

. Prove that the system has a solution such that (a) all

x_j

are integers; (b) at least one

x_j\ne0

; (c)

|x_j|\le q

for every

j

Step 5 of 5: Apply the pigeonhole principle

Previous step Next step

In plain words

Subtracting two bounded nonnegative candidates is the standard way to obtain a signed, nontrivial integer kernel vector without exceeding the same bound.

x=y-y\ne0,\quad |x_j|\le q

Detailed analysis

More nonzero vectors map to fewer output tuples, so two distinct vectors $u,v$ have the same image. Their difference $x=u-v$ is a nonzero integer vector, satisfies every equation because the outputs cancel, and obeys $|x_j|\le q$ since $0\le u_j,v_j\le q$ . This proves all three required properties.