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

  • 1
    $\begingroup$ 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}$. $\endgroup$ – mr_e_man Jan 2 at 12:47

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.

| cite | improve this answer | |
  • $\begingroup$ Can one further impose that the vectors $x_i$ for $i=2,\ldots,n$ are orthogonal to $x$ and still find a solution? $\endgroup$ – jj_p Nov 16 at 16:10
  • 1
    $\begingroup$ @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$. $\endgroup$ – user1551 Nov 16 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.