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

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

• Why $O(N^6)$? You have 9 variables, and 1 constraint, so the number of solutions should behave something like $O(N^8)$. Listing all integer points that satisfy an arbitrary polynomial equation is generally quite a hard problem, even when the equation is something simple like an elliptic curve. – Kirill Mar 5 '16 at 15:33
• You are right, Kirill. I made a mistake... Thanks! – Srikanth Mar 5 '16 at 15:36
• If the number of solutions to output is $O(N^8)$ and the algorithm takes $O(N^8)$, then that algorithm is as efficient as it can possibly be. – Kirill Mar 5 '16 at 15:38
• Hmm... Should have rephrased my question properly. I made some edits to reflect my final goal. The final answer actually contains a small set of matrices that I am interested in! I just don't know an efficient way to get to this... It is definitely that I don't have the right algorithm to solve the question. Hoping that folks on this forum would be interested! – Srikanth Mar 5 '16 at 15:50