1 of 1

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()

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

A useful result is that

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

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

Gram-Schmidt Orthogonalization

Overview

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}

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