The Gram-Schmidt Process

The Gram-Schmidt process is s a simple algorithm for producing an orthogonal or orthonormal basis for any nonzero subspace of Rn.

Example: Let W = Span {x1, x2}, where x1 = [3, 6, 0] and x2 = [1, 2, 2]. Construct an orthogonal basis {v1, v2} for W.

The component of x2 is orthogonal to x1 is x2 - p, which is in W because it is formed from x2 and a  multiple of x1. Let v1=x1 and 

v2 = x2 - p = x2 - x2*x1/x1*x1 (*x1) = [1, 2, 2] - 15/45[3, 6, 0] = [0, 0,2].

Then {v1, v2} is an orthogonal basis set of nonzero vectors in W. Since dim W = 2, the set {v1, v2} is a basis for W. 

Theorem 11: The Gram-Schmidt Process: Given a basis {x1, ......., xp} for a nonzero subspace W of Rn, define 

v1=x1

v2 = x2 - x2*v1/v1*v1 *(v1)

v3 = x3 - x3*v1/v1*v1 *(v1) - x3*v2/v2*v2 *(v2)

vp = xp - xp*v1/v1*v1 *(v1) - xp*v2/v2*v2 *(v2) - xp*vp-1/vp-1*vp-1

Then {v1,....,vp} is an orthogonal basis for W. In addition Span {v1,....,vp} = Span{x1,....,xk} 

for 1< k<p.

Orthonormal  Bases: 

An orthonormal basis is constructed easily from an orthogonal basis {v1,.....vp}, simply normalize all the vk.

Example: In the first example we constructed the orthogonal basis v1 = [3, 6, 0] and v2 = [0, 0, 2] an orthogonal basis is 

u1= 1/||v|| (v1)= 1/sqrt(45) [3, 6, 0] = [1/sqrt(5), 2/sqrt(5), 0]

u2 = 1/||v|| (v2) = [0, 0, 1]

Fun Fact: QR Factorization of Matrices: 

if an m x n matrix A has linearly independent columns x1,....,xn then applying the Gram-Schmidt process (with normalizations) to x1,...., xn amounts to factoring A as described in the next theorem. This factorization is widely used in computer algorithms for various computations, such as solving equations. 

Theorem 12: The QR Factorization: If A is an m x n matrix with linearly independent columns, then A can be factored as A = QR, where Q is an m x n matrix whose columns form an orthonormal basis for ColA and R is an n x n upper triangular matrix with positive entries on its diagonal. 

Example: Find a QR factorization for A= [1, 0, 0]

                                                                   [1, 1, 0]

                                                                   [1, 1, 1]

                                                                   [1, 1, 1]

The columns of A are the vectors x1, x2 and x3. An orthogonal basis for Col A= Span{x1, x2, x3}. 

v1= [1, 1, 1, 1]

v2 = [-3, 1, 1, 1]

v3 = [0, -2/3, 1/3, 1/3]

To simplify the arithmetic, scale v3 by letting v'3 = 3v3. Then normalize the three vectors to obtain u1, u2, and u3 and use these vectors as the columns of Q: 

Q= [1/2, -3/sqrt(12), 0]

      [1/2, 1/sqrt(12), -2/sqrt(6)]

      [1/2, 1/sqrt(12), 1/sqrt(6)]

      [1/2, 1/sqrt(12), 1/sqrt(6)]

By construction, the first k columns of Q are an orthonormal basis of Span [x1,.....,xn}. From the proof of Theorem 12, A = QR for some R. To find R, observe that Q(transpose)Q = 1, because the columns of Q are orthonormal. Hence

Q(transpose)A= Q(transpose)(QR)= IR=R

R= [1/2, 1/2, 1/2, 1/2]

      [-3/sqrt(12), 1/sqrt(12), 1/sqrt(12), 1/sqrt(12)]

      [0, -2/sqrt(6), 1/sqrt(6), 1/sqrt(6)]

* A = [2, 3/2, 1]

          [ 0, 3/sqrt(12), 2/sqrt(12)]

          [0, 0, 2/sqrt(6)]

Examine Problems: 

1.) The columns of Q are obtained by applying the Gram-Schmidt process to the columns of A. Find an upper triangular matrix R such that A=QR. 

A(2, 4) matrix = [ 5, 9, 1, 5, -2, -4, 1, 5]

Q(2, 4) matrix = [-1, 6, 6, 3, -8, 3, 1, -2]

2.) The given set is a basis for a subspace of W. Use the Gram-Schmidt process to produce an orthogonal basis for W. 

[3, 0, 1], [8, 2, 5]