Guides / Linear algebra

Gram–Schmidt and the QR decomposition: subtract the projections, normalize, then R = QᵀA

Gram–Schmidt turns any set of independent vectors into an orthonormal set that spans the same space: perpendicular vectors of length 1. It works one vector at a time, removing from each new vector the parts that point along the directions already found. Kept as a matrix factorization, the same arithmetic is A = QR, which is how least-squares problems are solved in practice. The mistakes come from a projection that isn't divided by a · a, an R built with the transpose the wrong way around, and a tall Q treated as if QQ^T were the identity.

Why it works

Split b into a part along a and a part perpendicular to a. The part along a is some multiple ta, and the rest, b − ta, must have zero dot product with a: a · b − t(a · a) = 0, so t = (a · b)/(a · a). Subtracting the projection leaves exactly the perpendicular part. Gram–Schmidt does this repeatedly: what is left of a_j after removing its components along q₁, …, q_j−1 is perpendicular to all of them. Because the q's are already perpendicular to each other, the projections can be subtracted one at a time without interfering.

Rearranged, each step says a_j = (q₁ · a_j) q₁ + ⋯ + ‖u_j‖ q_j: column j of A is a combination of the first j columns of Q only. Those coefficients are column j of R, which is why R is upper triangular. Since Q^TQ = I, multiplying A = QR on the left by Q^T gives R = Q^TA.

Example 1: projection onto a line

Project b = (4, 7) onto the line through a = (1, 2).

1. a · b = 4 + 14 = 18, a · a = 1 + 4 = 5The two dot products the formula needs.
2. p = 185(1, 2) = (3.6, 7.2)The coefficient 18/5 is a · b divided by a · a, because a isn't a unit vector.
3. b − p = (0.4, −0.2), (0.4, −0.2) · (1, 2) = 0The leftover is perpendicular to a, which is the check that the projection is right.

Example 2: Gram–Schmidt in the plane, and coordinates by dot products

Apply Gram–Schmidt to a₁ = (1, 2) and a₂ = (3, 1), then write x = (4, 7) in the new basis.

1. q₁ = 1√5(1, 2)‖a₁‖ = √5.
2. u₂ = (3, 1) − 55(1, 2) = (2, −1)a₁ · a₂ = 3 + 2 = 5 and a₁ · a₁ = 5. Check: (2, −1) · (1, 2) = 0.
3. q₂ = 1√5(2, −1)‖u₂‖ = √5.
4. x = 18√5 q₁ + 1√5 q₂In an orthonormal basis each coordinate is a dot product: q₁ · x = (4 + 14)/√5 and q₂ · x = (8 − 7)/√5. No system to solve. Check: (18(1, 2) + (2, −1))/5 = (20, 35)/5 = (4, 7).

Example 3: the QR decomposition of a 3×2 matrix

Find the QR decomposition of A = 24152−2.

1. q₁ = 13(2, 1, 2), r₁₁ = 3‖a₁‖ = √(4 + 1 + 4) = 3.
2. r₁₂ = q₁ · a₂ = (8 + 5 − 4)/3 = 3The component of a₂ along q₁.
3. u₂ = (4, 5, −2) − 3 · 13(2, 1, 2) = (2, 4, −4)Subtract that component. Check: (2, 4, −4) · (2, 1, 2) = 4 + 4 − 8 = 0.
4. r₂₂ = ‖u₂‖ = 6, q₂ = 13(1, 2, −2)√(4 + 16 + 16) = 6.
5. Q = 1321122−2, R = 3306Check the first column of QR: 3q₁ = (2, 1, 2) = a₁. The second: 3q₁ + 6q₂ = (2, 1, 2) + (2, 4, −4) = (4, 5, −2) = a₂.

Example 4: least squares with QR

Find the least-squares solution of Ax = b for the A of Example 3 and b = (1, 2, 7).

1. Q^Tb = (6, −3)q₁ · b = (2 + 2 + 14)/3 = 6 and q₂ · b = (1 + 4 − 14)/3 = −3: the coordinates of the projection of b in the basis q₁, q₂.
2. 3306 x̂ = 6−3With A = QR, AᵀA = RᵀR and Aᵀb = RᵀQᵀb, so the normal equations AᵀAx̂ = Aᵀb become Rx̂ = Qᵀb once the invertible Rᵀ is canceled.
3. x̂₂ = −12, x̂₁ = (6 − 3(−½))/3 = 52Back substitution, bottom row first, as with any triangular system.
4. Ax̂ = (3, 0, 6)The best fit: (5/2)(2, 1, 2) − (1/2)(4, 5, −2). It is the projection of b onto the plane of the columns.
5. b − Ax̂ = (−2, 2, 1), length 3The residual is perpendicular to both columns of A: (−2, 2, 1) · (2, 1, 2) = 0 and (−2, 2, 1) · (4, 5, −2) = 0. That is what makes x̂ the best fit.

Common mistakes, and the exact line they happen on

1. Projecting without dividing by a · a

The second step of Example 2.

1. a₁ · a₂ = 5Right so far.
2. u₂ = (3, 1) − 5(1, 2) = (−2, −9)This is the mistake. (a · b)a is the projection only when a is a unit vector. ‖a₁‖² = 5, so the coefficient is 5/5 = 1. The check catches it at once: (−2, −9) · (1, 2) = −20, not 0. Either divide by a · a, or normalize first and use q₁.

2. R computed as AᵀQ

The decomposition from Example 3.

1. Q = 1321122−2Right so far.
2. R = A^TQ = 3036This is the mistake. AᵀQ is the transpose of QᵀA, so it comes out lower triangular, which is already the warning. Multiplying back, its first column gives 3q₁ + 3q₂ = (3, 3, 0), not a₁ = (2, 1, 2). Row i of R is q_i dotted with each column of A: R = QᵀA.

3. Treating QQᵀ as the identity

The least-squares problem from Example 4.

1. Q^TQ = IRight so far: the columns of Q are orthonormal.
2. Ax̂ = QRx̂ = QQ^Tb = b, so the fit is exactThis is the mistake. Q is 3×2, so it has no inverse, and QQᵀ is not I. It is the projection onto the plane spanned by the columns: QQᵀb = 6q₁ − 3q₂ = (3, 0, 6), not (1, 2, 7). Only a square Q has QQᵀ = I. A quick check: the trace of QQᵀ is 2, the dimension of the plane, while the trace of the 3×3 identity is 3.

Practice

1. Find the angle between (1, 0, 1) and (0, 1, 1).

   Show answer

   cos θ = 1√2 · √2 = 12, so θ = 60°.

2. Apply Gram–Schmidt to (1, 1, 0) and (1, 0, 1).

   Show answer

   q₁ = (1, 1, 0)/√2. The coefficient is ½, so u₂ = (1, 0, 1) − ½(1, 1, 0) = (½, −½, 1), and q₂ = (1, −1, 2)/√6.

3. Find the QR decomposition of A = 023344.

   Show answer

   q₁ = (0, 3, 4)/5, q₁ · a₂ = 25/5 = 5, u₂ = (2, 3, 4) − (0, 3, 4) = (2, 0, 0), so q₂ = (1, 0, 0), and R = 5502.

4. With q₁ = (1, 1)/√2 and q₂ = (1, −1)/√2, write (5, 1) as c₁q₁ + c₂q₂.

   Show answer

   c₁ = 6/√2 = 3√2 and c₂ = 4/√2 = 2√2.

5. For A = 1321, find R, and use det A = det Q · det R to get det A.

   Show answer

   From Example 2, R = √5√50√5, with det R = 5. Q = 1√5122−1 has det Q = −1, so det A = −5, which matches 1 − 6. R gives |det A|; the sign comes from Q.