QR Factorization

Gram–Schmidt as a matrix product: A = QR.

The idea

The QR factorization writes a matrix $A$ with independent columns as $A = QR,$ where $Q$ has orthonormal columns — unit length and mutually perpendicular, so $Q^{T}Q = I$ — and $R$ is upper triangular.

Algorithm.

Algorithm: Gram–Schmidt QR Input: a matrix A with independent columns a_1, ..., a_n Output: Q with orthonormal columns q_1, ..., q_n and upper-triangular R with A = QR 1. q_1 = a_1 / ‖a_1‖; record R_11 = ‖a_1‖ 2. take the next unprocessed column a_k v_k = a_k - (q_1ᵀa_k) q_1 - ... - (q_(k-1)ᵀa_k) q_(k-1) // v_k is orthogonal to every earlier q_j record each coefficient: R_jk = q_jᵀa_k 3. q_k = v_k / ‖v_k‖; record R_kk = ‖v_k‖ // q_1, ..., q_k stay orthonormal 4. if unprocessed columns remain, go to step 2 5. return Q = [q_1, ..., q_n] and the recorded R

The figure shows step 2 for the second column: subtracting $(q_{1}^{T}a_{2})\,q_{1}$ from $a_{2}$ leaves $v_{2}$ orthogonal to $q_{1}$.

The recorded entries rebuild each processed column, $a_{k} = R_{1k}\,q_{1} + \cdots + R_{kk}\,q_{k}$, which is the factorization $A = QR$ read column by column. Because $q_{k}$ is built from $a_{1}, \ldots, a_{k}$ alone, no $a_{k}$ involves a later $q$, so every entry of $R$ below the diagonal is zero. And since $Q^{T}Q = I$, multiplying $A = QR$ on the left by $Q^{T}$ gives $R = Q^{T}A$.

Ways to work on it

• Walkthrough. Build A = QR from Gram–Schmidt on the columns.
• Practice. Normalize a column to a unit vector of Q.
• Hardest. Complete the QR factorization of a small matrix.

Not sure where to start? Take the ten-question placement test.