QR Decomposition

QR decomposition is a matrix factorization that expresses a matrix as $A=QR$, where $Q$ has orthonormal columns and $R$ is upper triangular or upper trapezoidal, depending on the dimensions. For real matrices, a square $Q$ is an orthogonal matrix; for complex matrices, it is a unitary matrix. A central tool in numerical linear algebra, QR decomposition converts problems involving general matrices into problems involving triangular matrices while preserving Euclidean lengths. (netlib.org)

Definition and forms

For $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, the full QR decomposition has the form

where $Q$ is $m\times m$ and $R_1$ is $n\times n$ and upper triangular. Here $Q^T$ denotes the transpose, and $I_m$ is the identity matrix. Partitioning $Q=[Q_1\ Q_2]$ gives the reduced, thin, or economy-size decomposition

with $Q_1$ of size $m\times n$. The reduced form omits columns unnecessary for reconstructing $A$. (netlib.org)

For matrices over the complex numbers, transpose is replaced by conjugate transpose, written $Q^*$. QR also exists for wide matrices, where the full factor $R$ is upper trapezoidal: its entries below the main diagonal are zero, but it has more columns than rows. (netlib.org)

Every real matrix with $m\ge n$ admits QR decomposition, including rank-deficient matrices. If its columns are linearly independent, the reduced decomposition becomes unique when all diagonal entries of $R_1$ are required to be positive. Without this convention, corresponding columns of $Q_1$ and rows of $R_1$ can change signs together. When $m>n$, the remaining columns of full $Q$ are not uniquely determined. (buttenschoen.ca)

Geometric interpretation

For a full-column-rank matrix, the columns of $Q_1$ form an orthonormal basis for the span of the columns of $A$. Writing $a_j$ and $q_i$ for individual columns,

Thus $R_1$ records the coordinates of the original columns in this orthonormal basis. Its triangular structure reflects the fact that the first $j$ original columns can be represented using the first $j$ basis vectors. The coefficients satisfy $r_{ij}=q_i^*a_j$, an inner product. (buttenschoen.ca)

As a consequence, $Q_1Q_1^*$ represents orthogonal projection onto the column space of $A$. QR therefore separates the geometry of that space, represented by $Q_1$, from the coordinate relationships represented by $R_1$. (buttenschoen.ca)

Computational methods

The Gram–Schmidt process constructs QR by subtracting projections onto previously obtained orthonormal vectors and normalizing the remainder. Classical Gram–Schmidt can lose substantial orthogonality in floating-point arithmetic. Modified Gram–Schmidt reorganizes the projections and generally behaves better, although reorthogonalization may still be necessary for demanding problems. (cs.cornell.edu)

Householder transformations eliminate entries below the diagonal one column at a time. In real arithmetic, a reflector can be written

A sequence of these orthogonal reflectors transforms $A$ into triangular form; their product determines $Q$. Householder QR is a standard dense-matrix method because of its numerical stability. (buttenschoen.ca)

Givens rotations act on two coordinates at a time to eliminate selected entries. They are useful when individual zeroing operations match the matrix structure or when an existing factorization needs updating. (cs.cornell.edu)

For dense real $m\times n$ matrices with $m\ge n$, Householder factorization without explicitly forming $Q$ requires approximately $2mn^2-\frac23n^3$ floating-point operations. Its computational complexity is therefore $O(mn^2)$. Implementations commonly store $Q$ implicitly as reflector vectors; blocked algorithms apply groups of reflectors using matrix–matrix operations. (cs.utexas.edu)

Least-squares problems

QR solves the overdetermined problem underlying ordinary least squares and linear regression:

For full column rank, orthogonal invariance of the Euclidean norm gives

The second term is independent of $x$. Consequently, the unique minimizer solves the triangular system

which is evaluated by back substitution. The residual norm is $\|Q_2^*b\|_2$, so it can be obtained without explicitly constructing the residual vector. (netlib.org)

Unlike solving the normal equations $A^*Ax=A^*b$, direct QR does not form $A^*A$. For full column rank, its spectral condition number satisfies $\kappa_2(A^*A)=\kappa_2(A)^2$. Avoiding this squaring helps prevent additional numerical difficulties, although QR cannot remove the original problem’s sensitivity to perturbations. (cs.cornell.edu)

Pivoting and numerical rank

Column-pivoted QR introduces a permutation matrix $P$:

Columns are reordered to expose stronger independent directions earlier. When the rank is uncertain, partitioning $R$ into a leading well-conditioned block and a small trailing block helps estimate numerical rank. This estimate depends on tolerances and scaling; ordinary column pivoting is not a universal substitute for singular value decomposition. In rank-deficient least squares, a basic solution obtained from pivoted QR need not be the minimum-norm solution. (netlib.org)

Connection with eigenvalue algorithms

The QR algorithm repeatedly uses QR decomposition to compute eigenvalues and eigenvectors. Its basic unshifted step is

Because $A_{k+1}=Q_k^*A_kQ_k$, successive matrices are related by similarity transformations and have the same eigenvalues. Practical implementations introduce shifts and exploit structured matrix forms to accelerate convergence toward a Schur decomposition. The factorization $A=QR$ is thus a building block of the iterative QR algorithm, rather than the same operation. (cs.cornell.edu)