Gauss Lattice Basis Reduction

A lattice is a set of points formed by all integer linear combinations of a set of basis vectors. In 2D, the Gauss lattice reduction algorithm allows us to find a "short" and nearly orthogonal basis for a given lattice, akin to the Euclidean algorithm for integers. The reduction works by iteratively projecting one vector onto the other and subtracting a rounded multiple to shorten it, followed by a swap. A reduced basis guarantees that its first vector is the shortest possible non-zero vector in the lattice.

Worked Example

Let the initial basis be `u = [5, 4]` and `v = [1, 3]`. The squared lengths are `lengthSq(u) = 41` and `lengthSq(v) = 10`.
Because `lengthSq(v) < lengthSq(u)`, we first swap them: `u = [1, 3]`, `v = [5, 4]`.
Next, we find the best integer multiple `q` of `u` to subtract from `v` to minimize its length using the trace calculation `v = v - round((u dot v) / (u dot u)) * u`. This is given by `q = round((u·v) / (u·u))`. Here, `u·v = 1*5 + 3*4 = 17` and `u·u = 10`. So `q = round(17 / 10) = 2`.
Calculation: `v = v - q*u = [5, 4] - 2*[1, 3] = [3, -2]`. The expected calculation result for `v` is exactly `[3, -2]` with a squared length of `13`.
We repeat the process. `lengthSq(u) = 10` is less than `lengthSq(v) = 13`, so we don't swap. We calculate `q = round( (u·v) / (u·u) )`. Here `u·v = 1*3 + 3*(-2) = -3` and `u·u = 10`. So `q = round(-3 / 10) = 0`.
Since `q = 0`, the algorithm terminates. The final result for `v` is `[3, -2]` and `u` is `[1, 3]`. The expected calculation result is `10` for the shortest squared length. Notice that the covolume (determinant magnitude) is preserved at 11 throughout all these steps, confirming they generate the same lattice.

Experiment

Explore how different starting bases require different numbers of reduction steps in theinteractive module. Notice how a "skewed" or "nearly parallel" basis quickly folds in on itself, becoming shorter and more orthogonal with every step.
Watch the trace to see how the algorithm behaves when provided with an exact orthogonal basis (where it immediately stops) or degenerate dependent bases (where the covolume is zero and reduction cannot proceed).

Limitations

This visualization focuses on 2-dimensional integer lattices. In higher dimensions, generalizing this concept leads to the LLL (Lenstra–Lenstra–Lovász) reduction algorithm. While Gauss's algorithm solves the shortest vector problem (SVP) exactly in 2D, LLL only provides an approximation in higher dimensions.

Furthermore, rounding exact half-integers in this module always breaks ties by rounding away from zero. Other variants of the algorithm might specify a different tie-breaking rule, though the resulting basis remains a valid reduced basis.

References

The SageMath reference documentation provides additional rigorous details for implementations of exact lattice basis reductions over integer matrices, which follow similar logic to the algorithm presented here.SageMath Dense Integer Matrices.

Gauss Lattice Basis Reduction