# integral basis of orthogonal complement

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.

-

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