Lattice reduction

In mathematics, the goal of lattice basis reduction is given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.

One measure of nearly orthogonal is the orthogonality defect. This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define. For perfectly orthogonal basis vectors, these quantities would be the same.

Any particular basis of ${\displaystyle n}$ vectors may be represented by a matrix ${\displaystyle B}$, whose columns are the basis vectors ${\displaystyle b_{i},i=1,\ldots ,n}$. In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix ${\displaystyle \det(B)}$. If the number of vectors is less than the dimension of the underlying space, then volume is ${\displaystyle {\sqrt {\det(B^{T}B)}}}$. For a given lattice ${\displaystyle \Lambda }$, this volume is the same (up to sign) for any basis, and hence is referred to as the determinant of the lattice ${\displaystyle \det(\Lambda )}$ or lattice constant ${\displaystyle d(\Lambda )}$.

...
Wikipedia