Unimodular Matrix calculation

Question

I know for a given matrix $M$, there exists a matrix $U$ over the integers with determinant $+1$ or $-1$ such that $UM=E$. I know $E$, but $M$ is not a square matrix. Is there any easy way to get $U$?

Answer 1

So I've thought about this problem a lot, and this answer is the best I can come up with:

Let's suppose that $U$ is a $k \times m$ matrix, $M$ is an $m \times n$ matrix, and $E$ is a $k \times n$ matrix.

If $W$ is an $n \times m$ matrix such that $MW = I$ (in this case, $I$ is $m \times m$), then $U = EW$. Matrices having this property are called right inverses of $M$.

The language of generalized inverses can be used to determine right inverses. If both matrices are full rank and $MW = I$, then $M$ and $W$ are $\{1,2\}$-inverses of each other, because $MWM = M$ and $WMW = W$. The best reference that I know of that discussed how to calculate $\{1,2\}$-inverses of matrices is Generalized Inverses: Theory and Applications, 2nd edition by Thomas N.E. Greville and Adi Ben-Israel. Unfortunately, the authors don't really have an eye for computational efficiency, so you'll need to tweak their algorithms accordingly.

However, the converse doesn't necessarily hold: if $M$ and $W$ are $\{1,2\}$-inverses and $M$ and $W$ are full rank, $MW$ may not equal $I$. The reasoning is as follows.

If $M$ and $W$ are $\{1,2\}$-inverses, then $MW$ will be a projection matrix with rank equal to $\min\{m,n\}$. $MW$ is an $m \times m$ matrix. These two facts combined means that:

• If $m \leq n$, then $W$ will be a right inverse because $MW = I$.
• If $m > n$, then $W$ will not be a right inverse because $MW$ has rank $n$, and the only full rank projection matrix is the identity matrix.

So the approach of determining a right inverse $W$ using $\{1,2\}$-inverses will only work if $m \leq n$ and $M$ is full rank. Otherwise, a right inverse of $M$ may not exist (there are no guarantees that it will, without imposing properties on $M$).

This doesn't yield a fast algorithm to solve your problem for the matrix dimensions that you've given, but it is at least a partial solution.

Answer 2

You are talking about computation of the Hermite Normal Form (HNF), which is covered in books by Schrijver and by Nemhauser and Wolsey. In the theory of lattices and integer matrices, the HNF plays a big role. It is like an integer QR factorization.

A square integer matrix with determinant $\pm 1$ is called a unimodular matrix. By Cramer's rule, the inverse of a unimodular matrix is integer and unimodular. Thus, the unimodular matrices are isomorphisms of $\mathbb{Z}^m$.

Suppose that $M$ is $m \times n$, with linearly independent rows, $m \le n$, and integer entries so that its rows are a basis of a sub-lattice of $\mathbb{Z}^n$. (A lattice in general is the set of integer linear combinations of a set of linearly independent vectors.)

$E$ is the HNF of the lattice determined by the rows of $M$. It will have an upper triangular form, with the additional property that the first nonzero of each row is bigger than the elements above it. It is a normal form in the sense that if two lattices are identical, then they have the same $E$, the same HNF. The HNF can be useful in answering a variety of lattice related questions. The most basic one is the question of whether a given vector $b$ in $\mathbb{Z}^n$ is in the lattice of $M$'s rows: It is iff $\text{inv}(U)b$ is in the lattice of $E$'s rows, and the triangular structure of $E$ makes this easy to check.

The elements of $E$ and $U$ may be very large integers, and controlling the growth of the elements is the key algorithmic challenge. If one ignores this, its easy to derive an algorithm by finding a unimodular "Givens" type transformation -- a $2 \times 2$ unimodular transformation that can zero one element of an integer 2-vector. Integer gcd is a subroutine of the construction of one of these. With them, one can introduce zeros so as to create the desired upper triangular form.