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

Dear MO_World,

I'm hoping someone can point me towards a reference for something. I have an invertible $2\times 2$ matrix, $A$, with real entries such that for both of the rows, the entries are rationally independent (this ensures that $A\mathbb Z^2$ only intersects the coordinate axes at the origin).

What I want is a pair of generators of the lattice, $u$ and $v$, with $u$ belonging to the first quadrant and $v$ to the fourth quadrant.

I have a proof that I'm not entirely happy with using continued fraction convergents, but as it's going in an already-long paper, I'd love to have a self-contained reference for this.

Does anyone have any suggestions?

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

EDIT: why does a lattice have a shortest vector? To get to the other side? No. Because it is too far to walk around. Also your matrix $A$ is invertible, $A^{-1}$ has an operator norm with respect to the ordinary length, for any vector $w$ we have $|A^{-1} w| \leq C |w|$ with a constant $C > 0$ that depends on the matrix. So $|A x| \geq |x| / C. $ All nonzero lattice vectors have length at least 1, so all vectors in your lattice have length at least $1/C.$ Furthermore, the number of lattice vectors with length below any given bound is finite. So there is a shortest vector.

EDITEDIT: For the why is the shortest vector part of a basis? Call it $u.$ It is expressed as $r x + s y,$ for $x,y$ the columns of your matrix. If $\gcd(r,s) = g > 1,$ then $u/g$ is a strictly shorter vector in the lattice.

ORIGINAL: Take a shortest vector $u,$ and a fairly short vector $v,$ with $$ u \cdot u = a, \; \; u \cdot v = b, \; \; v \cdot v = c. $$ Without loss of generality, $u$ is in the first quadrant. If $v$ is in the second or fourth quadrant we are done. If $v$ is in the third quadrant, replace by $-v.$ So now both are in the first quadrant, the angle $\theta$ between them is below $\pi/2$ and we get $$ 1 > \cos \theta = \frac{b}{\sqrt{ac}} > 0. $$ So $$ 0 \leq b \leq a \leq c $$ and $$ b^2 < a c. $$

So, take the fairly short vector $v$ and subtract off multiples of $u$. We know that $u$ is shortest so for any integer $k$
$$ | v - k u|^2 \geq |u|^2 = a. $$

Now, take the circle of radius $\sqrt a$ around the origin. For real $t,$ we know that, if the line $v - t u$ passes through the circle at all, the length of the segment of intersection is no longer than $\sqrt a,$ otherwise there would be an integral value of $t$ giving a lattice point inside the circle, which is forbidden. It follows that the point of closest approach to the origin is not closer than $\frac{\sqrt{3a}}{2}.$ In turn, pretending that the line passes through the fourth quadrant next, the length of the line segment between the intersections with the $x$ and $y$ axes is no shorter than $$ \sqrt {3a} > \sqrt a.$$ That is, there is an integral value $t = t_0$ for which $v - t_0 u$ lies in the fourth quadrant. The new basis for the lattice is $$u, v-t_0 u.$$

share|cite|improve this answer
Thanks for this - a nice argument. – Anthony Quas Jun 19 '12 at 4:52

Here is an other proof.

I will construct a hexagon with the vertices $u, v, w, -u, -v, -w$ from your lattice $L$ such that $$\angle(u,v),\ \angle(v,w),\ \angle(w,-u)\le \tfrac\pi2$$ and such that each pair $$(u,v),\ (v,w),\ (w,-u),\ (-u,-v),\ (-v,-w), (-w,u)$$ forms a basis of $L$. Clearly in this case one of these bases will satisfy your condition.


  • Take $u$ in $L$ which minimize the norm.
  • Take $v$ in $L\backslash\langle u\rangle$ which minimize the norm.

Note that $u$ and $v$ form a basis of $L$. WLOG we may assume that $\angle(u,v)\le\tfrac\pi2$. Note that for $w=v-u$ all the above conditions hold.

share|cite|improve this answer
Another very nice creative argument - thank you! – Anthony Quas Jun 19 '12 at 15:38

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.