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
    No, it was I who misunderstood what you were saying. now I see. thank you!2012-08-02