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.



integral basis of orthogonal complement
The situation in which we seek a single vector in the orthogonal complement with small entries is addressed by [Siegel's lemma](http://en.wikipedia.org/wiki/Siegel%27s_lemma). Regarding the basis problem, there is a general and very sharp result of [Bombieri and Vaaler](http://link.springer.com/article/10.1007%252FBF01393823) 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$.


