Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a vector $a_1=(k_1,\ldots,k_n)^T$ of coprime integers. Are there $a_2,\ldots,a_n \in \mathbb{Z}^n$ such that that the matrix $A := (a_1,\ldots,a_n) \in \mathbb{Z}^{n \times n}$ is regular, i.e. $A \in GL_n(\mathbb{Z})$ ?

In case $n=2$ this is true because there are integers $l_1,l_2$ s.t. $k_1l_1 + k_2l_2 = 1$. Then $a_2=(-l_2 , l_1)^T$ will do.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Solution from "Problems From The Book":

Yes, by induction. Let $g= \gcd(k_1,\dots,k_{n-1})$, and do it for $k_1/g, \dots, k_{n-1}/g$, call this matrix $A'$.

Add to $A'$ the following row: $(k_n /g , 0, \dots ,0)$. (almost all zeroes)

$g$ must be coprime to $k_n$, so we can find integers $x,y$ such that $xg+yk_n = 1$. Now add it the following column: $(yk_1,yk_2, \cdots, y k_{n-1}, xg)^{T}$. (almost proportional to first column)

It can be verified that the matrix has determinant $\pm 1$. To make the entries integral, multiply the first column by $g$ and divide the last column by $g$.

share|improve this answer
    
I think you have to choose $xg-yk_n=1$ if $\det(A')=1$. Anyway, that's a clever construction. Thanks. –  tj_ Aug 16 '12 at 21:20
    
To make the construction easier to understand, write $A' = (b_{ij})$ where $b_{i,1}=k_i/g$. Then the matrix in the penultimate step is $$C=\begin{pmatrix} k_1/g & b_{12} & \cdots & b_{1,n-1} & yk_1 \\ \vdots & \vdots & & \vdots & \vdots \\ k_{n-1}/g & b_{n-1,2} & \cdots & b_{n-1,n-1} & yk_{n-1} \\ k_n/g & 0 & \cdots & 0 & xg \end{pmatrix}.$$ –  tj_ Aug 16 '12 at 21:20

You should have specified which sense of coprime you mean: no nontrivial common factor to all at once or no nontrivial common factor to at least two of them. However the answer is "yes" even under the weaker former interpretation of the hypothesis.

More generally a set of independent elements of $\mathbb Z^n$ can be completed to a $\mathbb Z$-basis if the lattice of their $\mathbb Z$-linear combinations is saturated: $\mathbb Z^n$ contains no other rational linear combinations of them. Any saturated lattice is a direct factor of $\mathbb Z^n$, and one can complete the basis by choosing a complementary factor, and a basis of that. In the case of one vector, the weak coprime condition precisely means the rank $1$ lattice it spans is saturated.

The mentioned property can be proved by the Smith normal form for the inclusion map sending $\mathbb Z^r\to\mathbb Z^n$ where $r$ is the rank of the saturated sublattice; the saturated condition means there are no invariant factors greater than $1$.

share|improve this answer
    
By coprime I mean: $\forall g \in \mathbb{Z}: g \mid k_1 \wedge ... \wedge g \mid k_n \Rightarrow g = \pm 1$. –  tj_ Aug 16 '12 at 21:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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