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?



Generators of a 2D lattice
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.$$ 


