Are the two given lattices related to each other by a simple rotation?

Question

I am trying to come up with a general algorithm to determine if two lattices are related to each other by a simple rotation operation.

The way I think about a lattice is as an array of points. The lattice is specified by a set of basis vectors. For example a 2D lattice can be defined by the following basis:

$$\mathcal{B} = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \Lambda = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 2 & 5 \end{bmatrix} = \begin{bmatrix} \vec{b}_x & \vec{b}_y \end{bmatrix} $$

The lattice consists of all the points that can be expressed as integer linear combinations of the basis vectors: $l\vec{b}_x + m \vec{b}_y$, where $l,m \in \mathbb{Z}$. The lattice generated by the basis vectors $\vec{b}_x = \hat{e}_x + 2 \hat{e}_y$ and $\vec{b}_y = 5 \hat{e}_y$ is shown below.

Now suppose I am given two lattices with basis vectors as follows:

1. $\mathcal{B}_1 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \Lambda_1 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 2 & 5 \end{bmatrix}$ and

2. $\mathcal{B}_2 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \Lambda_2 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 3 & 5 \end{bmatrix}$.

The two lattices are shown next to each other.

I want to determine if Lattice 2 is related to Lattice 1 by a simple rotation other than the identity operation. I perform a few checks first:

1. I check that their volumes (determinants) are the same. Otherwise, they define two distinct lattices and so one lattice cannot be obtained by a simple rotation of the other.

2. I also check that $\Lambda_1^{-1} \cdot \Lambda_2$ is not a UNIMODULAR MATRIX (a matrix of integers with determinant $\pm$1). If it is then the two bases define the same lattice.

3. If they are related by a simple rotation, there exists a rotation matrix $\mathbb{R} \in O(3)$ such that $\Lambda_2 = \mathbb{R} \Lambda_1 U$, where $U$ is a unimodular matrix (i.e. a matrix of integers with $\det(U)=\pm 1$).

In the above example, I know visually that the two lattices are related to each other by a rotation operation. However, I am not sure how to solve it using a code of some sort. The complication I think comes from the fact that any lattice has infinitely-many bases.

My solution: I assume a unimodular matrix with unknown integer entries $a,b,c,d$. I can use the properties of the rotation matrix (i.e. $\mathbb{R} \cdot \mathbb{R}' = I$, where $\mathbb{R}'$ is the transpose of the rotation matrix and $I$ is an identity matrix) and the unimodular matrix ($\det(U) = \pm 1$) and solve for $a,b,c,d$. If there exists a solution where all the entries are integers then the two lattices are related by a rotation operation.

EDIT: To make it clear, here is an example of two lattices that are not simple rotations of each other but the checks pass:

1. $\mathcal{B}_1 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \Lambda_1 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 2 & 5 \end{bmatrix}$ and

2. $\mathcal{B}_2 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \Lambda_2 = \begin{bmatrix} \hat{e}_x & \hat{e}_y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 5 \end{bmatrix}$.

I think this should work but it is very inefficient. I think there should be an efficient solution for this. Any suggestions are appreciated!

Answer 1

Make the Gram matrices for your two lattices, then the quadratic forms they define. Gauss reduce both.

NO EIGENVECTORS

PDF

online calculator: http://www.numbertheory.org/php/reduceneg.html

Given a symmetric matrix of integers $$ G = \left( \begin{array}{rr} v \cdot v & v \cdot w \\ w \cdot v & w \cdot w \end{array} \right) = \left( \begin{array}{rr} e & f \\ f & g \end{array} \right) $$ we get a quadratic form $$ h(x,y) = a x^2 + b x y + c y^2, $$ where here $a=e, b = 2f, c = g.$ Notation $$ \langle a,b,c \rangle $$ refers to this form. Your form is automatically positive. Gauss reduction of a binary quadratic form is very fast, accomplished by a finite number of of these mappings: $$ \langle a,b,c \rangle \mapsto \langle c,-b,a \rangle,$$ or $$ \langle a,b,c \rangle \mapsto \langle a, b + 2 t a, c + bt + a t^2 \rangle.$$ For this choice we take $t$ so that $|b+2ta| \leq a.$

The final result is a Gauss reduced form $\langle a,b,c \rangle$ which means: $$a > 0, c \geq a, -a < b \leq a; $$ also if $a=c$ then $b \geq 0.$

If your lattices are $SL_2 \mathbb Z$ equivalent they will create identical reduced quadratic forms. If they are not quite equivalent ( for example one basis is the same as the basis of the other, but in reversed order) the (reduced)forms will be "opposite" $\langle a,b,c \rangle$ and $\langle a,-b,c \rangle$

My favorite book on this is Buell, Binary Quadratic Forms. It would be easier (and cheaper) to find a paperback reprint of L. E. Dickson, Introduction to the Theory of Numbers, originally 1929.

Buell:

Answer 2

Similar Matrices have identical smith normal forms. If you have Matrices $A$, $B$ with SNF's $$ U_AAV_A = U_BBV_B $$ you can transform lattice points and their solutions from $A$ to $B$ and back.