5
$\begingroup$

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.

1 Answers 1

10

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.

  • 0
    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?2012-08-02
  • 0
    @KotelKanim Yes, I meant gcd of determinants of _all_... I'll edit for clarity.2012-08-02
  • 0
    But then, what is wrong with my example? why it doesn't seem to work?2012-08-02
  • 0
    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...?2012-08-02
  • 0
    No, it was I who misunderstood what you were saying. now I see. thank you!2012-08-02