# Can you complete a basis in polynomial time?

Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ bits to describe. We would like to find vectors $v_{k+1}, \ldots, v_n$ such that $v_1, \ldots, v_n$ is an orthogonal basis for $\mathbb{R}^n$.

I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. My question is to provide a proof that this can indeed be done in polynomial time.

Here is where I am stuck. Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v_1, \ldots, v_l$. Take the basis vectors $e_1, \ldots, e_n$, go through them through them one by one, and if some $e_i$ is not in the span of the $v_1, \ldots, v_l$, then set $v_{l+1} = P_{{\rm span}(v_1, \ldots, v_l)^\perp} e_i$ (here $P$ is the projection operator). Repeat.

This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e_i$ onto, say, $v_1$ may have denominators which need $2K$ bits or more to describe - because $P_{v_1}(e_i)$ is $v_1$ times its $i$'th entry, divided by $||v_1||$. Just $v_1$ times its $i$'th entry may already need $2K$ bits to describe.

By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?

The result of the Gram-Schmidt can be expressed in determinantal form, see Wikipedia. This shows that the output of the Gram-Schmidt process is polynomial size. This suggests that if you run the classical Gram-Schmidt process, then all intermediate entries are also polynomial size (even in LLL, all intermediate entries are polynomial size). However, even if it is not the case, then using efficient algorithms for computing the determinant (see my other answer), you can compute the Gram-Schmidt orthogonalization in polynomial time.

Edit: This answer doesn't address the requirement of orthogonality. Perhaps the Bareiss algorithm still helps.

Let $V$ be a matrix whose rows are $v_1,\ldots,v_\ell$. Convert $V$ to row echelon form, say $PVP^{-1} = [I|A]$, using the Bareiss algorithm. Continue from there. (There are other alternatives using the same general idea.)

If you used Gaussian elimination instead, then intermediate entries could have exponential size, but the Bareiss algorithm avoids this somehow.

Edit: Here is a practical suggestion. Add random vectors - if you do it in a reasonable way, then it is very probably that the result will be a basis. You could even check whether you get a basis by computing the determinant. The latter can be done in many ways, see for example a survey by Rote, or you can compute the determinant modulo $p$ for "random" $p$ - if the result is non-zero (which it probably will), you know you got a basis.

• Can you elaborate on "continue from there?" What is the next step after the matrix is in row echelon form? – robinson Mar 30 '13 at 5:33
• Complete the echelon form into a basis (easy) and then apply $P$ in reverse. – Yuval Filmus Mar 30 '13 at 12:05
• But I need an orthogonal basis. It seems to me the resulting basis will not be orthogonal. – robinson Mar 30 '13 at 17:35
• Ah - I missed that. – Yuval Filmus Mar 30 '13 at 19:26