Linear Algebra - Orthogonalization - Building an orthogonal set of generators

Card Puncher Data Processing


Original stated goal: Find the projection of b orthogonal to the space V spanned by arbitrary vectors <math>{v_1} , \dots , {v_n}</math>


  • Input: A list <math>{v_1} , \dots , {v_n}</math> of vectors over the reals
  • output: A list of mutually orthogonal vectors <math>v_1^* , \dots , v_n^*</math> such that

<MATH>Span \{ v_1^* , \dots , v_n^* \} = Span \{v_1, \dots , v_n\}</MATH>

# output: a list of mutually orthogonal vectors.
def orthogonalize(vlist):
    vstarlist = []
    for v in vlist:
        # project orthogonal find the next orthogonal vector
        # and make iteratively a longer and longer list of mutually orthogonal vectors.
        vstarlist.append(project_orthogonal(v, vstarlist))
    return vstarlist


Lemma: Throughout the execution of orthogonalize, the vectors in vstarlist are mutually orthogonal.

Proof: by induction, using the fact that each vector added to vstarlist is orthogonal to all the vectors already in the list.


Order matters

If we run the procedure orthogonalize twice, once with a list of vectors and once with the reverse of that list, the output lists will not be the reverses of each other.

Matrix Equation has a matrix composed of mutually orthogonal vector and an upper triangle matrix

  • First iteration, since the set <math>\{v_0\}</math> is trivially a set of mutually orthogonal vectors:
    • <math>v^*_0 = v_0</math>
    • or as matrix equation: <math>[v_1] = [v^*_1] [1]</math>
  • Second Iteration, <math>v^*_1</math> is the the projection orthogonal of <math>v_1</math> to <math>v^*_0</math> then:
    • <math>v_1 = v^*_1 + \sigma_{01} v^*_0</math>
    • or as matrix equation: <math>[v_1] = \begin{bmatrix}v^*_0 & v^*_1 \end{bmatrix} \begin{bmatrix}\sigma_{01} \\ 1 \end{bmatrix}</math>
  • Third iteration: <math>v^*_2</math> is the projection of <math>v_2</math> orthogonal to <math>v^*_0</math> and <math>v^*_1</math> :
    • <math>v_2 = v^*_2 + (\sigma_{02} v^*_0 + \sigma_{12} v^*_1)</math>
    • or as matrix equation: <math>[v_2] = \begin{bmatrix}v^*_0 & v^*_1 & v^*_2 \end{bmatrix} \begin{bmatrix}\sigma_{02} \\ \sigma_{12} \\ 1 \end{bmatrix}</math>
  • After N Iterations, we will get this matrix equation (formed of two matrix) expressing original vectors in terms of starred vectors. It's not a matrix multiplication

<MATH> \begin{bmatrix} \begin{array}{r|r|r|r} \, \: \; \> & \\ \, \: \; \> & \\ \\ v_0 & v_1 & v_2 & \dots & v_n \ \\ \ \\ \end{array} \end{bmatrix} = \begin{bmatrix} \begin{array}{r|r|r|r} v^*_0 & v^*_1 & v^*_2 & \dots & v^*_n \end{array} \end{bmatrix} \begin{bmatrix} 1 & \sigma_{01} & \sigma_{02} & \dots & \sigma_{0n} \\ & 1 & \sigma_{12} & \dots & \sigma_{1n} \\ & & 1 & \dots & \sigma_{2n} \\ & & & \ddots & \vdots \\ & & & & 1 \\ \end{bmatrix} </MATH>

The two matrices on the right are special:

Discover More
Card Puncher Data Processing
Linear Algebra - Basis of a Vector Space

A basis for vector space V is a linearly independent set of generators for V. Thus a set S of vectors of V is a basis for V if S satisfies two properties: Property B1 (Spanning) Span S = V, and Property...
Card Puncher Data Processing
Linear Algebra - Closest point in higher dimension than a plane

Solving closest point in the span of many vectors Goal: An algorithm that, given a vector b and vectors v1, . . . , vn, finds the vector in Span {v1, . . . , vn} that is closest to b. Special case:...
Card Puncher Data Processing
Linear Algebra - Find a basis computation problem

Find a basis for a vector space Example: Find a basis for the null space of By the dot-product definition of matrix-vector multiplication, a vector v is in the null space of A if the dot-product...
Card Puncher Data Processing
Linear Algebra - Generators of a Vector Space

The generators for the set of vectors are the vectors in the following formula: where is a generating set for {[3, 0, 0], [0, 2, 0], [0, 0, 1]} is a generating set for . = Span {[3, 0,...
Card Puncher Data Processing
Linear Algebra - Orthogonal complement Vector Space

Let U be a of W. For each vector b in W, we can write b as the following projections: where: is in U, and is orthogonal to every vector in U. Let V be the set . V is the orthogonal complement...

Share this page:
Follow us:
Task Runner