01 / 21

QR
Factorization

Learn how to decompose any matrix into the product of an orthogonal matrix \(Q\) and an upper triangular matrix \(R\) using the Gram-Schmidt process.

Linear Algebra

What Is QR Factorization?

QR factorization expresses a matrix \(A\) as the product of two special matrices:

$$ A = QR $$

\(Q\): Orthogonal Matrix
Columns are orthonormal: mutually perpendicular unit vectors. Satisfies \(Q^T Q = I\).
\(R\): Upper Triangular
All entries below the main diagonal are zero. Diagonal entries encode lengths of projections.

Why Does QR Matter?

QR factorization is one of the most important decompositions in applied mathematics. It powers algorithms you encounter everywhere:

Least Squares
Solving \(Ax = b\) when there is no exact solution: regression, curve fitting, data science.
Eigenvalues
The QR algorithm iterates QR factorization to find eigenvalues of any square matrix.
Numerical Stability
More stable than solving normal equations \(A^T A x = A^T b\) directly.

Orthogonality Refresher

u v 90° u · v = 0 Orthogonal vectors

The Gram-Schmidt Process

Gram-Schmidt converts a set of linearly independent vectors into an orthonormal set. It is the engine behind QR factorization.

1
Start with the first column \(\mathbf{a}_1\). Normalize it: \(\mathbf{e}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|\).
2
Subtract projections. For each subsequent column \(\mathbf{a}_k\), remove its components along all previous \(\mathbf{e}_j\).
3
Normalize the result to get \(\mathbf{e}_k\). Repeat until all columns are processed.

Gram-Schmidt Formulas

$$ \mathbf{u}_1 = \mathbf{a}_1, \qquad \mathbf{e}_1 = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|} $$

$$ \mathbf{u}_k = \mathbf{a}_k - \sum_{j=1}^{k-1} \text{proj}_{\mathbf{e}_j}(\mathbf{a}_k) $$

$$ \text{proj}_{\mathbf{e}_j}(\mathbf{a}_k) = (\mathbf{e}_j \cdot \mathbf{a}_k)\,\mathbf{e}_j $$

Visualizing Projection Removal

e₁ a₂ proj u₂ u₂ ⊥ e₁

Building \(Q\) and \(R\)

Once Gram-Schmidt is complete, assemble the matrices:

\(Q\)
\(Q = [\,\mathbf{e}_1 \;|\; \mathbf{e}_2 \;|\; \cdots \;|\; \mathbf{e}_n\,]\)
Columns are the orthonormal vectors.
\(R\)
\(R_{jk} = \mathbf{e}_j \cdot \mathbf{a}_k\) for \(j \leq k\), and \(R_{jk} = 0\) for \(j > k\).

QR vs LU vs SVD

QR LU SVD
Form \(A = QR\) \(A = LU\) \(A = U\Sigma V^T\)
Factors Orthogonal + upper tri Lower tri + upper tri Two orthogonal + diagonal
Best for Least squares, eigenvalues Solving \(Ax = b\) Rank, pseudoinverse
Stability High Moderate Highest
Matrix shape Any \(m \times n\) Square Any \(m \times n\)

How to Compute QR

1
Write columns. Extract the columns \(\mathbf{a}_1, \mathbf{a}_2, \dots\) from matrix \(A\).
2
Orthogonalize. Apply Gram-Schmidt: compute \(\mathbf{u}_k\) by subtracting projections, then normalize to get \(\mathbf{e}_k\).
3
Build \(Q\). Place \(\mathbf{e}_1, \mathbf{e}_2, \dots\) as columns of \(Q\).
4
Build \(R\). Compute \(R = Q^T A\), or fill in entries \(R_{jk} = \mathbf{e}_j \cdot \mathbf{a}_k\).
5
Verify. Confirm \(QR = A\) and \(Q^T Q = I\).

Example 1: Setup

Find the QR factorization of:

$$ A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} $$

Example 1: Gram-Schmidt

1
Normalize \(\mathbf{a}_1\): \(\|\mathbf{a}_1\| = \sqrt{1^2+1^2+0^2} = \sqrt{2}\), so \(\mathbf{e}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}\).
2
Project \(\mathbf{a}_2\) onto \(\mathbf{e}_1\): \(\mathbf{e}_1 \cdot \mathbf{a}_2 = \frac{1}{\sqrt{2}}(1\cdot1 + 1\cdot0 + 0\cdot1) = \frac{1}{\sqrt{2}}\).
3
Subtract projection: \(\mathbf{u}_2 = \mathbf{a}_2 - \frac{1}{\sqrt{2}}\mathbf{e}_1 = \begin{bmatrix}1\\0\\1\end{bmatrix} - \begin{bmatrix}1/2\\1/2\\0\end{bmatrix} = \begin{bmatrix}1/2\\-1/2\\1\end{bmatrix}\).
4
Normalize: \(\|\mathbf{u}_2\| = \sqrt{1/4+1/4+1} = \frac{\sqrt{6}}{2}\), so \(\mathbf{e}_2 = \frac{1}{\sqrt{6}}\begin{bmatrix}1\\-1\\2\end{bmatrix}\).

Example 1: Result

$$ Q = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \\[6pt] \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{6}} \\[6pt] 0 & \frac{2}{\sqrt{6}} \end{bmatrix}, \qquad R = \begin{bmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} \\[6pt] 0 & \frac{\sqrt{6}}{2} \end{bmatrix} $$

Example 2: \(3 \times 3\) Matrix

Find the QR factorization of:

$$ A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} $$

1
\(\mathbf{e}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}\), since \(\|\mathbf{a}_1\| = \sqrt{2}\).
2
\(\mathbf{u}_2 = \mathbf{a}_2 - (\mathbf{e}_1 \cdot \mathbf{a}_2)\mathbf{e}_1 = \begin{bmatrix}1/2\\-1/2\\1\end{bmatrix}\), then \(\mathbf{e}_2 = \frac{1}{\sqrt{6}}\begin{bmatrix}1\\-1\\2\end{bmatrix}\).
3
\(\mathbf{u}_3 = \mathbf{a}_3 - (\mathbf{e}_1 \cdot \mathbf{a}_3)\mathbf{e}_1 - (\mathbf{e}_2 \cdot \mathbf{a}_3)\mathbf{e}_2 = \frac{1}{3}\begin{bmatrix}-2\\2\\1\end{bmatrix}\), then \(\mathbf{e}_3 = \frac{1}{3}\begin{bmatrix}-2\\2\\1\end{bmatrix}\).

Example 2: Final Matrices

$$ Q = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & \frac{-2}{3} \\[6pt] \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{6}} & \frac{2}{3} \\[6pt] 0 & \frac{2}{\sqrt{6}} & \frac{1}{3} \end{bmatrix} $$

$$ R = \begin{bmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[6pt] 0 & \frac{\sqrt{6}}{2} & \frac{1}{\sqrt{6}} \\[6pt] 0 & 0 & \frac{2}{3} \end{bmatrix} $$

Common Mistakes

✕ Forgetting to Normalize
After subtracting projections, you must divide by the norm. Skipping this means \(Q\) won't be orthogonal.
✕ Projecting onto \(\mathbf{a}_j\) not \(\mathbf{e}_j\)
Always project onto the normalized vectors \(\mathbf{e}_j\), not the raw columns \(\mathbf{a}_j\).
✕ Wrong \(R\) Entries
\(R_{jk} = \mathbf{e}_j \cdot \mathbf{a}_k\), not \(\mathbf{e}_j \cdot \mathbf{u}_k\). Use the original column \(\mathbf{a}_k\) for the dot product.

Question 1 of 5

In the factorization \(A = QR\), what property must Q satisfy?

Question 2 of 5

During Gram-Schmidt, to orthogonalize \(\mathbf{a}_2\), we compute \(\mathbf{u}_2 = \mathbf{a}_2 - \text{proj}_{\mathbf{e}_1}(\mathbf{a}_2)\). What does subtracting the projection achieve?

Question 3 of 5

If \(A\) is a \(4 \times 3\) matrix with linearly independent columns, what are the dimensions of \(Q\) and \(R\)?

Question 4 of 5

Given \(\mathbf{a}_1 = \begin{bmatrix}3\\4\end{bmatrix}\), what is the first orthonormal vector \(\mathbf{e}_1\) in Gram-Schmidt?

Question 5 of 5

Which entry of \(R\) stores the value \(\mathbf{e}_1 \cdot \mathbf{a}_2\)?