Return to Answer

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.

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.$$

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.$$

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.$$

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.

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.$$

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 {\frac{3a}{2}} > \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.$$

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.$$