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.