# 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$?

• In a more general setting, this became known as Serre's problem, and later the Quillen-Suslin Theorem. – Gerry Myerson Oct 28 '11 at 22:23
• @Gerry: Can you indicate how this is related to Quillen-Suslin? – Soarer Oct 29 '11 at 4:38
• @Soarer, sorry, it's a bit out of my depth. Some statements of the problem/theorem don't look anything like Aria's qiestion, but if you type Quillen Suslin matrix into a search engine you will probably find some references that bring out the relation. – Gerry Myerson Oct 29 '11 at 8:17
• @Soarer, Here's a reference: Moshe Roitman, Completing unimodular rows to invertible matrices, J. Algebra 49 (1977), no. 1, 206–211, MR0453779 (56 #12033). From the review: Quillen's solution of Serre's problem implies that if $R$ is a commutative ring, then any unimodular row over $R[x]$ which contains a unitary polynomial is completable to an invertible matrix. The author shows.... Other related results on this completion problem are discussed. – Gerry Myerson Oct 31 '11 at 6:11

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.

• In the formula for $\det A$, the two plus signs should be minus signs, which is easily seen for the case where $A$ is a $2 \times 2$ matrix. For the general case, $\det A = (-1)^{n + 1 + n + 1}sg\det B + (-1)^{1 + n + 1}a_{n + 1}(-1)^{n + 1}r \det B = (sg - ra_{n + 1})\det B$. Of course, the signs of $sg$ and $ra_{n + 1}$ do not affect the validity of the proof. – Maurice P Dec 16 '16 at 17:20

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.

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