Random Integer Matrices With Inverses That Are Also Integer Matrices

Joe Gregorio

I want to generate a random integer valued \( n \times n \) matrix \( A \) whose inverse is also an integer valued matrix, i.e. how can I generate Unimodular matrices?

The key is starting with an \( n \times n \) identity matrix \( I \), which has a determinant of 1. Then you can apply row operations to \( I \) that keep the determinant 1, i.e. by picking row operations that are expressible as multiplication by a matrix that also has a determinant of 1 with integer components.

The very simplest of these row operations is to add row \( i \) to row \( j \) where \( i \neq j \):

$$ r_i = r_i + r_j $$

Such a row operation has determinant of 1 and all integer values, so the resulting matrix after the operation still has a determinant of 1, and so it’s inverse also remains integer valued. You can actually add \( N \) times row \( i \) to row \( j \) and still have a determinant of 1, it’s the fact that \( i \neq j \) that keeps the determinant 1.

Such row operations also have nice inverses. If the row operation that represents:

$$ r_i = r_i + r_j $$

is denoted \( R \), then

$$ A=RI $$

and the inverse can be constructed by multiplying \( I \) on the right hand side by \(R^{-1}\):

$$ A^{-1}=IR^{-1} $$

And in this case the inverse of our row operation \( R \) is to just subtract column \( j \) from column \( i \).

If we create a series of such elementary row operations at random we can then generate both \( A \) and \( A^{-1} \).

\( A \) : $$ A = R_{m} … R_{2} R_{1} I $$

\( A^{-1} \) : $$ A^{-1} = I R_{1}^{-1} R_{2}^{-1} … R_{m}^{-1} $$

Here is Go code for an implementation:

Generating Invertible Matrices was one of my first stopping points on getting all of this working.

comments powered by Disqus