QR Decomposition

Existence of QR Decomposition

The $\mathrm{QR}$ decomposition factors a matrix into an orthogonal factor and an upper-triangular factor. $Orthogonal multiplication preserves lengths and angles$ , so it is well suited to stable numerical calculations.

Let $A \in \mathbb{R}^{m \times n}$ satisfy $m \geq n$ and $\operatorname{rank}(A)=n$ . Then there is an orthogonal matrix $Q \in \mathbb{R}^{m \times m}$ with $Q^TQ=I$ and an upper-triangular matrix $R \in \mathbb{R}^{m \times n}$ whose first $n$ diagonal entries are positive, such that

A = Q \cdot R

This factorization is the $\mathrm{QR}$ decomposition of $A$ .

Proof with Gram Schmidt Orthogonalization

Let $a_j$ denote column $j$ of $A$ . Gram-Schmidt $removes the components$ in the directions already found, then normalizes what remains:

\tilde{q}_j := a_j - \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k

Full column rank guarantees $\widetilde q_j\neq0$ at every step. The normalized vectors form the columns of $Q_1 \in \mathbb{R}^{m \times n}$ and satisfy $Q_1^TQ_1=I_n$ . Each original column can be reconstructed as

a_j = \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \tilde{q}_j

$A=Q_1R_1$ , where $R_1 \in \mathbb{R}^{n \times n}$ is upper triangular and $r_{ii}=\|\widetilde q_i\|_2>0$ .

Complete $Q_1$ with $m-n$ orthonormal columns to form $Q=(Q_1\quad Q_2)\in\mathbb{R}^{m\times m}$ .

Appending $m-n$ zero rows to $R_1$ gives:

R=\begin{pmatrix}R_1\\0\end{pmatrix}\in\mathbb{R}^{m\times n}

The completed matrices still satisfy $A=Q_1R_1=QR$ .

Full and Reduced QR Decomposition

For $A\in\mathbb{R}^{m\times n}$ with $m\geq n$ , the full and reduced forms describe the same factorization with $different matrix sizes$ . Both forms multiply back to $A$ , so the choice depends on whether you need the complete orthonormal basis or only the columns that carry the data.

Full QR Decomposition

The full form $keeps all$ $m$ columns of $Q$ :

A = Q \cdot R

Here $Q\in\mathbb{R}^{m\times m}$ is orthogonal and $R\in\mathbb{R}^{m\times n}$ contains an upper-triangular $n\times n$ block above $m-n$ zero rows.

Reduced QR Decomposition

The reduced form $removes those zero rows$ and the matching unused columns of $Q$ :

\begin{aligned} A &= Q \cdot R \\ &= (Q_1 \quad Q_2) \cdot \begin{pmatrix} R_1 \\ 0 \end{pmatrix} \\ &= Q_1 \cdot R_1 \end{aligned}

Here $Q_1\in\mathbb{R}^{m\times n}$ contains the first $n$ columns of $Q$ , and $R_1\in\mathbb{R}^{n\times n}$ is upper triangular. Storing only the first $n$ columns of $Q$ saves memory and avoids operations on blocks that are known to be zero.

The unused columns $Q_2\in\mathbb{R}^{m\times(m-n)}$ form an orthonormal basis for the null space of $A^T$ :

A^T Q_2 = R_1^T Q_1^T Q_2 = 0

The null space of $A^T$ is the set of vectors $x$ that satisfy $A^Tx=0$ .

Uniqueness Property

For a full-column-rank matrix, the reduced factorization $A=Q_1R_1$ is unique when every $diagonal entry$ of $R_1$ is positive. That sign condition removes the remaining freedom, because multiplying a column of $Q_1$ and the matching row of $R_1$ by $-1$ leaves the product unchanged.

Worked Thin QR Example

Let

A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}=(a_1\ \,a_2)

$Gram-Schmidt first$ gives

q_1=\frac{a_1}{\|a_1\|_2}=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}

The calculation gives:

Q_1=\begin{pmatrix}1/\sqrt2&1/\sqrt6\\1/\sqrt2&-1/\sqrt6\\0&2/\sqrt6\end{pmatrix}

Householder Method for QR Decomposition

Classical Gram-Schmidt gives a direct derivation, but $nearly dependent columns$ can lose orthogonality in floating-point arithmetic. Modified Gram-Schmidt reduces that error. Dense numerical software commonly uses Householder reflectors, while Givens rotations are useful when only selected entries need to be eliminated.

Householder Transformation

For a unit vector $v\in\mathbb{R}^m$ , define the Householder matrix

S = I - 2vv^T \in \mathbb{R}^{m \times m}

The $outer product$ $vv^T$ multiplies an $m\times1$ column by a $1\times m$ row, so it produces an $m\times m$ rank-one matrix. The reversed product $v^Tv$ is the scalar $1$ .

Properties of Householder Transformation

For $S=I-2vv^T$ and $\|v\|_2=1$ , the following properties hold. Symmetry and orthogonality come from the unit vector in the definition, the reflection explains what the transformation does to a vector, and $condition number one$ means that an exact reflection preserves the Euclidean norm of a perturbation vector.

$S$ is symmetric: $S^T = S$
$S$ is an orthogonal matrix: $S^T S = I$
$Sx$ reflects $x\in\mathbb{R}^m$ across the hyperplane perpendicular to $v$
$\text{cond}_2(S) = 1$

Householder Procedure

Let $A\in\mathbb{R}^{m\times n}$ satisfy $m\geq n$ and $\operatorname{rank}(A)=n$ . $Each Householder step$ zeros the entries below one diagonal position while leaving the zeros created by earlier steps unchanged.

Start with $A_1=A$ . Reflect its first column onto a multiple of the first coordinate vector:

\tilde{a}_1 \text{ first column of } A_1

u_1 = \tilde{a}_1 \mp \|\tilde{a}_1\|_2 \cdot e_1

Iterative Transformation Process

With $S_1=I_m-2v_1v_1^T$ , the first column below the diagonal becomes zero:

A_2 = S_1 \cdot A_1 = \begin{pmatrix} r_{11} & * \\ 0 & \tilde{A}_2 \end{pmatrix}

In the matrix $A_2$ , $r_{11} = \pm\|\tilde{a}_1\|_2$ and $\tilde{A}_2 \in \mathbb{R}^{m-1 \times n-1}$ .

Apply the next reflector only to the $remaining lower-right submatrix$ :

\tilde{a}_2 \text{ first column of } \tilde{A}_2

u_2 = \tilde{a}_2 \mp \|\tilde{a}_2\|_2 \cdot \tilde{e}_1

Embed the second reflector in the lower-right block of the identity matrix:

\tilde{S}_2 = I_{m-1} - 2v_2v_2^T \in \mathbb{R}^{m-1 \times m-1}

The second column below the diagonal then becomes zero:

A_3 = S_2 \cdot A_2 = \begin{pmatrix} r_{11} & * & * \\ 0 & r_{22} & * \\ 0 & 0 & \tilde{A}_3 \end{pmatrix}

Here $r_{22}=\pm\|\widetilde a_2\|_2$ and $\widetilde A_3\in\mathbb{R}^{(m-2)\times(n-2)}$ . Repeating the same operation leaves the final active column

\tilde{A}_n = \begin{pmatrix} \tilde{a}_{nn} \\ \vdots \\ \tilde{a}_{mn} \end{pmatrix} \in \mathbb{R}^{m-(n-1) \times 1}

After the last reflection, the transformed matrix is upper triangular:

\begin{aligned} A_{n+1} &= R \\ &= \begin{pmatrix} r_{11} & & * \\ & \ddots & \\ 0 & & r_{nn} \\ 0 & \cdots & 0 \\ \vdots & & \vdots \\ 0 & \cdots & 0 \end{pmatrix} \\ &= S_n \cdot \ldots \cdot S_1 \cdot A \\ &= Q^T \cdot A \end{aligned}

Because each reflector is orthogonal and symmetric, their product gives

A = Q \cdot R

The matrix $Q$ is orthogonal because it is a product of orthogonal reflectors.

Householder Algorithm

Initialize the active matrix and accumulated orthogonal factor:

A_1 := A

At step $i$ , take the active part of column $i$ :

\begin{aligned} \tilde{a}_i &= \begin{pmatrix} a_{ii} \\ \vdots \\ a_{mi} \end{pmatrix} \\ &:= \begin{pmatrix} (A_i)_{ii} \\ \vdots \\ (A_i)_{mi} \end{pmatrix} \in \mathbb{R}^{m-i+1} \end{aligned}

Compute its norm, choose a sign that $avoids cancellation$ , and form the Householder vector:

\sigma := \|\tilde{a}_i\|_2

The corresponding scale factor is

\beta := \frac{2}{u_i^Tu_i}=\frac{1}{\sigma(\sigma+|\tilde a_{ii}|)}

The normalized vector and the full reflector are

v_i=\frac{u_i}{\|u_i\|_2}

Update the active matrix and the accumulated factor without forming an extra dense product:

\begin{aligned} A_{i+1} &:= S_i A_i \\ &= (I_m - \beta \hat{u}_i \hat{u}_i^T) A_i \\ &= A_i - \hat{u}_i (\beta \hat{u}_i^T A_i) \end{aligned}

After $n$ steps,

R := A_{n+1}

Numerical Aspects and Householder Complexity

Implementing the decomposition in floating-point arithmetic raises two practical questions, how many operations it costs and how the $rounding error behaves$ . Both answers decide whether the method fits the problem: the operation count sets the run time for a large matrix, and the rounding behavior decides how much of the computed result you can trust.

Computational Complexity

The count below stores $Q$ $implicitly as reflectors$ and computes $R$ . Explicitly constructing a full $m\times m$ matrix $Q$ costs additional work.

For $m\ge n$ , a $\mathrm{QR}$ decomposition with Householder reflectors requires approximately:

2mn^2-\frac23n^3

The approximate number of $floating-point operations$ when $m=n$ is:

\frac43n^3

Numerical Properties

Orthogonal multiplication $preserves singular values$ , so $\operatorname{cond}_2(R)=\operatorname{cond}_2(A)$ for a full-column-rank matrix.

At step $i$ , the new diagonal entry is $\pm\|\widetilde a_i\|_2$ . Choose the sign below while computing the reflector to avoid subtracting nearly equal numbers:

u_i = \tilde{a}_i + s_i\|\tilde{a}_i\|_2e_1

After the factorization, matching signs in one column of $Q$ and one row of $R$ can be flipped to make the diagonal of $R$ positive. If $\|\widetilde a_i\|_2=0$ , the matrix lacks full column rank and this uniqueness condition no longer applies. A column-pivoted, rank-revealing $\mathrm{QR}$ decomposition is more informative when numerical rank matters.

A compact implementation rescales the Householder vector so its first active entry is 1. Its remaining entries fit below the diagonal of the working matrix, while a separate scalar stores the reflector strength. The diagonal and upper triangle retain $R$ . Apply the stored reflectors without constructing $Q$ explicitly.

The reduced factorization keeps the first $n$ columns of $Q$ and the first $n$ rows of $R$ .