IMC 2006 · Day 1 · P3

By induction, it is enough to consider the case $m = 2$.

Furthermore, we can multiply $A$ with any integral matrix with determinant 1 from the right or from the left, without changing the problem. Hence we can assume $A$ to be upper triangular.

Lemma. Let $A$ be an integral upper triangular matrix, and let $b, c$ be integers satisfying $\det A = bc$. Then there exist integral upper triangular matrices $B, C$ such that $\det B = b$, $\det C = c$, $A = BC$.

Proof. The proof is done by induction on $n$, the case $n = 1$ being obvious. Assume the statement is true for $n-1$. Let $A$, $b$, $c$ as in the statement of the lemma. Define $B_{nn}$ to be the greatest common divisor of $b$ and $A_{nn}$, and put $C_{nn} = \frac{A_{nn}}{B_{nn}}$. Since $A_{nn}$ divides $bc$, $C_{nn}$ divides $\frac{b}{B_{nn}} c$, which divides $c$. Hence $C_{nn}$ divides $c$. Therefore, $b' = \frac{b}{B_{nn}}$ and $c' = \frac{c}{C_{nn}}$ are integers. Define $A'$ to be the upper-left $(n-1) \times (n-1)$-submatrix of $A$; then $\det A' = b' c'$. By induction we can find the upper-left $(n-1) \times (n-1)$-part of $B$ and $C$ in such a way that $\det B = b$, $\det C = c$ and $A = BC$ holds on the upper-left $(n-1) \times (n-1)$-submatrix of $A$. It remains to define $B_{i,n}$ and $C_{i,n}$ such that $A = BC$ also holds for the $(i,n)$-th entry for all $i < n$.

First we check that $B_{ii}$ and $C_{nn}$ are relatively prime for all $i < n$. Since $B_{ii}$ divides $b'$, it is certainly enough to prove that $b'$ and $C_{nn}$ are relatively prime, i.e. $$\gcd \left( \frac{b}{\gcd(b, A_{nn})}, \frac{A_{nn}}{\gcd(b, A_{nn})} \right) = 1,$$ which is obvious. Now we define $B_{j,n}$ and $C_{j,n}$ inductively: Suppose we have defined $B_{i,n}$ and $C_{i,n}$ for all $i = j+1, j+2, \dots, n-1$. Then $B_{j,n}$ and $C_{j,n}$ have to satisfy $$A_{j,n} = B_{j,j} C_{j,n} + B_{j,j+1} C_{j+1,n} + \dots + B_{j,n} C_{n,n}$$ Since $B_{j,j}$ and $C_{n,n}$ are relatively prime, we can choose integers $C_{j,n}$ and $B_{j,n}$ such that this equation is satisfied. Doing this step by step for all $j = n-1, n-2, \dots, 1$, we finally get $B$ and $C$ such that $A = BC$.