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)

Answer 2

I wrote the following code in Magma that tries to find a $n \times n$ submatrix with full rank and then does as suggested in the first corrected version from David.

Note that running the code with the matrix suggested as a counterexample above gives, indeed, an error. In my case I am dealing with matrices that define quadratic forms with additional properties, so the code should always work (and indeed it does). It also does not check all the submatrices in its current form, just some of them.

It ended up being quite a simple question (either not doable or trivial), but I hope someone can use this in the future!

PreciseMatrix:=function(D);
k:=NumberOfRows(D);
l:=NumberOfColumns(D);
if l ge k then print "ERROR";
end if;
test:=0;
testb:=0;
J:=[1..l];
for i in [1..k-l+1] do
if test eq 0 then
I:=[i..i+l-1];
C:=Submatrix(D,I,J);
if Rank(C) eq l then
test:=1;
S:=C^-1;
for j in [1..i-1] do
Append(~I,j);
end for;
for j in [i+l..k] do
Append(~I,j);
end for;
T:=PermutationMatrix(Integers(),I);
E:=T*D;
X:=E*S;
end if;
end if;
end for;
if test eq 1 then return X;
end if;
testb:=1;
for y in [1..k] do
D:=SwapRows(D, 1, k);
J:=[1..l];
for i in [1..k-l+1] do
if test eq 0 then
I:=[i..i+l-1];
C:=Submatrix(D,I,J);
if Rank(C) eq l then
test:=1;
S:=C^-1;
for j in [1..i-1] do
Append(~I,j);
end for;
for j in [i+l..k] do
Append(~I,j);
end for;
T:=PermutationMatrix(Integers(),I);
E:=T*D;
X:=E*S;
end if;
end if;
end for;
if test eq 1 then return X;
end if;
end for;
print "error"; return 0;
end function;