QR Decomposition Calculator

What is QR Decomposition?

QR decomposition (also known as QR factorization) expresses a matrix A as the product of two matrices: an orthogonal (or unitary) matrix Q and an upper triangular matrix R. Every real m×n matrix with linearly independent columns admits such a factorization.

Here Q is an m×m orthogonal matrix (Q^TQ = I), meaning its columns form an orthonormal basis, and R is an m×n upper triangular matrix whose diagonal entries are non-negative when the decomposition is made unique (the so-called reduced or thin QR).

QR decomposition is one of the most numerically stable factorization methods and sits at the heart of many algorithms in scientific computing, statistics, and machine learning.

Properties of Orthogonal Matrices

The matrix Q produced by QR decomposition has several powerful properties that make it invaluable in numerical computations:

• Orthonormality — The columns of Q are mutually orthogonal unit vectors: Q^TQ = QQ^T = I.
• Norm preservation — Multiplying by Q does not change the Euclidean length of any vector: ‖Qx‖ = ‖x‖. This means Q introduces no rounding-error amplification.
• Determinant — det(Q) = ±1. If we enforce positive diagonal entries in R, we get det(Q) = +1 (a proper rotation).
• Condition number — The condition number of Q is exactly 1, making orthogonal transformations the gold standard for numerical stability.
• Easy inversion — Because Q^-1 = Q^T, inverting Q costs nothing more than a transpose.

The Gram-Schmidt Process

The classical Gram-Schmidt algorithm is the most intuitive way to compute the QR decomposition. It works by orthogonalizing the columns of A one at a time:

1. Start with the first column — Set u₁ = a₁, then normalize: e₁ = u₁ / ‖u₁‖.
2. Subtract projections — For each subsequent column a_k, remove the components along all previously computed orthonormal vectors: u_k = a_k − ∑_j=1^k-1 (e_j^T a_k) e_j.
3. Normalize — Compute e_k = u_k / ‖u_k‖.
4. Build Q and R — The orthonormal vectors e₁, e₂, … form the columns of Q. The entries of R are the projection coefficients: r_jk = e_j^T a_k for j ≤ k, and r_jk = 0 for j > k.

The modified Gram-Schmidt variant improves numerical stability by re-orthogonalizing against the already-updated vectors rather than the original columns. In exact arithmetic both produce the same result, but modified Gram-Schmidt is preferred in floating-point computation.

Householder Reflections

For large or ill-conditioned matrices, the Householder method is the standard production algorithm. Instead of building Q column by column, it applies a sequence of orthogonal reflections that zero out sub-diagonal entries:

• Each Householder reflector has the form H = I − 2vv^T, where v is a unit vector chosen so that H maps a column below the diagonal to a multiple of e₁.
• After n reflections (for an m×n matrix with m ≥ n), the product H_n … H₂ H₁ A = R is upper triangular, and Q = H₁ H₂ … H_n.
• Householder QR is backward stable and is the algorithm implemented in LAPACK (dgeqrf), NumPy (numpy.linalg.qr), and MATLAB (qr).

Givens Rotations

A third approach uses Givens rotations — 2×2 orthogonal rotations embedded in the larger matrix — to selectively zero out individual entries below the diagonal. Givens rotations are particularly useful for:

• Sparse matrices — Each rotation modifies only two rows, preserving sparsity.
• Parallel and hardware implementations — Givens rotations are easily pipelined on FPGAs and systolic arrays.
• Updating a QR factorization — When a single row or column is added or removed, Givens rotations can update the existing factorization efficiently.

Computational Complexity

The cost of computing a QR decomposition of an m×n matrix (m ≥ n) depends on the algorithm:

• Gram-Schmidt (classical or modified) — Approximately 2mn² floating-point operations (flops).
• Householder reflections — Approximately 2mn² − (2/3)n³ flops, with excellent cache behavior.
• Givens rotations — Approximately 3mn² − n³ flops, higher constant but advantageous in special cases.

For a square n×n matrix, all methods scale as O(n³). The Householder method is generally fastest in practice due to BLAS-3 (blocked) implementations in libraries like LAPACK.

Applications of QR Decomposition

QR decomposition is one of the most widely used matrix factorizations in applied mathematics and engineering:

• Least squares problems — Solving the overdetermined system Ax ≈ b. Substituting A = QR gives Rx = Q^Tb, a triangular system that is trivial to solve by back-substitution. This is more numerically stable than forming the normal equations A^TAx = A^Tb.
• Eigenvalue algorithms — The QR algorithm (not the same as QR decomposition, but built upon it) is the standard method for computing all eigenvalues of a dense matrix. Each iteration performs a QR decomposition and reforms the matrix as RQ, converging to the Schur form.
• Linear regression — Statistical software (R, MATLAB, Python's scikit-learn) uses QR decomposition internally to compute regression coefficients, ensuring numerical stability even with multicollinear predictors.
• Signal processing — Adaptive beamforming and recursive least squares algorithms rely on QR updating to track time-varying signals in real time.
• Control theory — Computing observability and controllability matrices, and performing model reduction via balanced truncation.
• Computer graphics — Extracting the rotation component from an arbitrary affine transformation matrix (polar decomposition begins with QR).
• Solving linear systems — While LU is more efficient for square systems, QR provides a stable alternative when the coefficient matrix is ill-conditioned.

QR vs. Other Decompositions

Choosing the right decomposition depends on the problem structure:

• QR vs. LU — LU is faster for solving square linear systems (2/3 n³ vs. 4/3 n³ flops) but can be unstable without pivoting. QR is unconditionally stable and handles rectangular matrices naturally.
• QR vs. SVD — SVD provides more information (singular values, rank, null space) but costs roughly 4× more than QR. If you only need a least squares solution or an orthogonal basis, QR is the pragmatic choice.
• QR vs. Cholesky — For least squares, forming A^TA and using Cholesky is fast but squares the condition number. QR avoids this and is preferred when accuracy matters.
• QR vs. Eigendecomposition — Eigendecomposition reveals the spectral structure of square matrices, while QR works on any matrix shape. Ironically, the most popular eigenvalue algorithm is itself based on repeated QR decompositions.

Existence and Uniqueness

Every real m×n matrix A with m ≥ n has a QR decomposition A = QR. If A has full column rank (rank n), then the thin QR decomposition (where Q is m×n with orthonormal columns and R is n×n upper triangular) is unique provided we require the diagonal entries of R to be positive.

When A is rank-deficient, the decomposition still exists but is not unique — some diagonal entries of R will be zero, and the corresponding columns of Q can be chosen arbitrarily from the orthogonal complement.

QR with Column Pivoting

Column-pivoted QR decomposition computes AP = QR, where P is a permutation matrix that reorders the columns of A so that the diagonal entries of R are non-increasing in absolute value: |r₁₁| ≥ |r₂₂| ≥ … This provides a rank-revealing factorization and can be used as a cheaper alternative to SVD for estimating numerical rank.