Matrix Operation Complexity — Time and Space for Every Common Operation
A complete reference of 24 matrix operations covering time complexity, space complexity, numerical stability, and when to use each one. From basic arithmetic to advanced decompositions.
By Michael Lip · Updated April 2026
Methodology
Complexity bounds are sourced from standard numerical linear algebra references (Golub & Van Loan, Trefethen & Bau) and verified against LAPACK documentation. Community relevance was assessed via StackOverflow engagement data from the StackExchange API v2.3 (e.g., "sparse matrix multiplication complexity" with 12.5K views). All complexities assume dense matrices of size n x n unless noted. Stability ratings: High = backward stable, Medium = conditionally stable, Low = known sensitivity to conditioning.
| # | Operation | Category | Time Complexity | Space | Stability | Notes |
|---|---|---|---|---|---|---|
| 1 | Addition / Subtraction | Arithmetic | O(n^2) | O(n^2) | High | Element-wise; trivially stable |
| 2 | Scalar Multiplication | Arithmetic | O(n^2) | O(1) in-place | High | Single pass over elements |
| 3 | Matrix-Vector Multiply | Arithmetic | O(n^2) | O(n) | High | BLAS Level 2 (GEMV) |
| 4 | Matrix-Matrix Multiply | Arithmetic | O(n^3) | O(n^2) | High | BLAS Level 3 (GEMM); Strassen O(n^2.807) |
| 5 | Transpose | Arithmetic | O(n^2) | O(1) in-place | High | Cache-oblivious algorithms for large n |
| 6 | Trace | Arithmetic | O(n) | O(1) | High | Sum of diagonal elements |
| 7 | Determinant (via LU) | Derived | O(2n^3/3) | O(n^2) | Medium | Product of LU diagonal; can overflow |
| 8 | Determinant (Cofactor) | Derived | O(n!) | O(n^2) | Low | Only for n <= 5; educational use |
| 9 | Matrix Inverse | Derived | O(n^3) | O(n^2) | Low | Avoid; use LU solve instead for Ax=b |
| 10 | LU Decomposition | Decomposition | O(2n^3/3) | O(n^2) | High* | With partial pivoting; LAPACK DGETRF |
| 11 | LU Solve (after factoring) | Solve | O(n^2) | O(n) | High | Forward + back substitution |
| 12 | Cholesky Decomposition | Decomposition | O(n^3/3) | O(n^2/2) | High | SPD matrices only; 2x faster than LU |
| 13 | QR Decomposition (Householder) | Decomposition | O(2mn^2 - 2n^3/3) | O(mn) | High | Backward stable; used for least squares |
| 14 | QR Decomposition (Gram-Schmidt) | Decomposition | O(2mn^2) | O(mn) | Low | Classical GS loses orthogonality; use modified GS |
| 15 | SVD (Full) | Decomposition | O(4n^2m + 8nm^2 + 9m^3) | O(mn) | High | Gold standard; LAPACK DGESVD |
| 16 | Truncated SVD (rank-k) | Decomposition | O(mnk) | O((m+n)k) | High | Randomized algorithms; scikit-learn TruncatedSVD |
| 17 | Eigenvalues (Symmetric) | Eigenvalue | O(4n^3/3) | O(n^2) | High | QR algorithm; LAPACK DSYEV |
| 18 | Eigenvalues (General) | Eigenvalue | O(10n^3) | O(n^2) | Medium | QR iteration after Hessenberg reduction |
| 19 | Hessenberg Reduction | Decomposition | O(10n^3/3) | O(n^2) | High | Preprocessing step for eigenvalue computation |
| 20 | Schur Decomposition | Decomposition | O(10n^3) | O(n^2) | High | Upper triangular form; basis for eigenvalues |
| 21 | Moore-Penrose Pseudoinverse | Derived | O(mn^2) | O(mn) | High | Via SVD; for least-squares on rank-deficient systems |
| 22 | Sparse Matrix-Vector (CSR) | Sparse | O(nnz) | O(nnz + n) | High | nnz = number of non-zeros |
| 23 | Sparse Matrix-Matrix | Sparse | O(n * nnz) | O(nnz_result) | High | Output sparsity depends on fill-in |
| 24 | Kronecker Product | Arithmetic | O(m^2 * n^2) | O(m^2 * n^2) | High | Result is mn x mn; used in quantum computing |
Practical Guidance
Never compute the inverse to solve Ax = b. LU factorization followed by forward-back substitution is both faster (same O(n^3) but lower constant) and more numerically stable. Computing A^-1 explicitly doubles the work and squares the condition number's effect on error.
Choose the right decomposition. For general linear systems, use LU with partial pivoting. For symmetric positive definite matrices (covariance, kernel, Gram), use Cholesky — it is 2x faster and inherently stable. For least-squares problems, use QR (Householder). For rank-revealing analysis or when you need the condition number, use SVD.
Strassen is rarely faster in practice. Despite its O(n^2.807) complexity, Strassen's algorithm has higher constants, worse numerical stability, and poor cache behavior compared to optimized BLAS implementations. The crossover point where Strassen wins is typically n > 1000-4000 depending on the hardware. Libraries like OpenBLAS and Intel MKL automatically select the best strategy.
Sparse matrices change everything. When a matrix has fewer than ~10% non-zero entries, sparse formats (CSR, CSC, COO) dramatically reduce both storage and computation. A sparse matrix-vector product costs O(nnz) instead of O(n^2), which for a 10,000 x 10,000 matrix with 1% density means 100x fewer operations.
Frequently Asked Questions
What is the time complexity of matrix multiplication?
Naive matrix multiplication of two n x n matrices is O(n^3). Strassen's algorithm reduces this to O(n^2.807) and is practical for large matrices (n > ~1000). The current theoretical lower bound is O(n^2.3729) but these algorithms are impractical. Real-world performance depends more on cache optimization and BLAS library choice than asymptotic complexity.
Why is computing the matrix inverse considered numerically unstable?
Matrix inversion amplifies floating-point errors proportionally to the condition number. For solving Ax = b, LU decomposition with forward-back substitution is both faster and more stable. The only time you should compute an explicit inverse is when you need to apply A^-1 to many different right-hand sides and the matrix is well-conditioned.
What is the difference between LU, QR, and SVD decomposition complexity?
LU is O(2n^3/3) — fastest, used for square linear systems. QR is O(2mn^2 - 2n^3/3) — more stable, used for least-squares. SVD is the most expensive at O(mn^2) but reveals complete geometric structure: singular values, rank, null space, and condition number. Choose based on your problem structure.
When should I use Cholesky decomposition instead of LU?
Use Cholesky whenever your matrix is symmetric positive definite — common in covariance matrices, kernel matrices, and normal equations. Cholesky is 2x faster than LU, uses half the storage, needs no pivoting, and provides a uniqueness guarantee. If Cholesky fails, your matrix is not positive definite.
How does sparse matrix multiplication complexity differ from dense?
For sparse matrices with nnz non-zero elements, matrix-vector multiplication drops from O(n^2) to O(nnz), and matrix-matrix from O(n^3) to O(n * nnz). For a matrix with 1% density, this is roughly a 100x speedup. The key trade-off is element access overhead in formats like CSR/CSC and potential fill-in during factorization.