Matrix Decomposition Calculator

Matrix Decomposition: Factoring Matrices for Computation

Matrix decomposition (also called matrix factorization) is the process of breaking a matrix into a product of simpler matrices that reveal its structure and make computations more efficient. Just as integer factorization (60 = 2 × 2 × 3 × 5) reveals the prime building blocks of a number, matrix decomposition reveals the fundamental components of a linear transformation. The three most important decompositions in applied linear algebra are LU, QR, and SVD, each optimized for different classes of problems.

LU Decomposition with Partial Pivoting

LU decomposition factors a square matrix A into a lower triangular matrix L (with ones on the diagonal) and an upper triangular matrix U, such that PA = LU where P is a permutation matrix that records row swaps during elimination. The decomposition is essentially a formalized version of Gaussian elimination: U is the row echelon form of A, and L stores the multipliers used during elimination.

The computational advantage of LU decomposition becomes clear when solving multiple systems with the same coefficient matrix. Given Ax = b, you first decompose A = LU (which costs O(n³/3) operations), then for each new right-hand side b, you solve Ly = Pb by forward substitution and Ux = y by back substitution (each costing only O(n²)). Without LU, each new right-hand side would require a full O(n³) elimination. This makes LU decomposition the standard method in numerical libraries for solving linear systems, computing determinants (det(A) = product of diagonal entries of U, with a sign flip for each row swap), and computing matrix inverses.

Partial pivoting selects the row with the largest absolute value in the current column as the pivot row, swapping it into position before elimination. This prevents division by zero and minimizes the growth of rounding errors. Without pivoting, even a well-conditioned matrix can produce catastrophically inaccurate results due to floating-point arithmetic. The permutation matrix P records these row swaps so that the factorization PA = LU remains exact.

QR Decomposition via Gram-Schmidt Orthogonalization

QR decomposition factors a matrix A (which can be rectangular) into an orthogonal matrix Q (whose columns are orthonormal: Q^TQ = I) and an upper triangular matrix R, such that A = QR. The classical Gram-Schmidt process constructs Q column by column: take each column of A, subtract its projection onto all previously computed orthonormal vectors, and normalize the result. The entries of R are the projection coefficients and the norms of the intermediate vectors.

QR decomposition is the computational engine behind the QR algorithm, the standard method for computing all eigenvalues of a matrix. The QR algorithm repeatedly computes A_k = Q_kR_k and forms A_k+1 = R_kQ_k, which converges to an upper triangular matrix whose diagonal entries are the eigenvalues. QR decomposition is also the preferred method for solving least-squares problems (minimizing ||Ax - b||) because it is numerically more stable than the normal equations approach (A^TAx = A^Tb), which squares the condition number.

The modified Gram-Schmidt process, which this calculator uses, reorthogonalizes against each new column immediately rather than against the original columns. This produces the same result in exact arithmetic but is significantly more stable in floating-point computation, reducing the loss of orthogonality that plagues classical Gram-Schmidt on ill-conditioned matrices.

Singular Value Decomposition (SVD)

SVD decomposes any m×n matrix A into the product A = UΣV^T, where U is an m×m orthogonal matrix (left singular vectors), Σ is an m×n diagonal matrix of non-negative singular values σ₁ ≥ σ₂ ≥ ... ≥ 0, and V is an n×n orthogonal matrix (right singular vectors). SVD exists for every matrix, regardless of shape or rank, making it the most general and powerful decomposition in linear algebra.

The singular values reveal critical information about the matrix. The rank equals the number of non-zero singular values. The condition number σ_max/σ_min measures how sensitive the solution of Ax = b is to perturbations in A or b. The Eckart-Young theorem proves that the best rank-k approximation to A (in both the Frobenius and spectral norms) is obtained by keeping only the k largest singular values and setting the rest to zero. This truncated SVD is the mathematical foundation of image compression (keeping the top singular values captures the image structure while discarding noise), latent semantic analysis (reducing a term-document matrix to its most significant dimensions), and recommender systems (Netflix Prize, where truncated SVD predicts user-movie ratings).

The singular values of A are related to the eigenvalues of A^TA: σ_i = sqrt(λ_i(A^TA)). The right singular vectors (columns of V) are the eigenvectors of A^TA, and the left singular vectors (columns of U) are the eigenvectors of AA^T. This calculator computes SVD through this eigenvalue relationship for small matrices, displaying each intermediate step.

Choosing the Right Decomposition

Use LU decomposition when you need to solve square linear systems Ax = b, especially when solving multiple systems with the same A but different b vectors. LU is also the fastest way to compute determinants and inverses. Use QR decomposition for least-squares problems, eigenvalue computation via the QR algorithm, and when numerical stability is paramount (QR preserves orthogonality better than LU for ill-conditioned matrices). Use SVD when you need to analyze the rank, condition number, or low-rank structure of a matrix, for pseudoinverse computation (Moore-Penrose inverse), or for dimensionality reduction in data analysis.

In terms of computational cost, all three decompositions are O(n³) for an n×n matrix. LU requires approximately n³/3 floating-point operations, QR requires approximately 2n³/3 (twice as expensive as LU), and SVD requires approximately 4n³/3 (four times as expensive as LU for the full decomposition). For this reason, production code uses the cheapest decomposition that solves the problem: LU for general systems, QR for least-squares, and SVD only when its specific properties are needed.

Related Tools

• Eigenvector Step Solver — step-by-step eigenvalue and eigenvector computation with visualization
• Eigenvalue Calculator — eigenvalues via characteristic polynomial for matrices up to 5×5
• Inverse Matrix Calculator — matrix inverse via the adjugate method
• Linear Algebra Cheatsheet — searchable formula reference with mini-calculators

Built by Michael Lip. Try the ML3X Matrix Calculator for interactive step-by-step solutions.