MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is this possible to do constructively? The only sources that I have for the possibility of this construction is an exercise in Lang's Algebra (on p. 598, I believe) which states that one can be constructed, and then a construction given in Milnor and Hussemoller's book which only applies in the case that the elementary divisors are all 1.

In my case, I have a rank 4 lattice of with a symplectic form of type (1, n), and I have some elements which span an index n sublattice. I would like to somehow relate them to a symplectic basis on the whole lattice, but it seems to me that I would need to have a constructive method for creating such a basis for this to be of any use whatsoever.

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


By posting your answer, you agree to the privacy policy and terms of service.

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