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 2 of 5: Bound one linear form

Previous step Next step

In plain words

Each row contributes only $q^2+1$ possible outputs, no matter how the coefficients are arranged.

-q^2\le\sum_{i=1}^q a_{ji}x_i\le q^2

Detailed analysis

For a fixed row $j$ , the linear form $L_j=\sum_{i=1}^q a_{ji}x_i$ has maximum and minimum differing by at most $q\cdot q=q^2$ : coefficients are in $\{-1,0,1\}$ and each $x_i$ lies in $[0,q]$ . Thus $L_j$ takes at most $q^2+1$ integer values.