# How to complete a primitive vector to a unimodular matrix

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

• This is equivalent to saying that the unimodular matrices act transitively on the integer "unit sphere" (the primitive vectors). If we know that any $x$ with GCD$(x)=1$ can be completed to a matrix $X$ with $|\det X|=1$, then given $x$ and $y$, we can define $A=YX^{-1}$ so that $AX=Y$ and, by selecting one column of this equation, $Ax=y$. Conversely, if we know that any primitive pair $x,y$ can be related by $Ax=y$ with $A$ unimodular, then we can take $y=[1,0,\cdots,0]^T$ so that $x=A^{-1}y$, which says that $x$ is the leftmost column of $A^{-1}$. – mr_e_man Jan 2 at 12:47

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 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. 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.
• Can one further impose that the vectors $x_i$ for $i=2,\ldots,n$ are orthogonal to $x$ and still find a solution? – jj_p Nov 16 at 16:10
• @jj_p No. E.g. if $\pmatrix{2&a\\ 3&b}$ is unimodular and it has orthogonal columns, then $2b-3a=\pm1$ and $2a+3b=0$. Hence $2(-2a/3)-3a=\pm1$, i.e. $a=\pm3/13\not\in\mathbb Z$. – user1551 Nov 16 at 18:07