QR Decomposition Calculator
Enter the elements of your matrix A to factor it as A = QR, where Q is an orthonormal matrix and R is upper triangular. The calculator uses the modified Gram-Schmidt process, shows every orthogonalization step, and verifies the result by checking that Q times R reproduces A. Supports 2x2 through 4x4 matrices. Results update as you type.
Formula
Worked example
For A = [[1,0],[0,1],[1,1]] (3x2): column 1 already has norm sqrt(2), so q_1 = [1/sqrt(2), 0, 1/sqrt(2)], r_11 = sqrt(2). Subtract the projection of a_2 onto q_1, then normalize the remainder to get q_2. R = [[sqrt(2), 1/sqrt(2)],[0, 1/sqrt(2)]].
What is QR decomposition?
QR decomposition (also called QR factorization) expresses any matrix A as the product A = QR of two matrices: Q, which has mutually perpendicular unit-length columns (orthonormal), and R, which is upper triangular (all zeros below the main diagonal). For a matrix A with m rows and n columns where m is at least n, Q is m by n and R is n by n. This factorization exists for any full-column-rank matrix and is unique when you require all diagonal entries of R to be positive.
How does the Gram-Schmidt process compute QR?
Modified Gram-Schmidt is the method used here. Starting from the columns a_1, a_2, ..., a_n of A, it builds orthonormal vectors one by one. For each column j, it starts with a copy v_j, then subtracts the component that lies along each previously computed q_k: v_j = v_j - (q_k^T v_j) q_k. The scalar q_k^T v_j becomes R[k][j]. After all subtractions, the norm of v_j becomes R[j][j] and normalizing gives q_j = v_j / R[j][j]. The modified version (updating v_j in place at each subtraction step) is more numerically stable than the classical version that computes all projections from the original a_j.
Applications: least squares and the QR eigenvalue algorithm
QR decomposition is the standard method for solving overdetermined linear systems (more equations than unknowns) in the least-squares sense. Given Ax = b, the least-squares solution is x = R^(-1) Q^T b, which avoids forming the ill-conditioned normal equations A^T A x = A^T b. QR is also the backbone of one of the most important algorithms in numerical linear algebra: the QR algorithm for computing eigenvalues. Starting from a matrix A, it repeats A_1 = QR, A_2 = RQ and continues iterating. Under mild conditions the sequence of A_k converges to an upper triangular (Schur) form whose diagonal entries are the eigenvalues.
Gram-Schmidt vs. Householder vs. Givens rotations
Three main algorithms exist. Modified Gram-Schmidt, used here, builds Q explicitly column by column and is straightforward to understand and implement; it is fine for small matrices but can lose orthogonality for ill-conditioned large ones. Householder reflections apply a sequence of reflective transformations to zero out sub-diagonal entries of each column; this is more numerically stable and is the method used by most production libraries (LAPACK, NumPy). Givens rotations apply plane rotations one entry at a time; they are ideal for sparse matrices and parallel computation because each rotation affects only two rows. All three produce the same Q and R (up to signs) for full-rank matrices.
QR decomposition: key properties and applications
| Property | Description |
|---|---|
| Q is orthonormal | Each column of Q has unit length; all columns are perpendicular (Q^T Q = I) |
| R is upper triangular | All entries below the main diagonal of R are zero |
| Uniqueness | Unique when A has full column rank and all diagonal entries of R are positive |
| Thin (reduced) QR | When m > n, compute only the first n columns of Q (m x n), giving a smaller R (n x n) |
| Least squares | Solve Ax = b in the least-squares sense via x = R^(-1) Q^T b, more stable than normal equations |
| QR algorithm | Iterating A_{k+1} = R_k Q_k converges to the Schur form, revealing eigenvalues |
| Householder alternative | Householder reflections give the same factorization with better numerical stability for large matrices |
| Givens rotations | Useful for sparse matrices and parallel computation; builds QR by successive plane rotations |
Summary of Q and R matrix properties and typical uses of QR factorization in numerical computing.
Frequently asked questions
What does QR decomposition output?
It outputs two matrices: Q, which is orthonormal (its columns are mutually perpendicular and each has length 1), and R, which is upper triangular (all entries below the main diagonal are zero). Their product Q times R exactly reproduces the original matrix A.
When does QR decomposition fail or not exist?
QR decomposition requires the matrix A to have full column rank, meaning no column can be written as a linear combination of the others. If a column is zero or is a scalar multiple of another, the Gram-Schmidt process produces a zero vector during normalization, and the decomposition is undefined for that column. The calculator reports a rank-deficiency error in that case. Also, QR in the standard sense requires m >= n (at least as many rows as columns).
What is thin (reduced) QR vs. full QR?
For an m by n matrix with m > n (more rows than columns), full QR gives a square m by m matrix Q and an m by n upper-trapezoidal R. Thin (or reduced or economy) QR keeps only the first n columns of Q, giving an m by n Q and a square n by n R. For most applications, especially least squares, the thin form is sufficient and more compact. This calculator always computes the thin form.
How do I use QR to solve a least-squares problem?
Set up the overdetermined system Ax = b where A has more rows than columns. Factor A = QR using this calculator. Then compute Q^T b (multiply Q transposed by b), and solve the triangular system Rx = Q^T b by back-substitution. Because R is upper triangular, back-substitution is straightforward: start from the last equation and work upward. This is numerically more stable than the normal equations because it avoids squaring the condition number of A.
Why is the reconstruction error not exactly zero?
Floating-point arithmetic accumulates small rounding errors in each operation. For a well-conditioned matrix, the reconstruction error (max absolute difference between A and Q*R) should be below about 1e-10 or 1e-12, essentially at machine epsilon. Larger errors (say 1e-6 or above) may indicate an ill-conditioned matrix where the columns are nearly linearly dependent, or a matrix with very large entries causing relative rounding errors to dominate.