Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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$?

share|improve this question
    
Could you give us a little more information about the problem, like the dimensions of the matrices? Do the matrices have any properties you might be able to exploit? (Besides $U$, of course.) Also, for my own understanding, $U$ is an integer matrix? –  Geoff Oxberry Feb 17 '12 at 7:05
2  
@Geoff: it looks to me that OP is considering the inverse Hermite normal form problem. –  J. M. Feb 17 '12 at 10:55
    
Matrix M is (100, 10). Yes U is an integer matrix. –  user12290 Feb 17 '12 at 11:43
1  
Is $E$ a special matrix, i.e., the identity, all ones, tridiagonal ...? –  Deathbreath Feb 29 '12 at 20:20
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.