Linear Algebra for Engineers lecture 32: Gram-Schmidt Orthogonalization
Overview
Alex Townsend explains how Gram-Schmidt converts an arbitrary basis into an orthogonal basis by subtracting projections onto vectors already processed, then produces an orthonormal basis by scaling each vector to length one. He works through two- and three-vector examples and connects the procedure to QR factorization, where a matrix A is written as A = QR with Q having orthonormal columns and R upper triangular.
Key takeaways
- For a basis A1, A2, Gram-Schmidt sets U1 = A1 and U2 = A2 minus proj_U1(A2), making U2 perpendicular to U1 without changing the span.
- For each later vector An, subtract projections onto every previously constructed Ui; projecting onto the original vectors instead may fail to produce orthogonality.
- An orthogonal basis becomes orthonormal by dividing each vector by its length, and delaying this step avoids square roots during projection calculations.
- Gram-Schmidt preserves the original column space because every new vector is formed from linear combinations of the original basis vectors.
- In matrix form, Gram-Schmidt produces QR factorization: Q contains orthonormal columns, R is upper triangular, and A = QR.
Chapters
- Alex Townsend recalls that projecting B onto the line spanned by U gives a multiple of U, with the residual perpendicular to the line.
- The orthogonal projection is the closest point on the line to B, so it minimizes the distance from B to any point on that line.
- An orthogonal basis makes it easy to express a vector as a sum of projection components.
- Gram-Schmidt converts an arbitrary basis into an orthogonal basis while preserving its span.
- For a one-dimensional space spanned by A1, the basis is already orthogonal because there are no other vectors to check.
- The procedure begins with U1 = A1 and makes no change in the one-vector case.
- For a basis A1, A2, Townsend sets U1 = A1, then removes from A2 its projection onto the line spanned by U1.
- The resulting vector is U2 = A2 minus proj_U1(A2), which is perpendicular to U1 by construction.
- Because U2 is a linear combination of A1 and A2, it remains in their span; together with U1 it forms a basis for the same plane.
- For A1 = (1, 1, 1, 1) and A2 = (0, 1, 1, 1), the projection coefficient is 3/4.
- The resulting orthogonal pair is U1 = (1, 1, 1, 1) and U2 = (-3/4, 1/4, 1/4, 1/4).
- To make the pair orthonormal, divide each vector by its length, but Townsend recommends postponing this scaling until all projections are finished.
- The process continues from left to right, keeping each completed vector and correcting the next basis vector.
- First compute U2 by removing the projection of A2 onto U1.
- For A3, subtract its projections onto both U1 and U2 so the new U3 is orthogonal to every previously constructed vector.
- Each subtraction uses a linear combination of vectors already in the original span, preserving the space being spanned.
- Townsend applies the three-vector procedure to extend the earlier four-coordinate example with a third vector.
- The calculation requires two projection terms for U3, one for U1 and one for U2.
- The projection targets must be the constructed orthogonal vectors U1 and U2, not the original A2, because U3 must be orthogonal to the new basis.
- The resulting vectors form an orthogonal basis by construction, though the arithmetic involves several fractions.
- For each new vector An, subtract its projections onto all earlier vectors U1 through U(n-1).
- The resulting U1 through Un are orthogonal and span the same space as A1 through An.
- Normalize only after completing the orthogonalization by dividing each Ui by its length.
- Townsend presents orthonormal bases as a generalization of the standard basis, useful in vector spaces beyond Rn.
- Townsend relates Gram-Schmidt to LU factorization: both procedures can be stored as matrix operations rather than repeated from scratch.
- Representing basis vectors as columns turns each Gram-Schmidt update into right multiplication by a matrix.
- These transformations preserve the column space while changing the columns into an orthogonal set.
- The first Gram-Schmidt update leaves the first and third columns unchanged while replacing the second with a combination of the first two.
- A second upper-triangular matrix leaves the first two columns fixed and replaces the third with a combination of all three.
- A final diagonal scaling matrix normalizes the columns, producing a matrix Q with orthonormal columns.
- Combining the upper-triangular transformations gives a factor R, while the orthonormalized columns form Q.
- The resulting QR factorization is A = QR, with R upper triangular and Q having orthonormal columns.
- Townsend notes that the symbols Q and R follow established convention, with Q denoting orthonormal columns and R the upper-triangular factor.
Transcript excerpt
0:00 now saying, "Please come and collect your cup. Make sure you only come one at a time. You need to uh tell us if you're coming at a very popular time." Uh, okay. Um, so today the the joy and excitement is in lecture 33, section 6.4. Okay. This morning I so I planned all these lectures over the Thanksgiving break, but this morning I decided to switch lectures 32 and 33. So I'm calling this lecture 33, but I can still count. This should be lecture 32, but I've switched the order because the final is too close and I want to get this material down. Uh so you have time, you have at least a weekend to think about it. Um so that's
0:48 why I switched these lectures. I still have given you uh almost all the information you need in section 6.3 already. Um so in terms of the homework, we're all still good. Uh I just thought this was the smart thing to do was to switch these around. Okay. So [clears throat] um the so we were looking last time at projections. We were making shadows orthogonal shadows precise, right? Uh this was our way. This is the math formula for a shadow at midday. Uh it's this formula here. This is the orthogonal projection of the vector B onto the line L which is spanned by U which is the span of U. And it's this formula here, right? It's a
1:37 it's a number times U. This is a number here, right? It's a dot product. It's a number divided by another number. And this is a number times U. So this guy is a multiple of U. It lives in the span of U. So this is projecting B onto U. And it's the very particular projection that
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Alex Townsend.