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.

Experiment

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

2. 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).