The QR Decomposition of a Matrix

The QR decomposition factors a matrix with linearly independent columns as the product of a matrix with orthonormal columns and an upper triangular matrix. The standard tool for building this factorization is the Gram-Schmidt process.

Matrices with Orthonormal Columns

A set of vectors is called orthonormal if each vector has length (or norm) \( 1 \) and each vector is orthogonal to every other vector in the set.

A matrix \( Q \) whose columns form an orthonormal set satisfies:

\[ Q^T Q = I_n \]

where \( Q^T \) is the transpose of \( Q \) and \( I_n \) is the \( n \times n \) identity matrix.

Note: If additionally \( Q \) is square (\( m = n \)), then \( Q \) is orthogonal and \( Q^{-1} = Q^T \). But in QR decomposition, \( Q \) is usually tall and skinny (\( m > n \)), so \( Q^T Q = I_n \) holds while \( Q Q^T \) does not equal \( I_m \).

The QR Decomposition

An \( m \times n \) matrix \( A \) whose columns are linearly independent can be factored as

\[ A = Q R \]

where

Uniqueness: If \( A \) has full column rank and we require the diagonal of \( R \) to be positive, the QR decomposition is unique.

The Gram-Schmidt Process

Steps

  1. Step 1 — Columns of \(A\). Write \( A \) as column vectors: \[ A = [\mathbf{v}_1 \; \mathbf{v}_2 \; \cdots \; \mathbf{v}_n]. \]
  2. Step 2 — Gram-Schmidt. Use the Gram-Schmidt process to produce an orthonormal set \( \mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_n \) from \( \mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n \).
  3. Step 3 — Build \(Q\) and \(R\). Form \( Q \) with the \( \mathbf{q}_i \) as columns, and compute \[ R = Q^{T} A. \]

Why \( R = Q^T A \)? Multiply both sides of \( A = QR \) on the left by \( Q^T \): \( Q^T A = Q^T Q R \). Since \( Q^T Q = I_n \), this simplifies to \( Q^T A = R \).

Why \(R\) is upper triangular. By construction, each \( \mathbf{q}_k \) is orthogonal to \( \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_{k-1}\} \), so \( \mathbf{q}_j \cdot \mathbf{v}_k = 0 \) for \( j > k \). Hence all entries of \(R\) below the diagonal vanish.

Examples with Solutions

Example 1 — QR Decomposition of a \(3 \times 3\) Matrix

Find the QR decomposition of

\[ A = \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 0 & -1 & 1 \end{bmatrix}. \]

View Solution to Example 1

Step 1 — Columns of \(A\).

\[ \mathbf{v}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}. \]

Step 2 — Gram-Schmidt.

First vector (already unit):

\[ \mathbf{q}_1 = \frac{\mathbf{v}_1}{\|\mathbf{v}_1\|} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}. \]

Second vector: \( \mathbf{v}_2 \cdot \mathbf{q}_1 = 0 \), so no projection is needed.

\[ \mathbf{u}_2 = \mathbf{v}_2 = \begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix}, \quad \|\mathbf{u}_2\| = \sqrt{5}, \quad \mathbf{q}_2 = \frac{1}{\sqrt{5}}\begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix}. \]

Third vector: project \( \mathbf{v}_3 \) onto \( \mathbf{q}_1 \) and \( \mathbf{q}_2 \).

\[ \mathbf{v}_3 \cdot \mathbf{q}_1 = 2, \quad \mathbf{v}_3 \cdot \mathbf{q}_2 = \frac{1}{\sqrt{5}}[(2)(0) + (0)(2) + (1)(-1)] = -\frac{1}{\sqrt{5}}. \]

\[ \mathbf{u}_3 = \mathbf{v}_3 - 2\mathbf{q}_1 + \frac{1}{\sqrt{5}}\mathbf{q}_2 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} + \frac{1}{5}\begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 2/5 \\ 4/5 \end{bmatrix}. \]

\[ \|\mathbf{u}_3\| = \frac{\sqrt{20}}{5} = \frac{2}{\sqrt{5}}, \quad \mathbf{q}_3 = \frac{1}{\|\mathbf{u}_3\|}\mathbf{u}_3 = \frac{\sqrt{5}}{2}\begin{bmatrix} 0 \\ 2/5 \\ 4/5 \end{bmatrix} = \begin{bmatrix} 0 \\ 1/\sqrt{5} \\ 2/\sqrt{5} \end{bmatrix}. \]

Step 3 — Build \(Q\) and \(R\).

\[ Q = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \tfrac{2}{\sqrt{5}} & \tfrac{1}{\sqrt{5}} \\ 0 & -\tfrac{1}{\sqrt{5}} & \tfrac{2}{\sqrt{5}} \end{bmatrix}. \]

Then \( R = Q^T A \):

\[ R = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \tfrac{2}{\sqrt{5}} & -\tfrac{1}{\sqrt{5}} \\ 0 & \tfrac{1}{\sqrt{5}} & \tfrac{2}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} 1 & 0 & 2 \\ 0 & 2 & 0 \\ 0 & -1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 2 \\ 0 & \sqrt{5} & -\tfrac{1}{\sqrt{5}} \\ 0 & 0 & \tfrac{2}{\sqrt{5}} \end{bmatrix}. \]

Final factorization:

\[ A = QR = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \tfrac{2}{\sqrt{5}} & \tfrac{1}{\sqrt{5}} \\ 0 & -\tfrac{1}{\sqrt{5}} & \tfrac{2}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} 1 & 0 & 2 \\ 0 & \sqrt{5} & -\tfrac{1}{\sqrt{5}} \\ 0 & 0 & \tfrac{2}{\sqrt{5}} \end{bmatrix}. \]

Example 2 — QR Decomposition of a \(4 \times 3\) Matrix

Find the QR decomposition of

\[ A = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 2 \\ -1 & 0 & 1 \\ 0 & -1 & 1 \end{bmatrix}. \]

View Solution to Example 2

Step 1 — Columns of \(A\).

\[ \mathbf{v}_1 = \begin{bmatrix} 0 \\ 0 \\ -1 \\ 0 \end{bmatrix}, \quad \mathbf{v}_2 = \begin{bmatrix} 1 \\ 1 \\ 0 \\ -1 \end{bmatrix}, \quad \mathbf{v}_3 = \begin{bmatrix} 0 \\ 2 \\ 1 \\ 1 \end{bmatrix}. \]

Step 2 — Gram-Schmidt.

First vector (already unit):

\[ \mathbf{q}_1 = \begin{bmatrix} 0 \\ 0 \\ -1 \\ 0 \end{bmatrix}. \]

Second vector: \( \mathbf{v}_2 \cdot \mathbf{q}_1 = 0 \), so no projection is needed.

\[ \mathbf{q}_2 = \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 0 \\ -1 \end{bmatrix}. \]

Third vector: \( \mathbf{v}_3 \cdot \mathbf{q}_1 = -1 \) and \( \mathbf{v}_3 \cdot \mathbf{q}_2 = \tfrac{1}{\sqrt{3}} \). So:

\[ \mathbf{u}_3 = \mathbf{v}_3 - (-1)\mathbf{q}_1 - \tfrac{1}{\sqrt{3}}\mathbf{q}_2 = \begin{bmatrix} 0 \\ 2 \\ 1 \\ 1 \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ -1 \\ 0 \end{bmatrix} - \frac{1}{3}\begin{bmatrix} 1 \\ 1 \\ 0 \\ -1 \end{bmatrix} = \begin{bmatrix} -1/3 \\ 5/3 \\ 0 \\ 4/3 \end{bmatrix}. \]

\[ \|\mathbf{u}_3\| = \frac{\sqrt{42}}{3}, \quad \mathbf{q}_3 = \frac{3}{\sqrt{42}}\mathbf{u}_3 = \begin{bmatrix} -1/\sqrt{42} \\ 5/\sqrt{42} \\ 0 \\ 4/\sqrt{42} \end{bmatrix}. \]

Step 3 — Build \(Q\) and \(R\).

\[ Q = \begin{bmatrix} 0 & \tfrac{1}{\sqrt{3}} & -\tfrac{1}{\sqrt{42}} \\ 0 & \tfrac{1}{\sqrt{3}} & \tfrac{5}{\sqrt{42}} \\ -1 & 0 & 0 \\ 0 & -\tfrac{1}{\sqrt{3}} & \tfrac{4}{\sqrt{42}} \end{bmatrix}. \]

Then \( R = Q^T A \):

\[ R = \begin{bmatrix} 1 & 0 & -1 \\ 0 & \sqrt{3} & \tfrac{1}{\sqrt{3}} \\ 0 & 0 & \sqrt{\tfrac{14}{3}} \end{bmatrix}. \]

Final factorization:

\[ A = QR = \begin{bmatrix} 0 & \tfrac{1}{\sqrt{3}} & -\tfrac{1}{\sqrt{42}} \\ 0 & \tfrac{1}{\sqrt{3}} & \tfrac{5}{\sqrt{42}} \\ -1 & 0 & 0 \\ 0 & -\tfrac{1}{\sqrt{3}} & \tfrac{4}{\sqrt{42}} \end{bmatrix} \begin{bmatrix} 1 & 0 & -1 \\ 0 & \sqrt{3} & \tfrac{1}{\sqrt{3}} \\ 0 & 0 & \sqrt{\tfrac{14}{3}} \end{bmatrix}. \]

More References and Links