# Linear Algebra - Orthogonalization - Building an orthogonal set of generators

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

## 3 - Computation

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

$$Span \{ v_1^* , \dots , v_n^* \} = Span \{v_1, \dots , v_n\}$$

# 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:

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.

### 3.1 - Property

#### 3.1.1 - 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.

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

• First iteration, since the set $\{v_0\}$ is trivially a set of mutually orthogonal vectors:
• $v^*_0 = v_0$
• or as matrix equation: $[v_1] = [v^*_1] $
• Second Iteration, $v^*_1$ is the the projection orthogonal of $v_1$ to $v^*_0$ then:
• $v_1 = v^*_1 + \sigma_{01} v^*_0$
• or as matrix equation: $[v_1] = \begin{bmatrix}v^*_0 & v^*_1 \end{bmatrix} \begin{bmatrix}\sigma_{01} \\ 1 \end{bmatrix}$
• Third iteration: $v^*_2$ is the projection of $v_2$ orthogonal to $v^*_0$ and $v^*_1$:
• $v_2 = v^*_2 + (\sigma_{02} v^*_0 + \sigma_{12} v^*_1)$
• or as matrix equation: $[v_2] = \begin{bmatrix}v^*_0 & v^*_1 & v^*_2 \end{bmatrix} \begin{bmatrix}\sigma_{02} \\ \sigma_{12} \\ 1 \end{bmatrix}$
• 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

$$\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}$$

The two matrices on the right are special: