# Finding a basis for a complex lattice given a nondivisible vector in the lattice

If I am given some lattice defined as, say

$$L=\{Az_1+Bz_2\ |\ A,B \in\mathbb{Z}\}$$

and a vector $v=az_1+bz_2$ , where $\gcd(a,b)=1$, I would like to find another vector $\,w\in L\,$ such that $v$ and $w$ form a basis for $L$.

I'm a bit stuck, but I can see how this would be accomplished in a lattice where $z_1=1$ and $z_2=i$ if I was given $v=1+i$: inspecting the lattice I could choose $w=i$ (or $w=1$) and still cover all the lattice points (diagonal lines of slope $1$ along all the lattice points).

If $v=2+i$, I can see how $w=1+i$ would work, where along each row of lattice "squares" you could could go across $2$, up $1$ ($v=2+i$), then up $1$, across $1$ ($w=1+i$), then subtract a $v$, so you are now at

$$(2+i)+(1+i)-(2+i)=1+i=w$$

then add a $w$ so you are at $2+2i$, then subtract a $v$ so you are at

$$(2+2i)-(2+i)=i$$

My questions are:

1. In general, are we only guaranteed a single choice of $w$?
2. How can I use the fact that there are always $s,t$ where $sa+tb=1$ to help find a a $w$?

-
Some more generous spacing, both within the same lines but, mainly, between different lines and phrases could help to make your question clearer, since as it is it is pretty hard to parse the whole thing. Take into account also that using double dollars signs to enclose equations or whatever automatically increases the fonts' size and allots them a separate line. –  DonAntonio Nov 29 '12 at 13:12
Point taken. I tried to make an edit, but it looks like you beat me to it. –  tacos_tacos_tacos Nov 29 '12 at 13:16
any time, @jshin. Now, did you mean "a lattice" in $\,\Bbb C\,$ over $\,\Bbb R\,$ ? I think you did, but then "a basis" for the lattice, for example in Elliptic Curves Theory, has to be taken from the set of basis of the vector space $\,\Bbb C_{\Bbb R}\,$...Are there any restrictions on this? –  DonAntonio Nov 29 '12 at 13:30
@DonAntonio Right. Would it make things a bit easier if I just assume that $z_1$ and $z_2$ are algebraic integers? –  tacos_tacos_tacos Nov 29 '12 at 13:33
Don't think so, unless you're given some further information on the lattice. But then you can do as follows: if you already have a non-zero vector $\,z_1\,$ in the lattice and want to complete it to a basis of it, you only need to take any element $\,z_2\,$ in the lattice s.t. $\,\frac{z_1}{z_2}\notin\Bbb R\,$...and that's all! –  DonAntonio Nov 29 '12 at 13:35

A lattice in $\,\Bbb C_{\Bbb R}\,$ is a free abelian group of the form $\,w_1\Bbb Z+w_2\Bbb Z\,$ , with $\,\{w_1,w_2\}\,$ a basis for (the real vector space) $\,\Bbb C_{\Bbb R}\,$.

This means that $\,w_1\Bbb Z+w_2\Bbb Z\,$ is a lattice iff

$$\{w_1,w_2\}\,\,\,\text{are linearly independent over }\,\,\Bbb R\Longleftrightarrow \frac{w_1}{w_2}\notin\Bbb R\Longleftrightarrow \operatorname{Im}\frac{w_i}{w_2}\neq 0$$

The above is the reason why we can always do the following:

$$\tau:=\frac{w_1}{w_2}\Longrightarrow w_1\Bbb Z+w_2\Bbb Z=Z+\tau\Bbb Z$$

and taking the basis $\,\{1,\tau\}\,$ for our lattice.

As usually done with elliptic curves, we can even choose $\,\tau\,\,\,s.t.\,\,\,\operatorname{Im}(\tau)>0\,$

Thus, if you already have some given, fix $\,z_1\,$ in the lattice (I used above $\,w_1\,$), then any element

$\,z_2\,$ (I used $\,w_2\,$) in the lattice s.t. $\,\displaystyle{\frac{z_1}{z_2}\notin\Bbb R}\,$ will do the work!

-
This makes sense. So in layman's terms, first rotate the lattice so that one of the original basis vectors lies on the real axis. Then pick another point in the lattice that is not along the same line. Then by the way you've set it up, that vector is going to be a linear combination of $1$ and the other vector, so it's going to span the whole lattice? –  tacos_tacos_tacos Nov 29 '12 at 13:57
Yes, though you're trying to follow a strong (I guess) geometric intuition of things, which is fine, and I didn't. –  DonAntonio Nov 29 '12 at 14:01
I still get hung up a lot on what complex multiplication/division "mean" and it helps me when I try to look at it pictorially. One more question - is Ika's statement about all lattices over the complex numbers being isomorphic to the integer lattice in 2D accurate? I thought that isomorphism is not supposed to change the fundamental region. –  tacos_tacos_tacos Nov 29 '12 at 14:06
It all depends: if by "lattice" we merely understand "free abelian groups of rank $\,2\,$ then any two fo these are isomorphic as free abelian group@. Yet, if your stuff *actually is connected to elliptic curves, the next stage is (or could be) to pass to quotients (complex torus) $\,\Bbb C/L\,$ , with $\,L=$a lattice, and then there exists some rather nice conditions that make sure two of these things are isomorphic as elliptic curves...but this may be far away if you're still styruggling with complex operations... –  DonAntonio Nov 29 '12 at 14:10

In this case $z_1$ and $z_2$ seem to be linear independent vectors. Hence $L$ is isomorphic to $\mathbb Z^2$ via $e^i\mapsto z_i$. The preimage of $v$ in $\mathbb Z^2$ is $(a,b)$ which I will just call $v$. Now you need a vector $w=(w_1,w_2)$ such that the equation $r\cdot v+ s\cdot w=u$ has an integral solution for all $u\in\mathbb Z^2$. This is equivalent to the matrix $(v,w)$ having determinant $\pm 1$, since for having an integral solution the matrix has to be invertible over $\mathbb Z$.

Now you use the second statement and just insert $s$ and $t$ from your equation into $w$ such that the determinant becomes the equation. I think $w=(-t,s)$ is correct. The image of this vector then is $t\cdot z_1+s\cdot z_2$ the second basis vector in your lattice $L$.

Since there are infinitely many vectors orthogonal to $v$ the choice is not unique. You may add or subtract $v$ to $w$ and the result will stay a basis.

Hope this helps.

-
Ika, it does help, but I don't think it's the case that $L$ is always isomorphic to $\mathbb{Z}^2$ since $L$ could be, say, a hexagonal lattice, which has a different fundamental region than $\mathbb{Z}^2$ –  tacos_tacos_tacos Nov 29 '12 at 13:10
If $L$ is generated by two linearly independent vectors $z_1$ and $z_2$ it will always be isomorphic to $\mathbb Z^2$. If the generators depend on each other it is isomorphic to $\mathbb Z$ and you don't need a second generator. In general every lattice is isomorphic (as a $\mathbb Z$ vector space) to some $\mathbb Z^n$. –  lka Nov 29 '12 at 13:14
But if we apply a rotation map, don't the angles between all the rays between lattice points remain the same, and not usually nice and orthagonal like $\mathbb{Z}^2$? –  tacos_tacos_tacos Nov 29 '12 at 13:19
Or is rotation, vector by vector, ok since after I find a basis for their equivalents in $\mathbb{Z}^2$ I can just apply the inverse rotation back to each basis vector? –  tacos_tacos_tacos Nov 29 '12 at 13:26
Yes, rotation is an isomorphism, since it can be given by an invertible matrix. And this matrix is then your isomorphism to $\mathbb Z^2$. So you only have to find a way to complete a primitive vector of $\mathbb Z^2$ to a lattice basis, and then use your matrix to get a basis of an arbitrary lattice. –  lka Nov 29 '12 at 15:21