# Integral solutions for linear equations

For $2n^2$ numbers ${a_{ij}} \in \{ 0,1, - 1\}$ $1 \le i \le n,{\kern 1pt} {\kern 1pt} 1 \le j \le 2n$. Please show that the linear system of equations:

$\left( {\begin{array}{*{20}{c}} {{a_{11}}} & \ldots & {{a_{1,2n}}} \\ \vdots & \ddots & \vdots \\ {{a_{n1}}} & \cdots & {{a_{n,2n}}} \\ \end{array}} \right)\left( \begin{array}{l} {x_1} \\ \vdots \\ {x_{2n}} \\ \end{array} \right) = 0$

has a set of integral solution $c_i$ , $1 \le i \le 2n$ such that not all $c_i$ are $0$ and $\left| {{c_i}} \right| \le n$.

-
First you have $x_i$, and then you have $c_i$? What do you really want? Note that your system is underdetermined... – J. M. Oct 26 '11 at 4:33
@J.M. It's sort of crucial that the problem is underdetermined. Since the system has fewer variables than equations, there's definitely a nontrivial solution. Since the system involves only rational coefficients, there's a rational solution as well, which can also be made integral by simple scaling. ($\langle c_i \rangle_{i =1}^n$ is one such integral solution, I guess.) The main part of the problem is that we should now show that there is an integral solution whose coordinate-entries are all small (i.e., bounded by $n$). – Srivatsan Oct 26 '11 at 4:47