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}$