1
$\begingroup$

For integers $a,b,c$ with $(a,b,c)=1$, does there exist a $3\times 3$ matrix with determinant $1$ with integer coefficients, such that $a,b,c$ are in the first row?

A simple existential argument would be preferred to an algorithm, but whatever works!

1 Answers 1

2

I don't know a nice existential proof, but I know a very simple algorithm that works by induction to prove that for integers $(a_1, \dots, a_s)$, these is a matrix with determinant $\gcd(a_i)$ and first row $(a_1 \dots a_s)$. (Exception: If $s = 1$, then the determinant will be $\pm \gcd(a_i)$.)

$s=1$ is trivial, now by induction hypothesis there is a matrix $N$ with first row $(a_2 \dots a_s)$ and determinant $d = \gcd(a_2, \dots, a_s)$. Then $\gcd(a_1, \dots, a_s) = \gcd(a_1, d) = a_1 x + d y$ by Bézout. Then the following matrix works:

$\begin{pmatrix} a_1 \\ 0 & & N & & \\ \vdots \\ 0 \\ (-1)^{s-1}y & (-1)^sa_2x/d & \dots & (-1)^sa_sx/d \end{pmatrix}$ (where we assume WLOG $d = 0$).

Apply the induction step twice to find your matrix. Namely, if $d = \gcd(a_2, a_3)$, $a_2x+a_3y = d$ and $a_1u+dv=1$, then your matrix is (barring typos):

$\begin{pmatrix} a_1 & a_2 & a_3 \\ 0 & -y & x \\ v & -a_2u/d & -a_3u/d \end{pmatrix}$

  • 0
    Excellent, thanks!2012-04-17