How to complete a primitive vector to a unimodular matrix

Question

I would like to understand the following relation between unimodular matrices and its columns in some sense: if $x$ is a primitive vector (that is to say an integer column of $n$ rows whose entries are coprime), then it can be completed to an $n\times n$ unimodular matrix.

In the case of $2 \times 2$ matrices, I can see that it is equivalent to a Bezout relation, but is there a generalisation of this proof to show this property for all $n$?

Answer 1

This may not be what you want, but the completion can be done as follows.

Let $x=x_1$ be the given integer vector. We look for $2n-1$ integer vectors $x_2,\ldots,x_n,y_1,\ldots,y_n$ such that $$ Y^TX=\pmatrix{y_1^T\\ y_2^T\\ \vdots\\ y_n^T}\pmatrix{x_1&x_2&\cdots&x_n} =\pmatrix{1&\ast&\cdots&\ast\\ &1&\ddots&\vdots\\ &&\ddots&\ast\\ &&&1}. $$ Since both $X$ and $Y$ have integer determinants and $\det(Y)\det(X)=\det(Y^TX)=1$, if $X$ and $Y$ do exist, we must have $\det(X)=\pm1$.

We can construct the columns of $X$ and $Y$ by mathematical induction. In the base case, we pick an $y_1$ such that $y_1^Tx_1=1$. This is possible because the GCD of the entries of $x_1=x$ are coprime.

In the inductive step, suppose $1\le k<n$ and $x_1,\ldots,x_k,y_1,\ldots,y_k$ are such that $y_i^Tx_i=1$ for each $i\le k$ and $y_i^Tx_j=0$ whenever $j<i\le k$. Since the rank of $A=\pmatrix{x_1&\cdots&x_k}$ is smaller than $n$, the equation $y_{k+1}^TA=0$ has a nontrivial solution $y_{k+1}\in\mathbb Q^n$. By rationalising the denominators in its entries, $y_{k+1}$ can be chosen as an integer vector. Then by pulling out common factors in its entries, $y_{k+1}$ can be chosen to be primitive. Thus there exists an integer vector $x_{k+1}$ such that $y_{k+1}^Tx_{k+1}=1$ and our proof is complete.

Answer 2

For an integral primitive vector $x=(x_1,\cdots,x_n)$, we can find $u_i\in \mathbb{Z}$ such that $\sum u_i x_i=1$. Now consider the homomorphism $\phi$ from a free abelian group $G$ (with basis $e_1,\cdots, e_n$) to $\mathbb{Z}$, mapping $e_i$ to $u_i\in \mathbb{Z}$. Then $\phi$ is a surjection and admits a section $\mathbb{Z} \to G$, mapping $1\to \mathbb{x}:=\sum x_i e_i$. Therefore, $G$ is isomorphic to $\mathbb{Z} \mathbb{x} \oplus \mathrm{ker} \phi$. Hence $\mathbb{x}$ can be extended to a basis of $G$, as we know that $\mathrm{ker} \phi$ is free and of rank $n-1$.

This new basis of $G$ gives an invertible integral matrix whose first column is $\mathbb{x}$.