Gram-Schmidt Orthogonalization

Overview

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

bi=bij=1i1μi,jbjμi,j=bi,bjbj,bjb_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 μi,j\mu_{i,j}is the Gram-Schmidt coefficients.

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

bi,bj={0ijbi2i=j\langle b_i^*,b_j^*\rangle=\begin{cases}0&i\neq j\\\left\lVert b_i^*\right\rVert^2&i=j\end{cases}

Let B\mathcal Bbe the matrix where the iith row is given by bib_iandB\mathcal B^*be the matrix where the iith row is given by bib_i^*, then the Gram-Schmidt orthogonalization gives us B=μB\mathcal B=\mu\mathcal B^*where μi,i=1,μj,i=0\mu_{i,i}=1,\mu_{j,i}=0and μi,j\mu_{i,j}is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of R4\mathbb R^4:

b1=(1231)b2=(6451)b3=(5513)\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, B\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 B=μB\mathcal B=\mu\mathcal B^* and that the rows of B\mathcal B^*are orthogonal to each other.

A useful result is that

det(BBT)=det(BBT)=ibi\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 bib_i^*is orthogonal.

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

3) Show that μμT=1\mu\mu^T=1and BBT\mathcal B^*\mathcal B^{*T} is a diagonal matrix whose entries are bi\left\lVert b_i^*\right\rVert. Conclude that det(BBT)=det(BBT)=ibi\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 B=LDO\mathcal B=LDOwhere LLis a lower diagonal matrix with 11on its diagonal, DDis a diagonal matrix and OOan orthogonal matrix, meaning OOT=1OO^T=1, show that B=DO\mathcal B^*=DOand μ=L\mu=L. Furthermore, prove that such a decomposition is unique.