Can any set of $n$ relatively prime elements be extended to an invertible matrix?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.