Mathematics RU

Practice · Chapter 36

Gaussian elimination

Gaussian elimination: solve a system, find the rank of a matrix, tell how many solutions a system has, and bring a matrix to reduced row echelon form.

How to solve it

Gaussian elimination simplifies a system without changing its solutions: rows may be swapped, multiplied by a non-zero number, and one row may get another row times a number added to it. The goal is echelon form, with zeros under every pivot. From there the solution is read from the bottom up.

Step by step

  1. Write the augmented matrix: the coefficients and, past the bar, the right-hand sides.
  2. Choose a pivot in the first column ($\pm 1$ is handy; if it is zero, swap rows) and clear everything below it.
  3. Move to the next column and the next row and repeat. You reach echelon form.
  4. The rank is the number of non-zero rows. A row $0 = c$ with $c \ne 0$ means no solutions; a rank below the number of unknowns means infinitely many; otherwise exactly one.
  5. To solve, go from the bottom up, substituting the unknowns found. For the reduced form, clear the entries above the pivots too.
The coefficient matrix. The augmented matrix. If its rank exceeds that of $A$, there are no solutions. The number of unknowns. Equal ranks below $n$ mean infinitely many solutions. Example: a matrix with two equal rows loses one row to zero after a subtraction, so its rank is one less than the number of rows.

Common mistakes

  • Changing a row but not its right-hand side. Operations act on the whole row of the augmented matrix.
  • Adding a multiple of a row to itself — that is scaling, not elimination.
  • Deciding how many solutions there are before reaching echelon form.
  • Taking the number of rows of the original matrix as the rank instead of the non-zero rows of the echelon form.

Example

Mathematics

Chapters

Introduction

  1. 0 What mathematics is

I Numbers

  1. 1 Counting
  2. 2 Zero and minus
  3. 3 Primes
  4. 4 Divisibility
  5. 5 Fractions
  6. 6 Root two

II Algebra

  1. 7 Letters
  2. 8 Equations
  3. 9 Functions and graphs
  4. 10 Quadratic equations
  5. 11 Systems and inequalities
  6. 12 Powers and logarithms
  7. 13 Sequences
  8. 14 Polynomials
  9. 15 Complex numbers

III Geometry

  1. 16 Euclid's Elements
  2. 17 The triangle
  3. 18 Pythagoras' theorem
  4. 19 The circle and π
  5. 20 Area and volume
  6. 21 Trigonometry
  7. 22 Vectors
  8. 23 Symmetry
  9. 24 Conic sections

IV Calculus

  1. 25 Limits
  2. 26 The derivative
  3. 27 Extrema
  4. 28 The integral
  5. 29 The number e
  6. 30 Series
  7. 31 Differential equations
  8. 32 Several variables
  9. 33 Fourier series
  10. 34 Complex analysis

V Linear algebra

  1. 35 Matrices
  2. 36 Gaussian elimination
  3. 37 Vector spaces
  4. 38 Eigenvectors
  5. 39 Least squares and SVD

VI Structures

  1. 40 Groups
  2. 41 Remainders and ciphers
  3. 42 Rings and fields
  4. 43 Galois theory
  5. 44 Zeta and curves

VII Chance & data

  1. 45 Combinatorics
  2. 46 Graphs
  3. 47 Probability
  4. 48 Random variables
  5. 49 Statistics
  6. 50 Markov and information

VIII Foundations

  1. 51 Logic and sets
  2. 52 Infinities
  3. 53 Rigorous analysis
  4. 54 Measure and integral
  5. 55 Functional analysis
  6. 56 Gödel and Turing

IX Horizons

  1. 57 Topology
  2. 58 Non-Euclidean geometries
  3. 59 Chaos and fractals
  4. 60 The frontier