Orthonormal basis and Gram-Schmidt orthogonalisation

Andrew Thangaraj

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