Saturday, May 3, 2014

Gram–Schmidt process and conjugation

The Gram–Schmidt process is a procedure to get orthogonal or orthonormal vectors out of a set of linearly independent vectors. It works as follows:

To get an geometric intuition for it, see the construction below:

The first two steps are straight-forward, suppose we now have $u_1, e_1, u_2, e_2$ in hand, and want to get $u_3, e_3$.

In the figure, let $EC = v_3$, and $EA = \text{proj}_{e_1}v_3, \; EB = \text{proj}_{e_2}v_3, \; ED = \text{proj}_{e_2}v_3 + \text{proj}_{e_2}v_3$ , then we claim $DC = u_3$. To justify we need to prove $DC \perp EA$ and $DC \perp EB$.

If we see from the top, we know since $DE$ is the sum of AE and BE, AEBD is a rectangle. So $EA \perp AD$, but we also know $EA \perp AC$, so $EA \perp$ the plane $ACD$, therefore $EA \perp CD$. The other half of the proof is similar.

We can also sort it out with algebra:

\begin{align*} \text{proj}_{e_1}v_3 &= \frac{e_1 \cdot v_3}{e_1 \cdot e_1} e_1 \\ &= (e_1 \cdot v_3) e_1 \\ \text{proj}_{e_2}v_3 &= \frac{e_2 \cdot v_3}{e_2 \cdot e_2} e_2 \\ &= (e_2 \cdot v_3) e_2 \\ \end{align*} \begin{align*} & u_3 \cdot e_1 \\ &= (v_3 - (e_1 \cdot v_3) e_1 - (e_2 \cdot v_3) e_2) \cdot e_1 \\ &= v_3 \cdot e_1 - e_1 \cdot v_3 \\ &= 0 \\ \end{align*}

You can imagine there is an identity matrix here:

\begin{align*} \text{proj}_{e_1}v_3 &= \frac{e_1^T I v_3}{e_1^T I e_1} e_1 \\ &= (e_1 \cdot v_3) e_1 \\ \text{proj}_{e_2}v_3 &= \frac{e_2^T I v_3}{e_2^T I e_2} e_2 \\ &= (e_2 \cdot v_3) e_2 \\ \end{align*}

If we substitute I with some other matrix A, then we can generalize the Gram Schmidt process into the so-called Gram Schmidt conjugation.