QR Decomposition via Gram-Schmidt
What You'll Learn
You'll learn how to use the Gram-Schmidt process to break a matrix into an orthogonal matrix Q and an upper triangular matrix R.
The Core Idea
Remember that QR decomposition expresses a matrix A as the product of an orthogonal matrix Q (whose columns are orthonormal) and an upper triangular matrix R. The Gram-Schmidt process is the natural tool to build these factors.
Here's how it works:
Step 1: Apply Gram-Schmidt to A's Columns
Take the columns of your matrix A and run them through Gram-Schmidt. This gives you an orthonormal set of vectors—these become the columns of Q.
Step 2: Capture the Coefficients in R
During Gram-Schmidt, each new orthonormal vector is built from the original columns using specific coefficients (inner products and norms). These coefficients naturally arrange themselves into an upper triangular matrix R.
The Connection
Think of it this way: when you apply Gram-Schmidt to the columns a₁, a₂, a₃, ... of A, you're essentially writing each original column as a linear combination of the new orthonormal columns q₁, q₂, q₃, ...:
- a₁ = (some coefficient) × q₁
- a₂ = (coefficient) × q₁ + (coefficient) × q₂
- a₃ = (coefficient) × q₁ + (coefficient) × q₂ + (coefficient) × q₃
Notice the pattern? Each aⱼ only depends on q₁, q₂, ..., qⱼ—never on later q's. This triangular dependency structure is exactly what makes R upper triangular.
The coefficients come directly from the Gram-Schmidt formulas: they're the inner products ⟨aⱼ, qᵢ⟩ and the norms computed during orthonormalization.
Key Takeaway: QR decomposition via Gram-Schmidt simply organizes the orthonormalization process into matrix form—Q holds the orthonormal basis you created, and R records how the original columns relate to that basis.