Reduce $m \times n$ matrix with full rank to a precise form

Question

I know that, given a certain $m \times n$ matrix $Q$ where $m > n$, it has full rank, meaning that there is a matrix $S \in \operatorname{GL}(n, \mathbb{Z})$ such that
$$QS = \begin{pmatrix} \operatorname{Id}^{n \times n} \\ E \end{pmatrix}$$

and I am interested in determining $E$ (equivalently, determining $S$).

Is there a standard way to do this, computationally? I think one idea could be to select an $n \times n$ submatrix $P$ of $Q$ with full rank, solve $PX = \operatorname{Id}$ for $X$ and then computing $QX$ (after an appropriate permutation to write $Q$ in the form $\begin{pmatrix} P \\ R \end{pmatrix}$)

I don't mind the tool being used (Gap, Magma, Mathematica, MatLab,…).

Answer 1

There are some odd minor glitches in this question, which make it impossible to literally answer as asked. First of all, the asker wants $S$ to be in $GL_n(\mathbb{Z})$. But with integer coefficients, having full rank doesn't have the desired consequence. For example, $\left[ \begin{smallmatrix} 1&1 \\ 1&-1 \end{smallmatrix} \right]$ has full rank, but its determinant is even, so we can't make it into the identity by right multiplying it by an integer matrix.

Secondly, the asker asks for the identity matrix to end up in the first $n$ rows. But consider the full rank matrix $\left[ \begin{smallmatrix} 0 \\ 1 \end{smallmatrix} \right]$. It's first row is $0$, so we can't make it into $1$.

Here are two corrected versions which both have simple answers:

Question Let $Q = \left[ \begin{smallmatrix} A \\ B \end{smallmatrix} \right]$ be a matrix so that we know there is an $S$ with $QS = \left[ \begin{smallmatrix} \mathrm{Id} \\ E \end{smallmatrix} \right]$. How do we find $S$ and $E$?

Answer Put $S=A^{-1}$ and $E = B A^{-1}$.

Or, alternatively:

Question Let $Q$ be a matrix over some field of full rank. How can we find a matrix $S$ such that $QS$ looks as simple as possible?

Answer Use column reduction (the transpose of row reduction). The reduced column echelon form of $Q$ will be of the form $QS$ and will have an identity matrix in some set of rows, but not necessarily the top rows.

Computer algebra systems usually produce row reductions, not column reductions, but that's easy to deal with. For example, in Mathematica, define

columnReduce[M_]:=Transpose[RowReduce[Transpose[M]]]

I believe the analogous MatLab code is

 function transpose(rref(transpose(M))) = cref(M)