Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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

You may be able to use Siegel's Lemma.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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