---
title: "Gram-Schmidt"
type: concept
related: [Orthonormal, Upper Triangular Matrix, Orthonormal Basis, Invariant Subspace, Norm]
source: https://www.jemoka.com/posts/kbhgram_schmidt/
confidence: high
status: active
---

OMG its Gram-Schmidtting!!! Ok so like orthonormal basis are so nice, don&rsquo;t you want to make them out of boring-ass normal basis? Of course you do.
Suppose \(v_1, &hellip; v_{m}\) is a linearly independent list in \(V\). Now let us define some \(e_{1} &hellip; 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&rsquo;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&lt;j &lt;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, &hellip;, v_{j-1})\) (because \(v_{j}\) are linearly independent). We have then \(v_{j} \not \in span(e_1, &hellip;, e_{j-1})\), given the two spans are equal.
Hence, \(v_{j} - \langle v_{j}, e_{1} \rangle e_{1}- &hellip; - \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}, &hellip;, e_{j-1}\) and would then be in the span thereof, which we know isn&rsquo;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 &lt; 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}, &hellip; 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} &hellip; v_{j}\) to \(e_{1}, &hellip; 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&rsquo;d already orthonormal vector will be \(0\), so nothing will be subtracted.
So, suppose you have an orthonormal list \(e_1, &hellip;, e_{m}\) in \(V\), which because orthonormal list is linearly independent, can be Gram-Schmidt&rsquo;d to the same thing.
As a linearly independent list expends to a basis, go do that. Now Gram-Schmidtting this new thing won&rsquo;t change \(e_1, &hellip; 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&rsquo;t actually change the span; meaning, if you have an upper-triangular matrix, you must have each \(span(v_1, &hellip;v_{j})\) be invariant under \(T\).
Now, recall that Gram-Schmidtting doesn&rsquo;t actually change span; therefore, if each \(span (v_1, &hellip; v_{j})\) is invariant under \(T\), then each \(span(e_1, &hellip; e_{j}) = span(v_1, &hellip; 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&rsquo;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.
