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?

  • 1
    $\begingroup$ 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. $\endgroup$ – William Apr 1 '12 at 17:48

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.

  • $\begingroup$ 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$? $\endgroup$ – user2468 Apr 1 '12 at 18:28
  • $\begingroup$ @J.D. We want $u\in\Bbb{Z}^n$ no? $\endgroup$ – anon Apr 1 '12 at 18:46
  • $\begingroup$ 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. $\endgroup$ – user2468 Apr 1 '12 at 18:48
  • 1
    $\begingroup$ @J.D. Does going back the way you came and then invoking Bezout's not count as a derivation? :P $\endgroup$ – anon Apr 1 '12 at 18:54

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


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.