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.

Suppose we have $n-1$ linearly independent vectors $a_1, \ldots,a_{n-1} \in \mathbb{Z^n}$. Is it possible to find another vector $a_n\in \mathbb{Z^n}$ such that the determinant of the matrix $M$ whose row vectors are $a_1,\ldots,a_n$ is 1?

share|improve this question
1  
For $1\leq n-1$ let $a_i\in\mathbb{Z}^n$ be the vector with $2$ in the $i$-th position and $0$ everywhere else. Can you find an $a_n$ in this case? Why or why not? Also, note for the sake of intuition: the determinant of a matrix (aka linear transformation) can be interpreted as the volume of the image of the unit cube. –  you Apr 1 '12 at 17:48

2 Answers 2

up vote 3 down vote accepted

Let $\rm M_k$ be the matrix formed by cutting out the $\rm k$th column of the $\rm a_i$ row vectors and putting them together. Then the condition that $\rm \det M=1$ imposed on $\rm \vec{v}=a_n$ is equivalent to

$$\rm (\det M_1)\,v_1-(\det M_2)\,v_2+\cdots\pm (\det M_n)\,v_n=1.$$

By Bezout's lemma, this has a solution in $\rm \vec{v}$ if and only if $\rm \gcd(\det M_1,\cdots,\det M_n)=1$.

This is not always the case. Take e.g. in $\rm n=3$, with $\rm v,w\ne0$ and $\rm u\ne0,\pm1$,

$$\rm a_1^T=\begin{pmatrix}u \\ 0 \\ \rm v\end{pmatrix} \quad and \quad a_2^T=\begin{pmatrix} 0 \\ \rm u \\ \rm w \end{pmatrix}$$

where we have $\rm \gcd(\det M_1, \det M_2,\det M_3)=\gcd(-uv,uw,u^2)\ne 1$. More generally, for arbitrary $\rm n$ following you's suggestion, let $\rm a_i=x_i\,\vec{e}_i$ with $\rm \gcd(x_1,\cdots,x_n)\ne1$. The resulting matrix will be diagonal, so its determinant is the product of the diagonal entries, which must be $>1$ in magnitude if any of the $\rm x_i$ are.

share|improve this answer
    
Follow up question: We can rewrite the constraint as $$({\rm det}M_1\quad -{\rm det}M_2\quad \ldots \quad \pm {\rm det} M_n \quad -1) \begin{pmatrix}v_1 \\ v_2 \\ \vdots\\v_n \\ 1\end{pmatrix}= 0,$$ or $Mu = 0.$ Since ${\rm rank}(M^{T}M) = 1,$ the nullity $> 0.$ Can't we solve $M^{T}M u = 0$ for $u$ (i.e. finding the nullspace basis of $M^{T}M$ and forming $u$)? Or is the fact the last entry in $u$ is $1,$ put conditions on finding $u$? –  user2468 Apr 1 '12 at 18:28
    
@J.D. We want $u\in\Bbb{Z}^n$ no? –  anon Apr 1 '12 at 18:46
    
Yes. Indeed $u \in \mathbb{Z}^{n}$. My source of confusion: I can not derive the condition $\gcd({\rm det}M_1,\ldots,{\rm det}M_n) = 1$ from my formulation. –  user2468 Apr 1 '12 at 18:48
1  
@J.D. Does going back the way you came and then invoking Bezout's not count as a derivation? :P –  anon Apr 1 '12 at 18:54

Hint $a_1=(2,2,2,..., 2)$.

share|improve this answer

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.