Matrices
1.7.4 Gaussian Elimination
Solving linear systems AX = B using the Gaussian elimination algorithm — augmented matrix, elementary row operations, row echelon form, unique/infinite/no solutions, overdetermined and underdetermined systems.
1.7.4 Gaussian Elimination
Gaussian elimination (Gauss, 1777–1855) solves AX = B in O(n³) operations — far more efficient than matrix inversion O(n!) for large systems. It also handles overdetermined and underdetermined systems.
Definition 1.28 — Augmented matrix [A|B]: Coefficient matrix A with right-hand side B appended as an extra column.
Example: x + 2y = 5; 3x + y = 7 → [1 2 | 5; 3 1 | 7]
Example: x + 2y = 5; 3x + y = 7 → [1 2 | 5; 3 1 | 7]
Definition 1.29 — Elementary row operations (don't change solution set):
1. Interchange rows Ri ↔ Rj
2. Scale row: Ri → λRi (λ ≠ 0)
3. Add multiple: Ri → Ri + λRj
1. Interchange rows Ri ↔ Rj
2. Scale row: Ri → λRi (λ ≠ 0)
3. Add multiple: Ri → Ri + λRj
Definition 1.30 — Row echelon form (REF): Zero rows at bottom; leading entry (pivot) of each row is 1 and strictly right of row above.
Definition 1.31 — Reduced row echelon form (RREF): REF + each pivot column has zeros everywhere else.
Definition 1.27 — Three cases:
• Unique solution: exactly determined and consistent
• Infinitely many solutions: consistent and indeterminate
• No solution: inconsistent
• Unique solution: exactly determined and consistent
• Infinitely many solutions: consistent and indeterminate
• No solution: inconsistent
Example 1.22 — Unique Solution
Solve: x + 2y + 3z = 14, 2x + 3y + z = 11, 3x + y + 4z = 17
| Step | Operation | Augmented matrix |
|---|---|---|
| Start | — | [1,2,3|14; 2,3,1|11; 3,1,4|17] |
| 1 | R₂→R₂−2R₁, R₃→R₃−3R₁ | [1,2,3|14; 0,−1,−5|−17; 0,−5,−5|−25] |
| 2 | R₂→−R₂, R₃→R₃−5R₂ | [1,2,3|14; 0,1,5|17; 0,0,20|60] |
| 3 | R₃→R₃/20 | [1,2,3|14; 0,1,5|17; 0,0,1|3] |
| Back sub | z=3 → y=17−15=2 → x=14−4−9=1 | x=1, y=2, z=3 |
Example — Infinitely Many Solutions
When last row becomes [0,0,0|0] → free parameter exists:
[1,2,−1|3; 0,1,−2|1; 0,0,0|0]
Let z = t (free). Then y = 1 + 2t, x = 3 − 2(1+2t) + t = 1 − 3t
x = 1−3t, y = 1+2t, z = t (infinitely many, t ∈ ℝ)
Example — No Solution
Reduced to: [1,2,3|4; 0,1,1|2; 0,0,0|5]
Last row 0x + 0y + 0z = 5 is impossible → No solution (inconsistent)
Solving Linear Equations by Matrix Inversion (1.7.1)
AX = B → X = A−1B (only if A is square and non-singular)
Efficiency note: Matrix inversion requires O(n!) operations. Gaussian elimination only O(n³). Always prefer Gaussian for large systems.