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

where $\mu_{i,j}$is the Gram-Schmidt coefficients.

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

Let be the matrix where the th row is given by andbe the matrix where the th row is given by , then the Gram-Schmidt orthogonalization gives us where and is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of :

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

This outputs two matrices, and :

One can quickly verify that and that the rows of are orthogonal to each other.

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

1) Show that the basis is orthogonal.

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

3) Show that and is a diagonal matrix whose entries are . Conclude that .

4*) Given the Iwasawa decomposition where is a lower diagonal matrix with on its diagonal, is a diagonal matrix and an orthogonal matrix, meaning , show that and . Furthermore, prove that such a decomposition is unique.