Linear Algebra - Orthogonalization - Building an orthogonal set of generators
Table of Contents
About
Original stated goal: Find the projection of b orthogonal to the space V spanned by arbitrary vectors <math>{v_1} , \dots , {v_n}</math>
Articles Related
Computation
- 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
where:
- the project orthogonal function is the high dimensional projection computation of mutually orthogonal vectors.
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.
Property
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. <note warning>It's not a matrix multiplication</note>
<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:
- Columns of first one are mutually orthogonal.
- Second is upper triangular.