Algebra • Numerical Linear Algebra Flagship

LU Decomposition Calculator

Factor any square matrix $A$ into Lower ($L$) and Upper ($U$) triangular components ($A = L \cdot U$) with exact Doolittle algorithm derivations, multiplier tracking, and determinant calculation.

Reviewed by Sanjay Samanta & Academic Review Board
Verified Doolittle & Gaussian Factorization Proofs
Last Updated: September 2026
Matrix Calculator (A & B) Row Echelon Form (REF / RREF) Matrix Rank LU Decomposition Char Polynomial Eigenvalues & Vectors
Direct Answer & Overview
Verified Educational Guide

LU Decomposition Overview & Formulas

LU decomposition factors a square matrix A into A = L · U, where L is unit lower triangular (diagonal entries = 1, upper entries = 0) and U is upper triangular (lower entries = 0). It accelerates multi-vector linear system solving and determinant evaluation.

Primary Mathematical Formula Standard Mathematical Model
Standard Equation
ƒ(x)
Q.E.D.
A = L · U, det(A) = ∏ u_ii (Product of U diagonal), Ax = b ⟹ Ly = b (Forward), Ux = y (Backward)
Evaluated with exact mathematical formulation • Rigorously verified
Exact Formula
Input Parameters
Required
1
Square matrix size (N × N, e.g. 2×2, 3×3, 4×4)
2
Matrix coefficients a_ij
Expected Outputs
Calculated
Unit Lower Triangular Matrix L
Upper Triangular Matrix U
Matrix determinant det(A) = det(U)
Step-by-step row elimination multipliers
Worked Numerical Example
Instant Verification
Decompose matrix A = [[2, 3], [4, 7]] into L and U
→ Multiplier m₂₁ = 4 / 2 = 2. Row 2 of U = [4 - 2(2), 7 - 2(3)] = [0, 1]. Lower matrix L has 1s on diagonal and m₂₁ = 2 below.
L = [[1, 0], [2, 1]], U = [[2, 3], [0, 1]] (Check: L·U = [[2, 3], [4, 7]])

LU Matrix Factorization Concept & Triangular Matrices

LU decomposition is the matrix equivalent of factoring integers. It splits a dense $n \times n$ matrix $A$ into two triangular matrices whose structured sparsity makes computation vastly faster:

$$A = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{pmatrix} = L \cdot U$$
Matrix L (Unit Lower Triangular)

All entries above the main diagonal are zero. Diagonal entries are strictly 1. Subdiagonal entries $l_{ij}$ store the exact elimination multipliers used during Gaussian elimination.

Matrix U (Upper Triangular)

All entries below the main diagonal are zero. Matrix $U$ is the exact Row Echelon Form (REF) produced by forward Gaussian elimination without row scaling.

Doolittle’s Algorithm & Forward Elimination Derivation

In Doolittle’s method, the entries of $L$ and $U$ are computed row-by-row and column-by-column:

1. Upper Matrix Row $i$:
$u_{ij} = a_{ij} - \sum_{k=1}^{i-1} l_{ik} u_{kj} \quad (j \ge i)$
2. Lower Matrix Column $j$:
$l_{ij} = \frac{1}{u_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} u_{kj} \right) \quad (i > j)$

Two-Stage Linear System Solving ($L\mathbf{y} = \mathbf{b}$, $U\mathbf{x} = \mathbf{y}$)

Instead of solving $A\mathbf{x} = \mathbf{b}$ directly, factor $A = LU$ and substitute $\mathbf{y} = U\mathbf{x}$:

Stage 1 • Forward Substitution ($L\mathbf{y} = \mathbf{b}$)

Because $L$ is lower triangular, solve top-to-bottom: $y_1 = b_1$, $y_2 = b_2 - l_{21}y_1$, and so on, in $\mathcal{O}(n^2)$ arithmetic steps.

Stage 2 • Backward Substitution ($U\mathbf{x} = \mathbf{y}$)

Because $U$ is upper triangular, solve bottom-to-top: $x_n = y_n / u_{nn}$, substituting upward to isolate all remaining variables $x_i$.

Fast Determinant Computation via Diagonal Product

Determinants of triangular matrices equal the product of their main diagonal entries. Applying the multiplicative property $\det(AB) = \det(A)\det(B)$:

$$\det(A) = \det(L) \cdot \det(U) = (1 \cdot 1 \dots 1) \cdot (u_{11} u_{22} \dots u_{nn}) = \prod_{i=1}^n u_{ii}$$

Computational Efficiency & Finite Element Analysis

Multi-Load Structural Engineering

In finite element modeling (FEA), the stiffness matrix $K$ is factored once into $LU$. Testing thousands of different wind and gravity load vectors $b$ runs in $\mathcal{O}(n^2)$ rather than re-factoring $K$.

Circuit Simulation (SPICE)

Analog circuit simulators factor the nodal admittance matrix into $LU$ during transient time-stepping simulations to analyze voltage responses over millions of time steps.

Numerical Stability (Partial Pivoting)

$PA = LU$ pivoting controls roundoff errors in floating-point operations by swapping the largest available column entry into the diagonal pivot position.

Graded Step-by-Step Numerical Solutions

Example 1 • 3x3 Doolittle Factorization Standard Tier

Decompose $A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$ into $L$ and $U$

1. Row 1 of $U$: $[u_{11}, u_{12}, u_{13}] = [2, 1, 1]$.

2. Column 1 of $L$: $l_{21} = 4/2 = 2$, $l_{31} = 8/2 = 4$.

3. Row 2 of $U$: $u_{22} = 3 - 2(1) = 1$, $u_{23} = 3 - 2(1) = 1$.

4. Column 2 of $L$: $l_{32} = (7 - 4(1)) / 1 = 3$.

5. Row 3 of $U$: $u_{33} = 9 - (4(1) + 3(1)) = 2$.

$L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}, \quad U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}, \quad \det(A) = 2 \cdot 1 \cdot 2 = 4$.

Common Pitfalls & Zero Pivot Singularities

Pitfall 1: Zero Diagonal Pivot Division by Zero
Standard Doolittle $A = LU$ fails if any diagonal pivot $u_{kk} = 0$, as computing $l_{ik} = \dots / u_{kk}$ attempts division by zero. In such cases, row swapping (partial pivoting $PA = LU$) must be performed.
Pitfall 2: Confusing Multiplier Signs in Lower Matrix L
When eliminating $R_i - m_{ij} R_j \rightarrow R_i$, the entry placed into $l_{ij}$ is the positive multiplier $m_{ij}$, NOT $-m_{ij}$.
Fact-Checked & Verified • Computational Accuracy Standards
Updated July 2026 • Editorial Policy
Authored By
Sanjay Samanta

Lead Developer & Founder of Basic Math Tools. Specializes in browser-native computational algorithms and applied mathematics.

Reviewed & Verified By
Academic Review Board

Mathematics & curriculum specialists. Audited against standard algebraic and arithmetic principles.

Found an error or have an improvement suggestion? Report a calculation issue

Frequently Asked Questions

What is LU Decomposition of a matrix?
LU decomposition (factorization) factors a square matrix A into the product of a unit lower triangular matrix L (ones on the main diagonal and zeros above) and an upper triangular matrix U (zeros below the main diagonal), such that A = L · U.
Why is LU decomposition useful for solving linear systems (Ax = b)?
Solving Ax = b becomes solving two simple triangular systems in sequence: first forward substitution for Ly = b, followed by backward substitution for Ux = y. This computes in O(n²) time per right-hand side b, compared to O(n³) for full matrix reinversion.
When is partial pivoting (PA = LU) required?
If any diagonal pivot element becomes zero during Gaussian elimination or is very close to zero (causing numerical instability), row permutation matrix P is introduced to swap rows: P · A = L · U.
What is the difference between Doolittle and Crout LU algorithms?
In Doolittle’s algorithm, the lower triangular matrix L has 1s on its main diagonal (unit lower triangular). In Crout’s algorithm, the upper triangular matrix U has 1s on its main diagonal (unit upper triangular).
How do you calculate the determinant of a matrix using LU decomposition?
Because det(L) = 1 (unit triangular), det(A) = det(L · U) = det(L) · det(U) = 1 · det(U). The determinant of U is simply the product of its main diagonal entries: det(A) = u₁₁ · u₂₂ · ... · u_nn.

Related Tools

Matrix Determinant Calculator | Calculate 2x2, 3x3, 4x4 Determinants

Algebra

Row Echelon Form Calculator

Algebra

Matrix Calculator

Algebra

Reduced Row Echelon Form (RREF) Calculator

Algebra

Matrix Rank Calculator

Algebra

Characteristic Polynomial Calculator

Algebra

Cookie & Privacy Notice

We use essential cookies for calculator preferences and third-party advertising cookies (including Google AdSense) to keep all math solvers 100% free. Learn more in our Privacy Policy.

Preferences