Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
4  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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