Efficient way to generate a list of possible matrices (all integer components) with a determinant $V$

Question

I have an interesting problem from my research that I have been struggling to solve. One part of the problem involves generating all possible matrices, where each set contains three integer vectors, of a given volume $V$. That is the determinant of the matrix should be $V$. The constraint is that the maximum of the absolute value of the integer components is bounded by $N$.

That is , suppose a $3 \times 3$ matrix $A$ with components $a_{ij}$, then

1. $a_{ij} \in \mathbb{Z}$
2. $\max (|a_{ij}|) \leq N$.
3. $\det(A) = V$

I have a MATLAB code that, I believe, scales as $O(N^8)$, and so, highly inefficient.

The way I am thinking about this is as a lattice of integer points. I need three vectors with components $(a_{11}, a_{12}, a_{13})$, $(a_{21}, a_{22}, a_{23})$, and $(a_{31}, a_{32}, a_{33})$. These components are all integers and will be the rows of the matrix $A$. The volume $V$ of the parallelepiped is the determinant of the matrix $V$.

I create $N_1 = (2N+1)^3$ number of lattice points. I choose two vectors, which will create $N_1 \choose 2$ combinations. And then I enumerate through the $N_1$ choices for the third vector and check if the determinant of the matrix is $V$. Any ideas to speed up this process? Thank you!

If you are interested, the reason I want to generate these matrices is listed as another question here - https://math.stackexchange.com/questions/1683555/unique-sub-lattices-of-a-given-volume

Edit 1: Explaining the final goal of the problem might help set this up better.

Let the solution of all the possible matrices be denoted by the set $S_V =\{ A \}$. I am only interested in a finite subset of matrices $Q_{V} = \{Q \} \subset S_V$, such that

1. For any two matrices $Q_1$ and $Q_2$ that belong to $Q_V$, $Q_1 \cdot Q_2^{-1}$ is a non-integer matrix. That is any matrix in $Q_V$ cannot be expressed as an integer linear combination of any other matrix in $Q_V$ (They do not belong to the same lattices).
2. For all matrices $A \in S_V$, there exists a matrix $Q \in Q_V$, such that $A \cdot Q^{-1}$ is an integer matrix. That is any matrices in $S_V$ can be expressed as an integer linear combination of a matrix in $Q_V$

This subset $Q_V$ ends up being pretty small. For example, for V = 3, there are only 13 matrices in the set $Q_V$ for any $N>3$.

Answer 1

I was able to get an answer on the math stackexchange site. You could find the answer here! It supposedly has to do with Hermite Normal Forms! Thank you, Heterotic for the answer.