# Basis for the intersection of two integer lattices

If $B_1$ and $B_2$ are the bases of two integer lattices $L_1$ and $L_2$, i.e.

$L_1=\{B_1n:n\in\mathbb Z^d\}$ and $L_2=\{B_2n:n\in\mathbb Z^d\}$,

is there an easy way to determine a basis for $L_1\cap L_2$? Answers of the form "Plug the matrices into a computer and ask for Hermite Normal Form, etc" are perfectly acceptable as this is a practical problem and the matrices of integers $B_1$ and $B_2$ are known, but I need some algorithmic way because the procedure will be repeated many times.

• From cseweb.ucsd.edu/classes/wi10/cse206a/lec2.pdf : compute the dual bases $D_1,D_2$, then ask for HNF of the concatenated matrix $[D_1\mid D_2]$ and get the dual of that. Commented Dec 4, 2015 at 23:55
• @StevenStadnicki Nice and elegant! Thanks so much! If you would like to post the comment as an answer I will gladly accept it. Commented Dec 5, 2015 at 11:02

A set of lecture notes up at http://cseweb.ucsd.edu/classes/wi10/cse206a/lec2.pdf suggests computing the dual bases $D_1$ and $D_2$ of your lattices, then getting the HNF/orthogonalization of the concatenated matrix $[D_1\mid D_2]$ and then computing the dual of that. You'll want to be slightly careful with your algorithm for computing normal form to keep the intermediate coefficients from blowing up, but that shouldn't be too hard.

• @Heterotic Did this work for you? I used the HermiteDecomposition function in Mathematica and I end up with non-integral coefficients.. Commented Sep 19, 2016 at 9:52
• Is this correct for non-full-rank lattices? (there's no mention in the linked PDF.) For example the two lattices with bases $[(0, 1)]$ and $[(1, 0)]$ are dual of themselves, but their intersection has basis $[]$ while the dual of their union has basis $[(1, 0),(0, 1)]$. Commented Apr 27, 2020 at 7:13

L1 and L2 are column vector latices
A is a 2x2 block matrix
0 is an all zeros matrix
\begin{align} A= \begin{bmatrix} L1 & L2\\ L1 & 0 \end{bmatrix} \end{align}

hermite normal form
\begin{align} B=hnf(A) \end{align}

\begin{align} B= \begin{bmatrix} C & 0\\ D & E \end{bmatrix} \end{align} B is a 2x2 block matrix where E is the latice intersection. you can get the number of columns in E by counting how many all zero columns there are in the block above.

The reason this works is because hnf produces zeros in the upper right block. These zero columns are made up of a linear combination of vectors from L1 and L2. since they add up to zero, the linear combination of L1 vectors equals the negative of the L2 vectors. This shows that these vectors are in both the L1 and L2 latice. You can recover these vectors by just looking at the L1 components, the block E matrix.

Unfortunately hnf tends to produce integer overflow errors in even small latices. However you don't need to put it in full hnf form. Any algorithm that will produce all zero columns in the top right block will work.

• If your thought was to use a specific software package (perhaps Matlab?), it would help Readers if you say so explicitly. For general formatting of math expressions, see this introductory note and its links to more detailed guides. Commented Oct 15, 2017 at 2:35
• Thanks for the link. I added some formatted math expressions Commented Oct 15, 2017 at 18:47