10
$\begingroup$

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

$\endgroup$
3
  • $\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, 2016 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$ Jun 20, 2016 at 23:44
  • 1
    $\begingroup$ Does this answer your question? Can the determinant of an integer matrix with a given row be any multiple of the gcd of that row? $\endgroup$ Apr 22, 2022 at 12:05

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The case $d = 0$ needs extra care. $\endgroup$ Apr 29, 2019 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, 2019 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$ Dec 30, 2019 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, 2019 at 10:32
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .