4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kirill Mar 5 '16 at 15:33
  • $\begingroup$ You are right, Kirill. I made a mistake... Thanks! $\endgroup$ – Srikanth Mar 5 '16 at 15:36
  • $\begingroup$ 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. $\endgroup$ – Kirill Mar 5 '16 at 15:38
  • $\begingroup$ 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! $\endgroup$ – Srikanth Mar 5 '16 at 15:50
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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