[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/gram_schmidt.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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’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.