# Is a vector of coprime integers column of a regular matrix?

Given a vector $a_1=(k_1,\ldots,k_n)^T$ of coprime integers. Are there $a_2,\ldots,a_n \in \mathbb{Z}^n$ such that that the matrix $A := (a_1,\ldots,a_n) \in \mathbb{Z}^{n \times n}$ is regular, i.e. $A \in GL_n(\mathbb{Z})$ ?

In case $n=2$ this is true because there are integers $l_1,l_2$ s.t. $k_1l_1 + k_2l_2 = 1$. Then $a_2=(-l_2 , l_1)^T$ will do.

-

Solution from "Problems From The Book":

Yes, by induction. Let $g= \gcd(k_1,\dots,k_{n-1})$, and do it for $k_1/g, \dots, k_{n-1}/g$, call this matrix $A'$.

Add to $A'$ the following row: $(k_n /g , 0, \dots ,0)$. (almost all zeroes)

$g$ must be coprime to $k_n$, so we can find integers $x,y$ such that $xg+yk_n = 1$. Now add it the following column: $(yk_1,yk_2, \cdots, y k_{n-1}, xg)^{T}$. (almost proportional to first column)

It can be verified that the matrix has determinant $\pm 1$. To make the entries integral, multiply the first column by $g$ and divide the last column by $g$.

-
I think you have to choose $xg-yk_n=1$ if $\det(A')=1$. Anyway, that's a clever construction. Thanks. – tj_ Aug 16 '12 at 21:20
To make the construction easier to understand, write $A' = (b_{ij})$ where $b_{i,1}=k_i/g$. Then the matrix in the penultimate step is $$C=\begin{pmatrix} k_1/g & b_{12} & \cdots & b_{1,n-1} & yk_1 \\ \vdots & \vdots & & \vdots & \vdots \\ k_{n-1}/g & b_{n-1,2} & \cdots & b_{n-1,n-1} & yk_{n-1} \\ k_n/g & 0 & \cdots & 0 & xg \end{pmatrix}.$$ – tj_ Aug 16 '12 at 21:20

You should have specified which sense of coprime you mean: no nontrivial common factor to all at once or no nontrivial common factor to at least two of them. However the answer is "yes" even under the weaker former interpretation of the hypothesis.

More generally a set of independent elements of $\mathbb Z^n$ can be completed to a $\mathbb Z$-basis if the lattice of their $\mathbb Z$-linear combinations is saturated: $\mathbb Z^n$ contains no other rational linear combinations of them. Any saturated lattice is a direct factor of $\mathbb Z^n$, and one can complete the basis by choosing a complementary factor, and a basis of that. In the case of one vector, the weak coprime condition precisely means the rank $1$ lattice it spans is saturated.

The mentioned property can be proved by the Smith normal form for the inclusion map sending $\mathbb Z^r\to\mathbb Z^n$ where $r$ is the rank of the saturated sublattice; the saturated condition means there are no invariant factors greater than $1$.

-
By coprime I mean: $\forall g \in \mathbb{Z}: g \mid k_1 \wedge ... \wedge g \mid k_n \Rightarrow g = \pm 1$. – tj_ Aug 16 '12 at 21:32