Linear Algebra
Gaussian Elimination
Row Operations
Learn the three elementary row operations: swap, scale, and add.
Three elementary row operations can be applied to any augmented matrix without changing the solution set:
| Operation | Notation | Description |
|---|---|---|
| Row Swap | Interchange two rows | |
| Row Scaling | Multiply a row by a non-zero constant | |
| Row Addition | Add a multiple of one row to another |
These correspond to legitimate algebraic manipulations: swapping equations, multiplying both sides by a constant, and adding equations together.
Row Echelon Form
Understand what it means for a matrix to be in row echelon form and reduced row echelon form (RREF).
A matrix is in row echelon form (REF) when:
- All zero rows are at the bottom
- Each pivot (leading entry) is to the right of the one above
- All entries below each pivot are zero
Reduced row echelon form (RREF) adds two stricter conditions:
- Every pivot is exactly
- All entries above and below each pivot are zero
| Property | REF | RREF |
|---|---|---|
| Zero rows at bottom | ||
| Pivots right of above | ||
| Zeros below pivots | ||
| Pivots equal | ||
| Zeros above pivots |
Most Gaussian elimination implementations stop at REF and use back-substitution, but reaching RREF gives the solution directly.
Solving Linear Systems
Use Gaussian elimination to solve systems of 2 or 3 equations.
Gaussian elimination solves linear systems by:
- Writing the system as an augmented matrix
- Applying row operations to reach row echelon form
- Using back-substitution (or continuing to RREF) to read the solution
For a 2x2 system, the matrix is (2 equations, 2 variables + constants). For a 3x3 system, it is . The process scales to any size — this is why Gaussian elimination is the foundation of computational linear algebra.
Concepts
The Augmented Matrix
A system of linear equations can be represented compactly as an augmented matrix. Each row corresponds to an equation, each column (except the last) corresponds to a variable, and the last column (separated by a vertical bar) contains the constants. For example:
Elementary Row Operations
Three operations can be applied to any augmented matrix without changing the solution set:
- Row Swap: Interchange two rows
- Row Scaling: Multiply a row by a non-zero constant
- Row Addition: Add a multiple of one row to another
These operations correspond to legitimate algebraic manipulations of the original equations.
Row Echelon Form (REF)
A matrix is in row echelon form when:
- All zero rows are at the bottom
- The leading entry (pivot) of each non-zero row is to the right of the leading entry of the row above
- All entries below a pivot are zero
Reduced Row Echelon Form (RREF) adds two more conditions:
- Every pivot is exactly
- All entries above and below each pivot are zero
| Property | REF | RREF |
|---|---|---|
| Zero rows at bottom | ||
| Pivots right of above | ||
| Zeros below pivots | ||
| Pivots equal | ||
| Zeros above pivots |
Gaussian Elimination Algorithm
The algorithm proceeds column by column, left to right:
- Find a non-zero entry in the current column (the pivot)
- Swap to bring the pivot row to the top of the remaining rows
- Scale the pivot row to make the pivot
- Eliminate all entries below the pivot using row addition
- Move to the next column and repeat
To reach RREF, after reaching row echelon form, work backwards eliminating entries above each pivot.
Worked Examples
Solving a 2x2 System
Problem
Solution Steps
Answer
Solving a 3x3 System
Problem
Solution Steps
Answer