# Extending a closest point to a basis for a lattice

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?

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.

• Sorry can you explain the “Therefore BU is a basis” part? Commented May 24 at 20:50
• This is a basic fact in lattice theory. $B$ is a basis of a lattice if and only if $BU$ is also a basis of the same lattice where $U$ is any unimodular matrix. See lemma 3 in cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/… Commented May 25 at 3:54
• Also, the matrix $U$ in my proof is unimodular because $U \in \mathbb{Z}^{2 \times 2}$ and the determinant of $U$ is $det(U) = c_1 \cdot d_1 - c_2 \cdot d_2 = 1$. Commented May 25 at 4:07
• I like this solution, thank you for the clarification, but it still requires that inverses of unimodular matrices are unimodular. Which is not super hard. But in total the number of steps is not short, I guess there is no elementary proof (like in three lines). Anyways thanks for the proof Commented May 26 at 5:51