Course contentsShow
← Mathematics
Lesson 2243 of 3,12146. Linear Algebra — Inner Products and OrthogonalityFree lesson

Computing QR: Step-by-Step Algorithm

Working through the complete algorithm to find Q and R for a given matrix using orthonormalization.

Computing QR: Step-by-Step Algorithm

What You'll Learn

You'll learn the explicit, step-by-step procedure to compute the QR decomposition of any matrix using the Gram-Schmidt process.

The Core Algorithm

The QR decomposition factors a matrix A into A = QR, where Q is an orthogonal matrix (with orthonormal columns) and R is upper triangular. Here's the complete algorithm:

Step 1: Apply Gram-Schmidt to the Columns of A

Let A = [a₁ a₂ ... aₙ] be your matrix with columns a₁, a₂, etc.

  1. Start with u₁ = a₁
  2. For each subsequent column k = 2 to n:
    • Compute uₖ = aₖ - proj_{u₁}(aₖ) - proj_{u₂}(aₖ) - ... - proj_{uₖ₋₁}(aₖ)
    • Each projection is: proj_{uⱼ}(aₖ) = (aₖ · uⱼ / uⱼ · uⱼ)uⱼ

Step 2: Normalize to Get Q

Divide each orthogonal vector by its length:

  • qₖ = uₖ / ||uₖ||
  • Form Q = [q₁ q₂ ... qₙ]

Step 3: Compute R

The matrix R contains the "ingredients" needed to reconstruct A from Q:

  • R is upper triangular: Rᵢⱼ = 0 when i > j
  • Diagonal entries: Rₖₖ = ||uₖ|| (the normalizing factors)
  • Upper entries: Rᵢⱼ = qᵢ · aⱼ for i < j

Think of it this way: Q holds your orthonormal basis vectors, and R records how much of each original column lies in each basis direction.

Example Pattern for a 3×3 Matrix

After Gram-Schmidt and normalization, compute R entry-by-entry using dot products between Q's columns and A's original columns.

Key Takeaway: The QR algorithm is just Gram-Schmidt (orthogonalize → normalize) plus bookkeeping the transformation coefficients in the upper-triangular matrix R.