# Extending a subset of $\mathbb{Z}^n$ to a basis

Let $v_1,\dots,v_k\in \mathbb{Z}^n$. Is there a nice criterion for the existence of $v_{k+1},\ldots,v_n \in\mathbb{Z}^n$ such that $v_1,\ldots,v_n$ form a basis of $\mathbb{Z}^n$?

For $k=1$, if $v_1 = (a_1,\ldots,a_n)$, it is not hard to see that it is iff $\gcd(a_1,\ldots,a_n)=1$. For bigger $k$ I can find out the answer for specific $v_1,\ldots,v_k$ algorithmically, but I would like to know a general criterion if there is one.

-

Stacking the vectors as a $k$-by-$n$ matrix $M$ with $k\le n$, the condition that the rows extend to a basis is that the gcd of all determinants of $k$-by-$k$ minors be $1$.

Proof: by the structure theorem for finitely-generated modules over a PID, such as $\mathbb Z$, there are $A,B$ integer matrices with integer inverses such that $AMB$ is diagonal. The left-and-right multiplication respects the gcd of minors.

For example, given $(1,0,a,b)$ and $(0,1,c,d)$ with arbitrary $a,b,c,d$ integers, there are $4$-choose-$2$ two-by-two minors, and the very first one is the two-by-two-identity, which has determinant $1$, so this will extend, as we know it does. True, there are other dets of minors, but the very first one gives $1$ already.

-
Do you mean the gcd of all $k$-by-$k$ minors should be 1? Perhaps I am missing something, but suppose n=4, k=2 and the vectors are $v_1 = (1,0,a,b), v_2 = (0,1,c,d)$. I can extend these to a basis (by standard unit vectors) no matter what $a,b,c,d$ are. so there is no restriction on the related minor. Maybe you meant that at least one such minor should have this property? –  KotelKanim Aug 2 '12 at 16:53
@KotelKanim Yes, I meant gcd of determinants of all... I'll edit for clarity. –  paul garrett Aug 2 '12 at 17:03
But then, what is wrong with my example? why it doesn't seem to work? –  KotelKanim Aug 2 '12 at 17:14
The first det of 2-by-2 minor is 1, so no matter what the a,b,c,d are you'll have gcd=1, so it does work. Perhaps I don't understand your intention...? –  paul garrett Aug 2 '12 at 17:21
No, it was I who misunderstood what you were saying. now I see. thank you! –  KotelKanim Aug 2 '12 at 17:28

I don't think there's a quick way, you just have to check if $v_1,...,v_k$ is a basis for $\mathbb{Z}^n$. If not then check if $v_1,...,v_k$ is linearly independent.

-
Presumably, by the way he stated the problem, $k<n$, so $v_1,...,v_k$ is not a basis. Also, $\mathbb Z_n$ is not the same as $\mathbb Z^n$. –  Thomas Andrews Aug 2 '12 at 15:21