> For the complete documentation index, see [llms.txt](https://cryptohack.gitbook.io/cryptobook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gram-schmidt-orthogonalization.md).

# Gram-Schmidt Orthogonalization

## Overview

Gram-Schmidt orthogonalization is an algorithm that takes in a basis $$\left{b\_i\right}*{i=1}^n$$ as an input and returns a basis $$\left{b\_i^\*\right}*{i=1}^n$$where all vectors are orthogonal, i.e. at right angles. This new basis is defined as 

$$
b\_i^*=b\_i-\sum\_{j=1}^{i-1}\mu\_{i,j}b\_j^*\quad\mu\_{i,j}=\frac{\langle b\_i,b\_j^*\rangle}{\langle b\_j^*,b\_j^\*\rangle}
$$

where $$\mu\_{i,j}$$is the **Gram-Schmidt coefficients**.

One can immediately check that this new basis is **orthogonal**, meaning

$$
\langle b\_i^*,b\_j^*\rangle=\begin{cases}0\&i\neq j\\\left\lVert b\_i^\*\right\rVert^2\&i=j\end{cases}
$$

Let $$\mathcal B$$be the matrix where the $$i$$th row is given by $$b\_i$$and$$\mathcal B^*$$be the matrix where the $$i$$th row is given by $$b\_i^*$$, then the Gram-Schmidt orthogonalization gives us $$\mathcal B=\mu\mathcal B^\*$$where $$\mu\_{i,i}=1,\mu\_{j,i}=0$$and $$\mu\_{i,j}$$is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of $$\mathbb R^4$$:

$$
\begin{matrix}
b\_1 &= & (&-1&-2&3&1&)\\
b\_2 &= & (&-6&-4&5&1&)\\
b\_3 &= & (&5&5&1&-3&)
\end{matrix}
$$

Instead of doing the Gram-Schmidt orthogonalization by hand, we can get sage to do it for us:

```
B = Matrix([
[-1, -2, 3, 1],
[-6, -4, 5, 1],
[5, 5, 1, -3]])

B.gram_schmidt()
```

This outputs two matrices, $$\mathcal B^\*$$and $$\mu$$:

```
(
[-1 -2  3  1]  [ 1  0  0]
[-4  0 -1 -1]  [ 2  1  0]
[ 0  3  3 -3], [-1 -1  1]
)
```

One can quickly verify that $$\mathcal B=\mu\mathcal B^*$$ and that the rows of $$\mathcal B^*$$are orthogonal to each other.

A useful result is that

$$
\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^\*\mathcal B^{*T}\right)=\prod\_i\left\lVert b\_i^*\right\rVert
$$

Intuitively, this tells us that the more orthogonal a set of basis for a lattice is, the shorter it is as the volume must be constant.

## Exercises

1\) Show that the basis $$b\_i^\*$$is orthogonal.

2\) Verify that the output of sage is indeed correct.

3\) Show that $$\mu\mu^T=1$$and $$\mathcal B^*\mathcal B^{*T}$$ is a diagonal matrix whose entries are $$\left\lVert b\_i^*\right\rVert$$. Conclude that $$\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod\_i\left\lVert b\_i^*\right\rVert$$.  

4\*) Given the Iwasawa decomposition $$\mathcal B=LDO$$where $$L$$is a lower diagonal matrix with $$1$$on its diagonal, $$D$$is a diagonal matrix and $$O$$an orthogonal matrix, meaning $$OO^T=1$$, show that $$\mathcal B^\*=DO$$and $$\mu=L$$. Furthermore, prove that such a decomposition is unique.