# Bases for $\Bbb Z^n$ containing a given vector

I am trying to prove the following theorem on finitely generated free abelian groups (which thus for simplicity may be assumed to be $\Bbb Z^n$):

Let $\alpha \in \Bbb Z^n$ be such that for all $k > 1$, $\alpha \notin k \Bbb Z^n$.

Then there exists a basis for $\Bbb Z^n$ containing $\alpha$.

It is easy to see that for $\alpha = (\alpha_1, \ldots, \alpha_n)$ to satisfy the premises, it is necessary and sufficient that $\gcd(\alpha_1, \ldots, \alpha_n) = 1$, since $k \Bbb Z^n = (k \Bbb Z)^n$.

It is also easy to solve the problem if for some $i$, $\alpha_i = 1$.

In general, I have tried to write up some matrix equations (the problem is equivalent to the existence of a matrix $M \in \mathrm{GL}(n, \Bbb Z)$ with first column $\alpha$) but I haven't been able to work it out; there may be an inductive argument possible but if so, I failed to find it.

-
This is maybe a number-theoretic statement : I mean this in the sense that for $n=2$, what you're looking at is you want to find $\ell, m \in \mathbb Z$ such that $$\begin{vmatrix} \alpha_1 & - \ell \\ \alpha_2 & m \\ \end{vmatrix} = m \alpha_1 + \ell \alpha_2 = 1.$$ This condition is equivalent to $(\alpha_1,\alpha_2) = 1$, so you're good. In higher dimension, you want the g.c.d. condition but with the coefficients of the linear combination having a particular structure. If you have done some number theory I suggest you read up a few elementary things (I can't think of one now). – Patrick Da Silva Oct 22 '12 at 9:23
@PatrickDaSilva $\mathrm{GL}(n, \Bbb Z)$ is indeed intimately related to number theory. For $n > 2$, however, I don't know corresponding theorems to the well-known one you indicated. – Lord_Farin Oct 22 '12 at 9:28

This is well-known and there are several proofs. Here is a proof using the classification of finitely generated abelian groups:

Consider $A:=\mathbb{Z}^n / \langle \alpha \rangle$. Since the rank of $\langle \alpha \rangle$ is $1$, the rank of $A$ is $n-1$. One computes that the torsion subgroup of $A$ is trivial. This implies $A \cong \mathbb{Z}^{n-1}$, i.e. we have an exact sequence $0 \to \langle \alpha \rangle \to \mathbb{Z}^n \to \mathbb{Z}^{n-1} \to 0$. Since $\mathbb{Z}^{n-1}$ is free, the sequence splits and we are done.

-
Thank you. Am I correct to observe that the premise on $\alpha$ is necessary to show that the torsion subgroup of $A$ is trivial? – Lord_Farin Oct 22 '12 at 10:13
Yes. All these statements are equivalent: 1) The entries of $\alpha$ are coprime, 2) the quotient $\mathbb{Z}^n / \langle \alpha \rangle$ is torsionfree, 3) this quotient is free, 4) there is a basis containing $\alpha$. – Martin Brandenburg Oct 22 '12 at 10:15

The result is due to Hermite, circa 1850. A more traditional proof appears in $\S 1.3.3$ of these notes on Geometry of Numbers.

I have to say though that I like Martin Brandenburg's proof much better and have already incorporated it into other notes of mine. Notice also that the result holds not just with $\mathbb{Z}$ replaced by any PID (as in the linked notes above) but in fact with $\mathbb{Z}$ replaced by any Bezout domain: an integral domain in which every finitely generated ideal is principal. To carry over Martin's proof one needs only to know that a finitely generated torsionfree module over a Bezout domain is free; for this, see $\S$ 3.9.2 of my commutative algebra notes.

Finally, this condition is related to -- but not exactly the same as -- several conditions on rings which have been studied by Kaplansky and others. Indeed there is such a thing as a Hermite ring. (In fact, unfortunately there are at least three different classes of rings which go by that name, and the relations among them are subtle. I have always found this a bit confusing.)

Added: Probably more helpful than muttering about Hermite rings is to refer to Corollary 3.2 of this (very nice, as always) note of Keith Conrad. The condition on a commutative ring $R$ that $\operatorname{GL}_n(R)$ acts transitively on elements $x \in R^n$ whose coordinates generate the unit ideal is equivalent to: all finitely generated stably free $R$-modules are free. Thus for instance the result holds for polynomial rings in any finite number of indeterminates over a PID by Quillen-Suslin, and it does not hold in any Dedekind domain which is not a PID.

-