Gram-Schmidt — Jemoka Knowledge Base

OMG its Gram-Schmidtting!!! Ok so like orthonormal basis are so nice, don’t you want to make them out of boring-ass normal basis? Of course you do. Suppose v_1, … v_{m} is a linearly independent list in V. Now let us define some e_{1} … e_{m} using the procedure below such that e_{j} are orthonormal and, importantly:

\begin{equation} span(v_1, \dots, v_{m}) = span(e_{1}, \dots, e_{m}) \end{equation}

The Procedure We do this process inductively. Let:

\begin{equation} e_1 = \frac{v_1}{\|v_1\|} \end{equation}

And then, let:

\begin{equation} e_{j} = \frac{v_{j} - \langle v_{j}, e_{1} \rangle e_{1} - \dots -\langle v_{j}, e_{j-1} \rangle e_{j-1}}{\|v_{j} - \langle v_{j}, e_{1} \rangle e_{1} - \dots -\langle v_{j}, e_{j-1} \rangle e_{j-1}\|} \end{equation}

That is, for each vector v_{j}, we subtract out the component which it is already parallel (i.e. not orthogonal, i.e. already accounted by) each other already orthonormal basis. Then we norm the whole thing as lengths don’t matter and we desire norm-1. The Proof We Prove this by induction. Base case: j=1 span (v_1) = span (e_{1}) because, by definition above, e_1 = \frac{v_1}{\|v_1\|}. And hence, they are multiples of each other and hence has the same span. Induction: at 1<j <m So, we have that:

\begin{equation} span (v_1, \dots, v_{j-1}) = span(e_1, \dots, e_{j-1}) \end{equation}

Let now v_{j} \not \in span(v_1, …, v_{j-1}) (because v_{j} are linearly independent). We have then v_{j} \not \in span(e_1, …, e_{j-1}), given the two spans are equal. Hence, v_{j} - \langle v_{j}, e_{1} \rangle e_{1}- … - \langle v_{j}, e_{j-1} \rangle e_{j-1} \neq 0 because otherwise v_{j} would be writable as a linearly combinations of e_{1}, …, e_{j-1} and would then be in the span thereof, which we know isn’t true. Dividing a vector by its norm produces a norm-1 vector; so we have now that e_{j} would be a norm-1 vector. Now, let k < j. We desire that \langle e_{j}, e_{k} \rangle = 0 because we want our new e_{j} to be orthogonal to every other existing vector. We have:

\begin{equation} \langle e_{j}, e_{k} \rangle = \langle \frac{v_{j} - \langle v_{j}, e_{1} \rangle e_{1} - \dots - \langle v_{j}, e_{k} \rangle e_{k} - \dots \langle v_{j}, e_{j-1} \rangle e_{j-1}}{\|v_{j} - \langle v_{j}, e_{1} \rangle e_{1}- \dots - \langle v_{j}, e_{k} \rangle e_{k} - \dots \langle v_{j}, e_{j-1} \rangle e_{j-1}\|}, e_{k} \rangle \end{equation}

Now, if we parcel out the large fraction the bottom, and apply additivity in the first slot, we will note that all of the \langle e_{i \neq k}, e_{k} \rangle=0 as everything already on this list is orthonormal. Finally, then we have only:

\begin{equation} \langle v_{j}, e_{k} \rangle - \langle v_{k}, e_{k} \rangle \langle e_{k}, e_{k} \rangle \end{equation}

on top, which conveniently equals 0. Meaning \langle e_{j}, e_{k} \rangle= 0, so e_{k} is indeed orthogonal to the rest of the list. By definition of e_{j} above, v_{j} can be written as a linear combination of e_{1}, … e_{j-1} as well as a bare e_{j}. Therefore:

\begin{equation} span(v_1, \dots, v_{j}) \subset span (e_1, \dots e_{j}) \end{equation}

Of course, both subspaces are the same dimension and so extending the basis to v_{1} … v_{j} to e_{1}, … e_{j} would be trivial. So they are equal. Phew. \blacksquare Corollary Results Every Inner Product Space has an orthonormal basis Take any basis, Gram-Schmidt it, orthonormal list of the right length is a basis. \blacksquare Orthonormal list extended to orthonormal basis Based on the procedure above, Gram-Schmidt does nothing to already orthonormal vectors: the inner products between any yet-to-be-reghramschmidt’d already orthonormal vector will be 0, so nothing will be subtracted. So, suppose you have an orthonormal list e_1, …, e_{m} in V, which because orthonormal list is linearly independent, can be Gram-Schmidt’d to the same thing. As a linearly independent list expends to a basis, go do that. Now Gram-Schmidtting this new thing won’t change e_1, … e_{m} at all, but will give you extra orthonormal vectors to them which all form the basis as its the right length. Orthonormal upper-triangular matrix basis exists if normal upper-triangular exists Note that Gram-Schmidtting doesn’t actually change the span; meaning, if you have an upper-triangular matrix, you must have each span(v_1, …v_{j}) be invariant under T. Now, recall that Gram-Schmidtting doesn’t actually change span; therefore, if each span (v_1, … v_{j}) is invariant under T, then each span(e_1, … e_{j}) = span(v_1, … v_{j}) after Gram-Schmidtting is still invariant under T. So we can actually build an upper-triangular matrix out of the orthonormalized matrix as well. Schur’s Theorem Support V is a finite-dimensional complex vector space, then T has an upper-triangular matrix w.r.t. an orthonormal basis of V. every complex operator has an upper-triangular matrix; and orthonormal upper-triangular matrix basis exists if normal upper-triangular exists.