Extending a closest point to a basis for a lattice

Question

We are given a lattice $\Lambda$ in $\mathbb{R}^2$, and we are given that it contains a basis of 2 vectors, such that the integer combinations span the whole space.

Now we choose some $u$ in $\Lambda$, such that $|u|$ is minimal. We want to show that we can find a basis for $\Lambda$ for which it contains $u$.

We are also given that if the parallelogram generated by 2 elements of the lattice contains no other points of the lattice, then these 2 elements form a basis for the lattice.

Therefore we can take $v \in \Lambda$ linearly independent with $u$, such that $|v|$ is minimal. This works, and we can show it by looking at the parallelogram generated by $u$ and $v$, and seeing that if a point where inside that parallelogram, it must form a distance strictly less than $|u|$, which was minimal by assumption.

My question is this: It seems really obvious that we can extend $u$ to a basis containing $u$, and I feel like I am using many steps to prove something obvious. Is there a much easier way of doing this?

Answer 1

Here is an alternate proof that there is a lattice basis that contains $u$. Let $B = [b_1, b_2]$ be any basis of $\Lambda$. We can write $u = B c$ where $c \in \mathbb{Z}^2$. Observe that the entries in $c$ are coprime to each other, i.e., $gcd(c_1, c_2) = 1$ where $c = [c_1, c_2]^T$. If $gcd(c_1, c_2) = g \neq 1$, then $u/g$ is also a vector in the lattice $\Lambda$ such that $\|u/g\| < \|u\|$, contradicting the minimality of $u$.

Given that $gcd(c_1, c_2) = 1$, we can find two integers $d_1, d_2$ such that $c_1\cdot d_1 - c_2 \cdot d_2 = 1$ (Bezout's identity). This means that the matrix

$$U = \begin{bmatrix} c_1 & d_2 \\ c_2 & d_1 \end{bmatrix}$$

is unimodular. Therefore, $B U = [u, u']$ is a basis of $\Lambda$ that contains $u$.

Observe that the only fact about $u$ that we used is that $u/g$ is not a lattice vector when $|g| > 1$. So, if we start with any vector $u$ with this condition, then it can be extended to a basis of the lattice.