Right inverse of integer matrix

Question

If I have a rectangular matrix $A$ (say $4 \times 6$) with integer entries, is there a way to tell whether it has a right inverse that also has integer entries. I know that if $AA^T$ has determinant $\pm 1$ then $A^T(AA^T)^{-1}$ will give such an inverse, but there are infinitely many right inverses, so is there a way to tell if there is an integral one if this one doesn't work?

Answer 1

Using the Pinelis' and Steinberg's posts, we can -easily - deduce

$\textbf{Proposition.}$ Let $m<n$, $A\in M_{m,n}(\mathbb{Z})$ and let $S$ be its Smith normal form.

Then $A$ admits a right inverse in $M_{n,m}(\mathbb{Z})$ IFF $S_{m,m}=1$.

$\textbf{Proof.}$ $(\Rightarrow)$ We put $S=UAV$, where $U,V$ are integer matrices with determinant $\pm 1$.

Here $AR=I_m$; then $S(V^{-1}RU^{-1})=I_m$ and $S$ has an integer right inverse.

Since $S=\begin{pmatrix} D&0_{m,n-m}\end{pmatrix}$, where $D$ is integer diagonal $\geq 0$, that implies that $D=I_m$.

The converse is clear because the sequence $S_{i,i}$ is non-decreasing. $\square$

$\bullet$ $\textbf{Remark 1.}$ Let $m=4,n=6$; if we randomly choose $A$ (uniform random choice of the $a_{i,j}$'s in $(-100..100))$, then we find that $72\%$ of these matrices admit an integer right inverse.

$\bullet$ $\textbf{Remark 2.}$ If we want to know all the integer right inverses of $A$, it suffices to write $V^{-1}RU^{-1}=\begin{pmatrix}D^{-1}\\Z_{n-m,m}\end{pmatrix}$, where $Z$ is integer arbitrary. We obtain solutions with $m(n-m)$ integer parameters.

Answer 2

If $A$ is $m\times n$, then for a right inverse to exist it is clearly necessary that the rank of $A$ be $m$ and hence $m\le n$.

For a right inverse of $A$ with integral entries to exist it is sufficient that there exist an $m\times m$ submatrix $A_1$ of $A$ with determinant $\pm1$. Indeed, then without loss of generality $A=\begin{bmatrix}A_1&A_2 \end{bmatrix}$ for some matrix $A_2$ and hence the matrix $\begin{bmatrix}A_1^{-1}\\ 0 \end{bmatrix}$ will be a right inverse of $A$ with integral entries.

It seems quite possible that there is no non-tautological necessary and sufficient condition for the existence of a right inverse of $A$ with integral entries.