4 added 229 characters in body

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

3 added 595 characters in body

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

2 deleted 10 characters in body

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

1