MathOverflow is a question and answer site for professional mathematicians. 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

Suppose there are $r$ linearly independent vectors $v_1,\dots,v_r\in \mathbb{R}^n$, all of them have integer-valued entries and $\|v_i\|_\infty\leq m$ for some integer $m$.

My goal is to find an integral basis $w_1,\dots,w_{n-r}$ in the orthogonal complement to $\text{span}(v_1,\dots,v_r)$, such that $\max_i \|w_i\|_\infty$ is small.


I think we can bound $\max_i \|w_i\|_\infty \leq (mr)^{O(r)}$.

Put $v_1,\dots,v_r$ as row vectors of some matrix. Reduce this matrix to the row echelon form $(I_r\ \ A)$, where $I_r$ is the $r\times r$ identity matrix and $A$ is a rational matrix. Then form an $(n-r)\times n$ matrix $(A^T\ \ -I_{n-r})$, and the rows of this matrix form a basis of the orthogonal complement of $\text{span}(v_1,\dots,v_r)$. We can then scale it to an integer matrix.

As we do not perform any column operations, so the bound on both denominators and numerators in $A$ should be independent of $n$. I think both are bounded by $(mr)^{O(r)}$, so the entries in the basis $\{w_i\}$ are bounded by $(mr)^{O(r)}$.


Question: is this bound tight? Since a basis of the orthogonal complement is not necessarily obtained in this way via reduced row echelon form, I am wondering what a good bound is.

share|cite|improve this question
up vote 3 down vote accepted

The situation in which we seek a single vector in the orthogonal complement with small entries is addressed by Siegel's lemma. Regarding the basis problem, there is a general and very sharp result of Bombieri and Vaaler that states:

Theorem: Let $\sum_{n=1}^{N}a_{m,n} x_n =0$ ($m=1,2,\ldots, M$) be a linear system of $M$ linearly independent equations in $N > M$ unknowns with rational integer coefficents $a_{m,n}$. Then there exists $N-M$ linearly indepdent integral solutions $v_{i}=(v_{i,1},v_{i,1},\ldots, v_{N,i}) $ ($1\leq i \leq N-M$) such that $ \prod_{i=1}^{N-M} \max_{n} | v_{i,n}| \leq D^{-1} \sqrt{|det( A A^{t})| } $ where $A$ denotes the $M \times N$ matrix $A=(a_{m,n})$ and $D$ is the greatest common divisor of the determinants of all $M\times M$ minors of $A$.

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.