Linear Systems Solvers

Choose a solver below

Solving Systems

Decompositions

Vector Spaces

Need Help?

Check the educational content below each solver for detailed explanations.

View all tutorials →

Calculating...

Home Linear Systems Lu_Decomposition

LU Decomposition Calculator: Matrix Factorization & System Solver

Perform LU Decomposition of a square matrix A into lower triangular L and upper triangular U matrices where A = LU. Optionally solve the linear system Ax = b using forward and back substitution.

Calculator

Enter your matrix below and click "Calculate" to see the step-by-step solution.

Matrix Size (n × n)

n =

Maximum size: 6×6

A Coefficient Matrix A (n × n)

b Constant Vector b (Optional)

Solve system Ax = b

Performing LU decomposition...

Enter a square matrix A to compute its LU decomposition.

Optionally provide vector b to solve the system Ax = b.

Learn About Lu_Decomposition

Understanding the concepts behind the calculations.

What is LU Decomposition?

LU decomposition (or LU factorization) breaks a square matrix $A$ into two simpler triangular matrices:

$$ \boxed{A = LU} $$

Where:

L (Lower Triangular): Has 1's on the diagonal and multipliers below. It represents the row operations performed.
U (Upper Triangular): The result of Gaussian elimination (row echelon form).

Visual Representation (3×3):

$$ 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} $$

💡 Core Concept: LU decomposition is essentially Gaussian elimination stored in matrix form. Instead of just getting the answer, we save the "steps" (multipliers) in $L$ so we can reuse them later!

When to Use LU Decomposition

✅ Perfect For:

Solving multiple systems $Ax=b_1, Ax=b_2...$ with the same $A$.
Computing determinants quickly ($\det(A) = \prod U_{ii}$).
Matrix inversion (solving $AX=I$ column by column).
Analyzing matrix structure (rank, singularity).

❌ Not Suitable For:

Matrices with zero pivots (requires PLU with pivoting).
Singular matrices ($\det(A) = 0$).
Very large sparse matrices (iterative methods are better).
Solving a single system once (Gaussian elimination is simpler).

🚀 Performance Tip: For solving $k$ systems with the same $A$:

LU Decomposition: One $O(n^3)$ factorization + $k$ fast $O(n^2)$ substitutions.
Gaussian Elimination: Requires $k$ separate $O(n^3)$ eliminations.

How LU Decomposition Works (Doolittle's Method)

We use Doolittle's Algorithm, which ensures $L$ has 1's on the diagonal. The process mirrors Gaussian elimination:

Form U: Perform row operations to eliminate entries below the pivot. The resulting matrix is $U$.
Form L: Record the multipliers used to eliminate those entries. Place them in the corresponding position in $L$.

$$ \text{Multiplier } l_{ij} = \frac{\text{Value to eliminate}}{\text{Pivot}} $$

📐 Important: If a pivot $u_{ii}$ is zero, standard LU fails. You must swap rows (PLU decomposition).

Step-by-Step Example

Problem: Decompose $A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 6 & 7 & 8 \end{bmatrix}$

Step 1: Eliminate Column 1 (Find $l_{21}, l_{31}$)

Pivot is $A_{11} = 2$.

To eliminate $4$ in Row 2: Multiplier $l_{21} = 4/2 = \mathbf{2}$.
Operation: $R_2 \leftarrow R_2 - 2R_1 \Rightarrow [0, 1, 1]$
To eliminate $6$ in Row 3: Multiplier $l_{31} = 6/2 = \mathbf{3}$.
Operation: $R_3 \leftarrow R_3 - 3R_1 \Rightarrow [0, 4, 5]$

$$ \text{Current Matrix: } \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 4 & 5 \end{bmatrix} $$

Step 2: Eliminate Column 2 (Find $l_{32}$)

New Pivot is $A_{22} = 1$.

To eliminate $4$ in Row 3: Multiplier $l_{32} = 4/1 = \mathbf{4}$.
Operation: $R_3 \leftarrow R_3 - 4R_2 \Rightarrow [0, 0, 1]$

$$ U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} $$

Step 3: Construct L and Verify

Place the multipliers into $L$ (with 1s on diagonal):

$$ L = \begin{bmatrix} 1 & 0 & 0 \\ \mathbf{2} & 1 & 0 \\ \mathbf{3} & \mathbf{4} & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} $$

✅ Verification: Multiply $L \times U$ to confirm you get $A$.

$$ \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 6 & 7 & 8 \end{bmatrix} = A $$

Solving Systems with LU Decomposition

To solve $Ax = b$, we substitute $A=LU$: $(LU)x = b \Rightarrow L(Ux) = b$.

Step 1: Forward Substitution (Solve $Ly = b$)

Since $L$ is lower triangular, we solve for $y$ from top to bottom.

$$ \begin{aligned} y_1 &= b_1 \\ y_2 &= b_2 - l_{21}y_1 \\ y_3 &= b_3 - l_{31}y_1 - l_{32}y_2 \end{aligned} $$

Step 2: Back Substitution (Solve $Ux = y$)

Since $U$ is upper triangular, we solve for $x$ from bottom to top.

$$ \begin{aligned} x_3 &= y_3 / u_{33} \\ x_2 &= (y_2 - u_{23}x_3) / u_{22} \\ x_1 &= (y_1 - u_{12}x_2 - u_{13}x_3) / u_{11} \end{aligned} $$

Example: Solve $Ax = b$ with $b = [4, 10, 18]^T$ using our $L$ and $U$.

1. Forward Substitution ($Ly = b$):

$y_1 = 4$
$y_2 = 10 - 2(4) = 2$
$y_3 = 18 - 3(4) - 4(2) = 18 - 12 - 8 = -2$
Result: $y = [4, 2, -2]^T$

2. Back Substitution ($Ux = y$):

$x_3 = -2 / 1 = -2$
$x_2 = (2 - 1(-2)) / 1 = 4$
$x_1 = (4 - 1(4) - 1(-2)) / 2 = (4 - 4 + 2) / 2 = 1$

Solution: $x = [1, 4, -2]^T$

LU Decomposition Variants

Method	L Diagonal	U Diagonal	Best For
Doolittle	1's	Any (Pivots)	General use (Standard)
Crout	Any	1's	Alternative formulation
LUP (with Pivoting)	1's	Any	When zero pivots occur ($PA=LU$)
Cholesky	$L$	$L^T$	Symmetric Positive Definite matrices

🔧 LUP Decomposition: If a pivot is zero, we swap rows using a permutation matrix $P$. The equation becomes $PA = LU$.

Advantages & Disadvantages

✅ Advantages

Efficient for multiple RHS: Factor once, solve many times.
Fast Determinant: $\det(A) = u_{11} \cdot u_{22} \cdots u_{nn}$.
Reveals Structure: Rank, singularity, and invertibility are obvious from $U$.
Memory Efficient: $L$ and $U$ can overwrite $A$ in memory.

❌ Disadvantages

Pivot Issues: Fails if a pivot is zero (requires pivoting).
Numerical Stability: Less stable than QR decomposition for ill-conditioned matrices.
Fill-in: Sparse matrices may become dense in $L$ and $U$.

Frequently Asked Questions

Q: When should I use LU vs Gaussian Elimination?

A: Use LU if you need to solve $Ax=b$ for many different $b$ vectors. Use Gaussian Elimination if you only have one $b$. LU saves the work of elimination in $L$ and $U$.

Q: What happens if a pivot is zero?

A: Standard LU fails. You must use LUP Decomposition, which swaps rows to find a non-zero pivot.

Q: Is LU decomposition unique?

A: Yes, if we fix the diagonal of $L$ to 1s (Doolittle) or $U$ to 1s (Crout), the decomposition is unique for non-singular matrices.

Q: How does LU help compute determinants?

A: Since $\det(L)=1$ and $\det(A)=\det(L)\det(U)$, then $\det(A) = \det(U)$. The determinant of a triangular matrix is just the product of its diagonal entries.

Practice Problems

Beginner

Find $L$ and $U$ for $A = \begin{bmatrix} 3 & 1 \\ 6 & 5 \end{bmatrix}$
Find $L$ and $U$ for $A = \begin{bmatrix} 2 & -1 \\ -4 & 3 \end{bmatrix}$

Intermediate

Verify the LU decomposition for $A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 6 & 7 & 8 \end{bmatrix}$
Use the LU factors from #3 to solve $Ax = [4, 10, 18]^T$

Advanced

Why does $A = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ require pivoting? Compute $P, L, U$.

Click to reveal solutions

1. $L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}$, $U = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$

2. $L = \begin{bmatrix} 1 & 0 \\ -2 & 1 \end{bmatrix}$, $U = \begin{bmatrix} 2 & -1 \\ 0 & 1 \end{bmatrix}$

3. $L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{bmatrix}$, $U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$

4. $x = [1, 4, -2]^T$

5. Pivot $A_{11}=0$ fails. Swap rows: $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$, $L = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, $U = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$

Summary

Key Takeaways

LU = L·U where $L$ is lower triangular (1's on diag) and $U$ is upper triangular.
Best for: Multiple systems with same $A$ (Factor once, solve many times).
Det(A): Product of $U$'s diagonal entries.
Requires: Non-zero pivots (use LUP if zero appears).
Process: Gaussian elimination creates $U$; multipliers create $L$.

💡 Pro Tip: Use our calculator to explore LU decomposition! Enter your matrix, and we'll show you $L$, $U$, and how to use them to solve systems step-by-step.