

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer



share|cite|improve this question
up vote 5 down vote accepted

Here is an algorithm, it may not be a good one. I will only explain how to find a basis $e_i$, $f_i$ such that $\langle e_i, e_j \rangle = \langle f_i, f_j \rangle =0$ and $\langle e_i, f_j \rangle = c_i \delta_{ij}$ for some constants $c_i$. I will punt on explaining how to make sure that $c_1$ divides $c_2$ which divides $c_3$ and so forth. This presentation is closely based on the algorithm in Wikipedia for computing Smith normal form.

Find $e$ and $f$ so that $\langle e,f \rangle \neq 0$ (EDIT) and such that the lattice spanned by $e$ and $f$ is the intersection of the whole lattice with the vector space spanned by $e$ and $f$.

Set $d := \langle e,f \rangle$. Complete $(e,f)$ to a basis $(e,f,g_1, g_2, \ldots, g_{2n})$ of our lattice.

Case 1: We have $\langle e,g_i \rangle = \langle f, g_i \rangle =0$ for all $i$. Take $e_1=e$, $f_1=f$ and apply our algorithm recursively to the sublattice spanned by the $g_i$.

Case 2: For all $i$, the integer $d$ divides $\langle e,g_i \rangle$ and $\langle f, g_i \rangle =0$. Replace $g_i$ by $$g_i - \frac{1}{d}\langle g_i, f \rangle e- \frac{1}{d}\langle e, g_i \rangle f.$$ We have now reduced to Case 1.

Case 3: There is some $g_i$ so that $k:=\langle e, g_i \rangle$ is not divisible by $d$. Then, for some $q$, we have $0 < k-qd < d$. Set $f'=g_i-kf$ and $g'_i=f$. Then $(e,f',g_1,g_2,\ldots, g'_i, \ldots, g_n)$ is a basis, and $\langle e, f' \rangle$ is less than $d$. Return to the beginning with this new basis.

Case 4: There is some $g_i$ so that $k:=\langle f, g_i \rangle$ is not divisible by $d$. Just like Case 3, with the roles of $e$ and $f$ switched.

Since $d$ decreases at every step, eventually we will hit Case 1 and be able to reduce the dimension.

share|cite|improve this answer
Ah, thank you. Your method seems a little more constructive than the ultimate method that I was shown: For $e \in \Lambda$, $\langle e, \Lambda \rangle$ is an ideal in $\mathbb{Z}$, which we write as $n_e\mathbb{Z}$. Choose $e$ such that $n_e$ is minimal. There is then necessarily some $e'$ such that $\langle e, e' \rangle = n_e$, and we can use these to set up the induction, once you verify that $n_e$ divides all other possible pairings. – Simon Rose Nov 22 '09 at 0:13
Actually, on hindsight there is a flaw in your algorithm, at the very first step. The problem is that your initial choice of elements may not be basis elements! Even if they are both primitive, it is possible that they span a non-trivial sublattice, in which case your first step does not actually succeed. – Simon Rose Nov 24 '09 at 5:12
Thanks. You can just fix that right at the beginning though. I added a note to avoid this. – David Speyer Nov 24 '09 at 13:15

Your Answer


