Random Integer Matrices With Inverses That Are Also Integer Matrices

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.