# Significance of Gram-Schmidt coefficients in LLL algorithm

Let $\{ {\bf v}_1,{\bf v}_2 \}$ be two linearly independent vectors. An orthogonal base $\{{\bf u}_1,{\bf u}_2 \}$ of the vector space $\mathrm{span}\{ {\bf v}_1,{\bf v}_2 \}$ can be computed using Gram-Schmidt Orthogonalization process (GSO) which is summarized by the formulas $${\bf u}_1={\bf v}_1 \quad\text{and}\quad {\bf u}_2={\bf v}_2-\mu_{2,1}{\bf u}_1 \quad\text{where}\quad\mu_{2,1}=\frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||^2}$$ Geometrically it is given as

In order to get ${\bf u}_2$ i.e., orthogonal to ${\bf u}_1$ project ${\bf v}_2$ onto ${\bf u}_1$ and the length of the projection on ${\bf u}_1$ is given by $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$ and to get the direction we multiply the length by the unit vector $\frac{{\bf u}_1}{||{\bf u}_1||}$ and the $\mathrm{proj}_{{\bf u}_1} {\bf v}_2= \frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||}\times \frac{{\bf u}_1}{||{\bf u}_1||},$ where the length of the projection is $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$. In GSO process $\mu_{2,1}=\frac{\text{length of the projection of $$v_2$$ on $$u_1$$}}{||{\bf u}_1||}$ what does $\mu_{2,1}$ represent geometrically?

If $\{ {\bf v}_1,{\bf v}_2 \}$ is the basis of the lattice to solve the shortest vector problem, our aim is to find the orthogonal basis. But orthogonal vectors computed using GSO need not be a basis because $\mu_{2,1}$ need not be an integer.

Since SVP is a hard problem, the LLL algorithm solves approximate SVP. In defining an LLL reduced basis the first requirement is $\mu_{2,1} \le \frac{1}{2}$ (size reduction condition). What does this imply?

• This answer might be helpful. – yyyyyyy Jan 15 '17 at 21:47

Say you have an integer lattice $\mathcal{L}$ with (ordered) basis $B=\{{\bf b}_1,\ldots,{\bf b}_n \},$ ${\bf b}_j\in {\bf Z}^m$, $n\leq m$. As you wrote the first condition of the LLL reduced basis $\{ {\bf u}_1,\ldots,{\bf u}_n\}$ is the process of size reduction. That is $|\mu_{i,j}|\leq \frac{1}{2}$, $j<i$. If you set $M_i=\mathrm{span}({\bf b}_1,\ldots,{\bf b}_i),\ i<n$ then this condition shortens the projection $\mathrm{proj}_{M_i}({\bf b}_{i+1})$, while the second condition (Lovász) shortens the projection $\mathrm{proj}_{M_i^\perp}({\bf b}_{i+1})= {\bf b}_{i+1}^*$.