Under what circumstances does row reducing an integer matrix yield another integer matrix?

Question

If I start with a matrix of all integers, and put it in row reduced echelon form, in general I will not get a matrix of all integers. Under what circumstances does the resulting matrix have all integers?

Answer 1

$\newcommand{\lcm}{\operatorname{lcm}}$If all ratios of entries to other entries in the same row are rational numbers, as in fact they are if all entries are integers, then you can use row operations to get a fully reduced matrix in which all entries are integers. \begin{align} & \begin{bmatrix} 12 & -4 & 5 & -6 \\ 15 & 3 & 2 & 1 \\ 2 & 0 & -3 & 1 \end{bmatrix} \\ & \qquad \text{You have $\lcm(12,15) = 60$ and $\lcm(12,2)=12$, so do this:} \\ & \qquad \text{2nd row } \longleftarrow (4\times\text{2nd}) + (-5\times \text{1st}) \\ & \qquad \text{3rd } \longleftarrow (6\times\text{3rd}) + (-1\times\text{1st}) \\[10pt] & \begin{bmatrix} 12 & -4 & 5 & -6 \\ 0 & 32 & -17 & 34 \\ 0 & 4 & -23 & 12 \end{bmatrix} \end{align} By using LCMs, you keep the entries as integers.

But suppose somehow you get a row of rational numbers, like this: $$ \begin{array}{rrrr} \dfrac{88}{51} & \dfrac{19}{68} & \dfrac 7 {12} & \dfrac{8}{15} \end{array} $$ We have $\lcm(51,68,12,15) = 1020.$

One way to find this is via prime factorizations: $$ \begin{align} 51 & = 3\times17\\ 68 & = 2\times2\times17\\ 12 & = 2\times2\times3\\ 15 & = 3\times5 \end{align} $$ The LCM is the smallest number divisible by $3,$ by $2\times2,$ by $17,$ and by $5,$ thus $2\times2\times3\times5\times17 = 1020.$

The elementary row operation to apply now is multiplication of every member of the row by $1020.$

Do not do it like this: $\displaystyle 1020\times \frac{88}{51} = \frac{89760}{51}.$ Instead, cancel before multiplying:$\require{cancel}$ $$ 1020\times \frac{88}{51} = (20\times \cancel{51})\times\frac{88}{\cancel{51}} = 1760, $$ and similarly in every case the denominator cancels out completely, and you get $$ \begin{array}{cccc} 1760 & 285 & 595 & 544 \end{array} $$ Every entry is an integer.

If you define fully reduced form that requires every pivot element to be $1,$ then you'll still need to divide each row by the leading entry and you won't get all integers. So this doesn't answer your question in that case. I'm inclined to let that division wait until the last step.