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.


1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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