Can any set of $n$ relatively prime elements be extended to an invertible matrix? Say you're given a ordered set of $n$ relatively prime elements, $a_1,\dots,a_n$ in a principal ideal domain $D$. If I relabel these elements $a_{11},\dots,a_{1n}$ in the same order, is it possible to find some remaining $a_{kj}$ in $D$ such that $(a_{kj})$ is an invertible $n\times n$ matrix over $D$?
 A: We can prove this by induction. For $n=1$, the set $\{a_1\}$ is relatively prime if and only if $a_1$ is a unit, and thus $(a_{11})$ is invertible.
So assume that we can extend any set of $n$ relatively prime elements to an invertible matrix, and let $n+1$ relatively prime elements $a_1,\dotsc,a_{n+1}$ be given. Let $g=\gcd(a_1,\dotsc,a_n)$. Then we can write $a_i=gb_i$ for $1\le i\le n$, with the $b_i$ relatively prime, and we can extend the $b_i$ to an invertible $n\times n$ matrix $B$. If we multiply the first row of $B$ by $g$, we can place it into the upper left $n\times n$ block of the matrix $A$ to be constructed, and we'll have $a_i=gb_i$ in the right place for $1\le i\le n$. Now place a multiple of the first row of $B$ into the $n+1$-th row of $A$, with the multiplier $r$ yet to be determined, and fill the $n+1$-th column with zeros except for the first and last elements $a_{n+1}$ and $s$, with $s$ yet to be determined. Now the determinant of the upper left $n\times n$ block is $g\det B$, and the determinant of the lower left $n\times n$ block is $(-1)^{n+1}r\det B$, so by Laplace expansion the determinant of the entire matrix $A$ is
$$\det A=sg\det B+ a_{n+1}r\det B=(sg+ ra_{n+1})\det B\;.$$
Since $a_1,\dotsc,a_{n+1}$ are relatively prime, $g$ and $a_{n+1}$ are relatively prime. Thus we can choose $r$ and $s$ such that the expression in parentheses is $1$ and $\det A = \det B$. But a matrix over a commutative ring is invertible if and only if its determinant is invertible (see Do these matrix rings have non-zero elements that are neither units nor zero divisors? and necessary and sufficient condition for trivial kernel of a matrix over a commutative ring). Thus, since $B$ is invertible, $A$ is invertible.
A: There is much written on this and related problems, e.g. it is the special case $\rm\:k=1\:$ of below.
MR 82k:15013
Gustafson, William H.; Moore, Marion E.; Reiner, Irving
Matrix completions over Dedekind rings.
Linear and Multilinear Algebra 10 (1981), no. 2, 141--144.
Let  d  be any element of the ideal generated by the  k by k  minors of a
k by n  matrix  M  over a Dedekind domain  R . The authors show that  M can 
be "completed" to form the top  k  rows of some invertible  n by n matrix of
determinant  d .
In fact, their proof works if  R  is any Prufer domain whose finitely generated
ideals can be generated by  $\ 1\ 1/2\ $ elements; merely precede their lemma by the
proof of the formula $\rm\  A \oplus B \cong R \oplus AB\ $  given in Theorem 4.1 of R. C. Heitmann
and the reviewer [Rocky Mountain J. Math. 5 (1975), 361--373; MR 52 #3141].  
Reviewed by Lawrence S. Levy
                   91k:15028 
A: This follows from the structure theorem of finitely generated modules over a principal ideal domain. 
Consider your $n$-tuple $(a_1,\dots,a_n)$ as an element $a$ of the module $D^n$ over $D$, and form the quotient module $Q=D/\langle a\rangle$. It is clearly a finitely generated module over $D$ (since $D^n$ is), and the hypothesis $\gcd(a_1,\dots,a_n)=1$ means that the quotient $Q$ is torsion-free, since the order $d\in D$ (generator of the annihilator) of any torsion element would be is a common divisor of $a_1,\dots,a_n$. By the structure theorem, $Q$ is therefore a free module over $D$. If $[\overline b_1,\ldots,\overline b_k]$ is a basis for $Q$, consisting of images of elements $b_i\in D^n$, then $[a,b_1,\ldots,b_k]$ forms a basis of $D^n$. Since the rank of a free module is well defined one has $k=n-1$, and the $b_i$ are a possible choice for the remaining rows of your matrix.
