# Orthonormal basis and Gram-Schmidt orthogonalisation

Aug-Nov 2020

## Recap

• Vector space $V$ over a scalar field $F$
• $F$: real field $\mathbb{R}$ or complex field $\mathbb{C}$ in this course
• $m\times n$ matrix A represents a linear map $T:F^n\to F^m$
• dim null $T$ + dim range $T$ = dim $V$
• Linear equation: $Ax=b$
• Solution (if it exists): $u+$ null$(A)$
• Four fundamental subspaces of a matrix
• Column space, row space, null space, left null space
• Eigenvalue $\lambda$ and Eigenvector $v$: $Tv=\lambda v$
• A linear map is represented by an upper triangular matrix
• Some linear maps are diagonalizable
• Inner products, norms
• Orthogonality and related properties

## Orthonormal list of vectors

$V$: inner product space

$e_1,\ldots,e_m$: orthonormal if

1. $\lVert e_i\rVert=1$
2. $\langle e_i,e_j\rangle=0$, $i\ne j$

Examples

1. Standard basis

2. $\{(1/\sqrt{2},1/\sqrt{2}),(1/\sqrt{2},-1/\sqrt{2})\}$

## Orthonormality and linear independence

If $e_1,\ldots,e_m$: orthonormal, $\lVert a_1e_1+\cdots+a_me_m\rVert^2=\lvert a_1\rvert^2+\cdots+\lvert a_m\rvert^2$

Proof

Direct evaluation using $\lVert e_i\rVert=1$, $\langle e_i,e_j\rangle=0$ for $i\ne j$

Orthonormal set of vectors are linearly independent

Proof

$a_1e_1+\cdots+a_me_m=0$ implies $\lvert a_i\rvert=0$ for each $i$

## Orthonormal basis

An orthonormal basis for $V$ is an orthonormal list of vectors of $V$ that is also a basis.

• An orthonormal list of $n=$ dim $V$ vectors is an orthonormal basis

Examples

Standard basis

$\left(\dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2},\dfrac{1}{2}\right)$, $\left(\dfrac{1}{2},\dfrac{1}{2},\dfrac{-1}{2},\dfrac{-1}{2}\right)$, $\left(\dfrac{1}{2},\dfrac{-1}{2},\dfrac{-1}{2},\dfrac{1}{2}\right)$, $\left(\dfrac{-1}{2},\dfrac{1}{2},\dfrac{-1}{2},\dfrac{1}{2}\right)$

## Coordinates of a vector over an orthonormal basis

$V$: inner product space

Basis: $\{e_1,\ldots,e_n\}$

What are the coordinates of a vector $v$ in above basis?

Suppose basis is orthonormal. $v=\langle v,e_1\rangle e_1+\cdots+\langle v,e_n\rangle e_n$ $\lVert v\rVert^2=\lvert\langle v,e_1\rangle\rvert^2+\cdots+\lvert\langle v,e_n\rangle\rvert^2$

Proof

Use $\lVert e_i\rVert=1$, $\langle e_i,e_j\rangle=0$ for $i\ne j$

## Gram-Schmidt orthonormalisation procedure

$V$: inner product space

1. input: $v_1,\ldots,v_m$, a linearly independent list

2. $e_1=v_1/\lVert v_1\rVert$

3. for $j=2,\cdots,m$ $e_j=\dfrac{v_j-\langle v_j,e_1\rangle e_1-\cdots-\langle v_j,e_{j-1}\rangle e_{j-1}}{\lVert v_j-\langle v_j,e_1\rangle e_1-\cdots-\langle v_j,e_{j-1}\rangle e_{j-1}\rVert}$

4. output: $e_1,\ldots,e_m$, an orthonormal list such that $\text{span}(v_1,\ldots,v_j)=\text{span}(e_1,\ldots,e_j)$ for $j=1,\ldots,m$

Proof: induction on $j$

## Existence and extension

$V$: inner product space, finite-dimensional

$V$ has an orthonormal basis

Proof: Take a basis for $V$ and perform Gram-Schmidt

An orthonormal list of vectors can be extended to an orthonormal basis.

Proof: Extend to a basis and then apply Gram-Schmidt

## Upper triangular matrix representation

$V$: vector space, $T:V\to V$, operator

$B=\{v_1,\cdots,v_n\}$: basis for $V$

$M(T,B)$: matrix of $T$ w.r.t. $B$

$M(T,B)$ is upper triangular if and only if span$(v_1,\cdots,v_j)$ is invariant under $T$ for $j=1,\dots,n$

Proof

$M(T,B)=\begin{bmatrix} a_{11}&\ast&\cdots&\ast\\ 0&a_{22}&\cdots&\ast\\ \vdots&\ddots&\ddots&\vdots\\ 0&\cdots&0&a_{nn} \end{bmatrix}$

Coordinates of $v\in\text{span}(v_1,\cdots,v_j)$ in $B$: non-zero only in first $j$ positions

## Schur’s theorem

$V$: finite-dimensional inner product space over $\mathbb{C}$

$T:V\to V$, operator

There exists an orthonormal basis $B$ such that the matrix of $T$ with respect to $B$ is upper-triangular.

Proof

There exists a basis over which $T$ is upper-triangular. Use Gram-Schmidt on the basis to get $B$.