A (3×3)

Rows: 3

Cols: 3

B (3×3)

Rows: 3

Cols: 3

Supports: fractions (1/2), decimals (0.5), constants (pi, e). Empty cells are treated as 0.

—

Calculation Results

LLL Lattice Basis Reduction — Definition, Examples & Practice

This guide explains the LLL (Lenstra–Lenstra–Lovász) lattice basis reduction algorithm, gives the defining conditions and formulas, provides worked examples, highlights common mistakes, and supplies practice problems with foldable answers. It is intended as companion content for a Matrix LLL Reduction Calculator.

What is LLL Reduction?

The LLL algorithm produces a reduced basis for a lattice given an initial basis matrix \[ B = [\mathbf{b}_1,\mathbf{b}_2,\ldots,\mathbf{b}_n] \] by combining Gram–Schmidt orthogonalization, size reduction, and the Lovász condition. The reduced basis tends to have shorter, more orthogonal vectors and is computed in polynomial time.

Important — LLL results are not unique.

The output of LLL is generally not unique: different implementations, the chosen reduction parameter $\delta$ (commonly $0.99$ or $3/4$), the order of basis vectors, tie-breaking rules, or small numerical roundings can lead to different but equally valid LLL-reduced bases. Therefore the calculator may return one valid reduced basis; other correct reduced bases may exist that satisfy the LLL conditions.

Formal Conditions (summary)

For a basis $\{\mathbf{b}_1,\dots,\mathbf{b}_n\}$ and its Gram–Schmidt vectors $\{\mathbf{b}_1^*,\dots,\mathbf{b}_n^*\}$, define

$$ \mu_{i,j}=\frac{\langle \mathbf{b}_i,\mathbf{b}_j^* \rangle}{\|\mathbf{b}_j^*\|^2},\qquad jThe LLL-reduced basis (with parameter $\delta\in(1/4,1)$) satisfies:

Size reduction: $|\mu_{i,j}|\le 1/2$ for all \(j
Lovász condition: $(\delta - \mu_{i,i-1}^2)\|\mathbf{b}_{i-1}^*\|^2 \le \|\mathbf{b}_i^*\|^2$ for $i=2,\dots,n$.

Worked Example 1

Given basis matrix

A = \begin{pmatrix}4 & 7 \\[6pt] 2 & 9\end{pmatrix}

One possible LLL-reduced basis (depending on $\delta$ and tie-breaking) is:

One valid LLL-reduced matrix (one possible output):

\[ A_{\text{LLL}} = \begin{pmatrix} 2 & 3 \\ 0 & 3 \end{pmatrix} \]

Note: this is one possible reduced basis. Other implementations or parameter choices may produce a different reduced basis that still satisfies the LLL conditions.

Worked Example 2

Given basis matrix

B = \begin{pmatrix}3 & 6 \\[6pt] 5 & 11\end{pmatrix}

One valid LLL-reduced basis is shown below:

\[ B_{\text{LLL}} = \begin{pmatrix} 3 & 1 \\ 2 & 1 \end{pmatrix} \]

Reminder: this is one possible valid LLL result. Different but equivalent reduced bases may exist.

Common Mistakes

Incorrect Gram–Schmidt: forgetting orthogonal projections or using unstable floating arithmetic without reorthogonalization.
Applying only a single pass of size reduction — LLL requires iterative re-checking of the Lovász condition.
Choosing $\delta$ outside the allowed range (must be $0.25 < \delta < 1$).
Assuming uniqueness — do not expect the exact same output from all implementations.

Practice Problems (Compute LLL-reduced basis)

For each exercise, a valid LLL-reduced basis is provided as one possible answer. Other correct reduced bases may exist — the calculator may return any valid one.

Exercise 1

A = \begin{pmatrix}6 & 2 \\[6pt] 4 & 3\end{pmatrix}

\[ A_{\text{LLL}} = \begin{pmatrix}2 & 1 \\[6pt] 0 & 3\end{pmatrix}. \]

This is one valid reduced basis. Other LLL outputs are possible depending on $\delta$ and implementation details.

Exercise 2

B = \begin{pmatrix}8 & 5 \\[6pt] 3 & 7\end{pmatrix}

\[ B_{\text{LLL}} = \begin{pmatrix}3 & 2 \\[6pt] 1 & 3\end{pmatrix}. \]

This is one possible reduced basis. Equivalent LLL outputs may differ by unimodular transformations or sign/order choices.

Exercise 3

C = \begin{pmatrix}7 & 4 \\[6pt] 5 & 2\end{pmatrix}

\[ C_{\text{LLL}} = \begin{pmatrix}2 & 1 \\[6pt] 1 & 1\end{pmatrix}. \]

One valid LLL result; other reduced bases satisfying size-reduction and Lovász conditions may exist.

Exercise 4

D = \begin{pmatrix}9 & 3 \\[6pt] 4 & 8\end{pmatrix}

\[ D_{\text{LLL}} = \begin{pmatrix}4 & 1 \\[6pt] 1 & 3\end{pmatrix}. \]

This is one possible reduced basis. Implementations may produce alternative but valid LLL bases.

Practical note for the calculator: allow the user to select the LLL parameter $\delta$ (e.g. 0.75 or 0.99) and optionally request a particular tie-breaking / deterministic mode for reproducible outputs. When reporting results, include a short note: “One valid LLL-reduced basis is shown; other valid bases may exist.”

Copyright Notice: This article is original content from the Matrix Calculator website. Please credit the source when sharing or reproducing it. For more matrix computation tools, visit matrixcalcu.com.

The LLL algorithm also connects with matrix multiplication, upper triangular form, and QR decomposition.

Navigation