Overview
Gaussian Elimination transforms a matrix into triangular form and then solves variables by back substitution.
FoundationSource checked
Gaussian Elimination
Solves linear systems by eliminating variables row by row.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Intermediate
- Family
- Linear Algebra
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
numeric approximationmatrix operationlinear algebraconvergence checkerror control
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^3)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)
When to Use
- Use it for solving moderate-size dense linear systems.
- Use it when matrix factorization or row reduction is the right model.
- Use pivoting when numerical stability matters.
When Not to Use
- Avoid naive elimination without pivoting on ill-conditioned systems.
- Avoid it for very sparse systems when sparse solvers preserve structure better.
- Avoid returning a single solution when the system is singular or underdetermined.
What It Does
- Eliminates coefficients below pivots
- Solves a triangular system
Use Cases
- Solving systems of equations
- Matrix computations
- Engineering calculations
Inputs
- Coefficient matrix
- Right-hand-side vector
Outputs
- Solution vector
Key Formulas (1)
Row elimination
rowj = rowj − factor · rowi
row_j = row_j - factor * row_iRemoves one variable from a lower row using a pivot row.
Pseudocode
- 1.Choose a pivot row for each column
- 2.Scale or swap rows when needed
- 3.Eliminate entries below the pivot
- 4.Continue until the matrix is triangular
- 5.Use back substitution to solve variables
Canonical Example
- Input
- system: x + y = 3, x - y = 1
- Output
- x = 2, y = 1
- Explanation
- Elimination removes one variable, then back substitution recovers both values.
Implementation Notes
- Use partial pivoting in standard floating-point implementations.
- Track row swaps consistently across the matrix and vector.
- After forward elimination, solve variables with back substitution.
Common Pitfalls
- Dividing by a zero or tiny pivot.
- Forgetting to apply row swaps to the right-hand side.
- Ignoring singular or nearly singular systems.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow matrix entries below pivots turning into zeros.
Step 1 of 5: Choose a pivot row for each column
matrix-eliminationNotes
Pivoting is not an implementation detail; it is central to robust Gaussian elimination.
Sources (1)
What each reference supports for this entry.
Matrix Computations
BookReference text for numerical linear algebra, matrix factorizations, SVD, and eigenvalue methods.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toJacobi Method
Gaussian elimination solves directly, while Jacobi iterates.
Prerequisite ofLU Decomposition
LU decomposition factors the elimination process into reusable matrices.
Related Algorithms
Tags
Numerical MethodsLinear AlgebraClassic