# Can the determinant of an integer matrix with a given row be any multiple of the gcd of that row?

Let $n\geq2$ be an integer and let $a_1,\ldots,a_n\in\mathbb Z$ with $\gcd(a_1,\ldots,a_n)=1$. Does the equation $$\begin{vmatrix}a_1&\cdots&a_n\\x_{11}&\cdots&x_{1n}\\x_{21}&\cdots&x_{2n}\\\vdots&\ddots&\vdots\\x_{n-1,1}&\cdots&x_{n-1,n}\end{vmatrix}=1$$ always have an integer solution for the $x_{kl}$'s?

Motivation

Consider the following question:

Let $(0,0)\neq(a,b)\in\mathbb Z^2$. What is the minimal area of a triangle whose vertices have coordinates $(0,0)$, $(a,b)$ and $(x,y)\in\mathbb Z^2$?

It is easily seen to be $\frac12\gcd(a,b)$, by noting that the area is given by $$\frac12\left|\begin{vmatrix}a&b\\x&y\end{vmatrix}\right|=\frac12|ay-bx|$$ and Bézout's theorem. Note that this is the case $n=2$. We also have:

Let $(0,0,0)\neq(a_1,a_2,a_3)\in\mathbb Z^3$. The minimal volume of a tetrahedron whose vertices have integer coordinates $(0,0,0)$, $(a_1,a_2,a_3)$, $(x_1,x_2,x_3)$ and $(y_1,y_2,y_3)$ is $\frac16\gcd(a_1,a_2,a_3)$.

The proof is a bit more tedious: (source (in Dutch))

The volume is given by $\frac16\left|\begin{vmatrix}a_1&a_2&a_3\\x_1&x_2&x_3\\y_1&y_2&y_3\end{vmatrix}\right|=\frac16\left|a_1\begin{vmatrix}x_2&x_3\\y_2&y_3\end{vmatrix}+a_2\begin{vmatrix}x_1&x_3\\y_1&y_3\end{vmatrix}+a_3\begin{vmatrix}x_1&x_2\\y_1&y_2\end{vmatrix}\right|$. So it suffices to show that $\left(\begin{vmatrix}x_2&x_3\\y_2&y_3\end{vmatrix},\begin{vmatrix}x_1&x_3\\y_1&y_3\end{vmatrix},\begin{vmatrix}x_1&x_2\\y_1&y_2\end{vmatrix}\right)$ can take any value in $\mathbb Z^3$. Let $(u,v,w)\in\mathbb Z^3$. If $\gcd(v,w)=d>1$, we can solve for $(u,\frac vd,\frac wd)$ and multiply $x_1,y_1$ by $d$ to get a solution for $(u,v,w)$. Assume $\gcd(v,w)=1$. Now choose $x_1=y_1=1$, $x_2,x_3$ such that $x_2v-x_3w=u$ and $y_2=x_2+w$, $y_3=x_3+v$ to get $\left(\begin{vmatrix}x_2&x_3\\y_2&y_3\end{vmatrix},\begin{vmatrix}x_1&x_3\\y_1&y_3\end{vmatrix},\begin{vmatrix}x_1&x_2\\y_1&y_2\end{vmatrix}\right)=(u,v,w)$.

This is what made me think that these observations might generalise to higher dimensions...

• Might this not follow by induction by expanding the determinant along the second row? Aug 27, 2015 at 11:58
• I like this question a lot. It's interesting, well-written, and new to me Aug 29, 2015 at 21:25

The conjecture appears true:

For any $a_1,\ldots,a_n\in\mathbb Z$, the determinant of a matrix with them in its first row can be any multiple of their $\gcd$.

It clearly suffices to handle the case in which their $\gcd$ is $1$. I found a recursive procedure that seems to work. For $n=2$ we take $$\begin{pmatrix}a_1&a_2\\-b_2&b_1\end{pmatrix}$$ where $b_1a_1+b_2a_2=1$. Now let $n\geq3$ and suppose we've constructed $M$ such that $$\left|\begin{array}{c}a_2&\cdots&a_n\\\hline\\ &\large M\end{array}\right|=\gcd(a_2,\ldots,a_n)=a.$$

Imagine expanding this determinant along the first row. What we get is a linear combination of $a_2,\ldots,a_n$ with the $n-2\times n-2$ minors of $M$, say $m_2,\ldots,m_n$, as coefficients. Note that this implies $\gcd(m_2,\ldots,m_n)=1$, so there exist $c_2,\ldots,c_n\in\mathbb Z$ such that $$\left|\begin{array}{c}c_2&\cdots&c_n\\\hline\\ &\large M\end{array}\right|=1.$$ Because $\gcd(a_1,a)=1$ we have $xa_1+ya=1$ for some $x,y\in\mathbb Z$. Now observe that $$\left|\begin{array}{c|ccc}a_1&a_2&\cdots&a_n\\ -y&xc_1&\cdots&xc_n\\\hline 0\\ \vdots&&M\\ 0\end{array}\right|=a_1\cdot\left|\begin{array}{c}xc_2&\cdots&xc_n\\\hline\\ &\large M\end{array}\right|+y\cdot\left|\begin{array}{c}a_2&\cdots&a_n\\\hline\\ &\large M\end{array}\right|=1.$$

Note: the obtained matrix will look like $$\begin{pmatrix}a_1&a_2&a_3&\cdots&a_{n-1}&a_n\\ *&*&*&\cdots&*&*\\ 0&*&*&\cdots&*&*\\ 0&0&*&\cdots&*&*\\ \vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&*&*\end{pmatrix},$$ which is called an upper Hessenberg matrix.

When you calculate the gcd of $$n$$ numbers $$(a_1, \ldots, a_n)$$ you apply the Euclid methods by substracting some multiple on one from another, and perhaps some transpositions. That translates into multiplication on the right by some elementary matrices. Conclusion: we can multiply $$(a_1, \ldots, a_n)$$ on the right by a product of elementary matrices and get $$(d, 0, \ldots, 0)$$.

$$\bf{Added:}$$ Let us prove a more general result. Assume that we have a $$k \times n$$ matrix $$A$$ with elements in a PID ( $$1\le k, such that the gcd of the $$k\times k$$ minors of is $$1$$. Then the matrix can be completed to a unimodular $$n\times n$$ matrix. Indeed there exist $$M \in GL_k(R)$$, $$N\in GL_n(R)$$ such that

$$M \cdot A = D \cdot N$$

where $$D$$ is a $$k\times n$$ matrix with $$1$$ on the principal diagonal. It follows that $$M A$$ forms $$k$$ rows of the unimodular matrix $$N$$, and so will $$A$$ be the first $$k$$ rows of a unimodular matrix.