Let $n \geq 2$. Let $a_1, a_2, \ldots, a_n$ be $n$ integers such that $\gcd\left(a_1, a_2, \ldots, a_n\right) = 1$. Prove that there exists a matrix in $\operatorname{SL}_n\left(\mathbb{Z}\right)$ whose first row is $\left(a_1, a_2, \ldots, a_n\right)$.

Since the gcd of the integers $a_1,\ldots, a_n$ is $1$, there exists weights $x_i \in \mathbb{Z}$ such that $a_1x_1+\cdots+ a_nx_n=1$. My two ideas are (a) to brute force construct an $n\times n$ matrix with first row $a_1,\ldots ,a_n$ and to construct the remaining rows such that the determinant is $\sum a_ix_i=1$ or (b) to use induction.

(a) (Constructive) This is tedious since once I find a way to construct the remaining $n-1$ rows to ensure that $a_1x_1$ appears in the determinant, I am not sure how to modify these $n-1$ rows to ensure that only the terms $a_ix_i$ appear in the cofactor expansion. If such a matrix exists, I'd like to see it.

(ii) (Non-constructive) If I proceed by induction then the base case $n=2$ is settled since I can choose the 2nd row to be $-x_2, x_1$ so that the determinant is $a_1x_1-a_2(-x_2)=1$. However, I'm not sure how to use the inductive hypothesis to show that if I can construct such an $n\times n$-matrix then I can construct an $\left(n+1\right) \times \left(n+1\right)$-matrix with the desired property. In particular, if the gcd $(a_1,\ldots ,a_{n+1})$ is $1$, it is not necesarry that the gcd of any $n$ of these terms is $1$, so induction may not even apply here.

How can I construct such a matrix or prove that one exists (without necessarily constructing it)?

  • $\begingroup$ Hint: Prove the following more general statement by induction. For any integers x_1,..., x_n with gcd d, there exist A, B in gl_n(Z) such that the first row of A is x_1,..., x_n and AB=diag(d,1,1,...,1). $\endgroup$ – stewbasic Jun 20 '16 at 23:35
  • 1
    $\begingroup$ If one wants a proof by induction, I suspect we will need to prove that if $\gcd(a_1,\cdots,a_n)=d$, there is an integer matrix with determinant $d$ whose first row is $a_1,\dots,a_n$. $\endgroup$ – André Nicolas Jun 20 '16 at 23:44

Suppose the statement holds for $n\geq2$, and consider integers $a_1,\ldots,a_{n+1}$ whose GCD is $1$. Let $d=\gcd(a_1,a_2,\ldots,a_n)$, and let $a_i'=a_i/d$ for $i\leq n$. Note that $$ 1=\gcd(a_1,\ldots,a_{n+1})=\gcd(d, a_{n+1}) $$ and $$ 1=\gcd(a_1',\ldots,a_n'). $$ By induction, there are matrices $X\in SL_2(\mathbb Z)$ and $Y\in SL_n(\mathbb Z)$ whose first rows are $(d, a_{n+1})$ and $(a_1',\ldots,a_n')$ respectively. Let $$ X=\begin{pmatrix}d&a_{n+1}\\ p&q\end{pmatrix}. $$ Also consider the $1\times n$ row matrix $v=\begin{pmatrix}p&0&\ldots&0\end{pmatrix}$ and the $n\times 1$ column matrix $w=\begin{pmatrix}a_{n+1}&0&\ldots&0\end{pmatrix}^T$. Let $D$ be the $n\times n$ diagonal matrix with diagonal $(d,1,\ldots,1)$. Let $$ Z=\begin{pmatrix}DY&w\\ vY&q\end{pmatrix}. $$ Note that the first row of $Z$ is $(a_1,\ldots,a_{n+1})$. Also $$\begin{eqnarray*} Z\begin{pmatrix}Y^{-1}&0\\ 0&1\end{pmatrix} &=&\begin{pmatrix}D&w\\ v&q\end{pmatrix}\\ &=&\begin{pmatrix}d&0&a_{n+1}\\0&I&0\\ p&0&q\end{pmatrix}. \end{eqnarray*}$$ Since $X$ is invertible over $\mathbb Z$, so is the RHS, and so is $Z$. Thus $\det(Z)=\pm1$, and we get the required matrix by flipping the sign of one row of $Z$ if necessary.

  • $\begingroup$ The case $d = 0$ needs extra care. $\endgroup$ – darij grinberg Apr 29 '19 at 3:36
  • $\begingroup$ @darijgrinberg How can $\;d=0\;$ be ever possible if $\;(a_1,...,a_n)\ge(a_1,...,a_n,a_{n+1})=1\;$ ? $\endgroup$ – DonAntonio Dec 30 '19 at 9:57
  • $\begingroup$ @DonAntonio: Your $\geq$ sign is a $\subseteq$, so it is certainly possible. Imagine $a_1 = a_2 = \cdots = a_n = 0$ and $a_{n+1} = \pm d$. $\endgroup$ – darij grinberg Dec 30 '19 at 10:09
  • $\begingroup$ @darijgrinberg No, my sign is fine...but I thought it was a given the $\;a_i\;$ were different from zero. Thanks. $\endgroup$ – DonAntonio Dec 30 '19 at 10:32

I can get close; consider the block matrix $$\left(\begin{matrix} a_1x_1 & r\\ c&I\end{matrix}\right)$$ where $r$ is the row vector $(\begin{matrix} a_2 & a_3 & \cdots & a_n\end{matrix})$, $c$ is the column vector $(\begin{matrix} -x_2 & -x_3 & \cdots & -x_n\end{matrix})^T$, and $I$ is the $(n-1)\times (n-1)$ identity matrix.


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.