Extending an element in generating set for free abelian group

Question

Let $G$ be a finitely generated free abelian group and $S$ be a minimal generating set i.e. ${\rm rank}(G)=|S|$. If $w$ is a word in $G$ then when it can be extended in a new minimal generating set for $G$? For example if $S=\{s_{1},s_{2}\}$ then $s^{n}$ can not be extended in a new generating set while $w=s^{3}_{1}s^{2}_{2}$ can. Intuitively, I would argue that we should be able to solve for one of the generators. Is this true?

Answer 1

As has been noted in the comments, there is some linear algebra going on under the hood. That is maybe a hint that we should view this problem geometrically. To that end, I'll be calling elements of this group "vectors", and thinking of them as living in some integer lattice of $\mathbb{R}^n$. Indeed, these kinds of questions arise very naturally in the geometry of numbers.

We say a set of vectors $\{v_1, \ldots, v_i \}$ is primitive exactly when it can be extended to a basis of the lattice. So in this problem we are interested in knowing when $\{ w \}$ is primitive.

If we write $w = g_1^{n_1} g_2^{n_2} \cdots g_k^{n_k}$ in terms of the "natural" basis $\{ g_1, \ldots, g_k \}$, there turns out to be a nice combinatorial description of primitivity:

$w = g_1^{n_1} g_2^{n_2} \cdots g_k^{n_k}$ is primitive if and only if $\text{gcd}(n_1, \ldots, n_k) = 1$.

A nice computational proof can be found as Theorem $2.1$ in Magliveras, van Trung, and Wei's "Primitive Sets in a Lattice" (see here).

This turns out to be related to the comment about finding a matrix whose determinant is $\pm 1$. Indeed, the proof in the above article works by cleverly using bezout's lemma to take a (row) vector $w = (n_1, \ldots, n_k)$ and find $k-1$ new (row) vectors $v_2, \ldots, v_k$ so that when we assemble these vectors into a matrix, we find

$$ \text{det} \begin{pmatrix} - w - \\ - v_2 - \\ \vdots \\ - v_k -\end{pmatrix} = \text{gcd}(n_1, \ldots, n_k) $$

When $\text{gcd}(n_1, \ldots, n_k) = 1$ this matrix has determinant $1$, and thus is invertible as an integer matrix. But this is exactly what it means for your rows to be a basis. The linked article is nice because it shows you what the other basis elements are too.

---

I hope this helps ^_^