← Back to linear algebra 1

Gaussian Elimination and Row Reduction

Gaussian elimination is a systematic method for solving systems of linear equations by reducing the number of variables. Instead of manipulating the equations directly, we work with an augmented matrix that represents the system.

Augmented Matrix

Consider the system:

{y+z=2x−z=3−2x+y+2z=−3\begin{cases} \quad \quad \quad y + z = 2 \\ \quad x \quad \quad - z = 3 \\ -2x + y + 2z = -3 \end{cases}

We represent this as an augmented matrix:

[011210−13−212−3]\left[\begin{array}{ccc|c} 0 & 1 & 1 & 2 \\ 1 & 0 & -1 & 3 \\ -2 & 1 & 2 & -3 \end{array}\right]

The vertical line separates the coefficients from the constants on the right-hand side. We solve the system by applying Elementary row operations.

We can manipulate the augmented matrix using three types of elementary row operations:

  1. Interchange: Exchange two rows. Notation: ri↔rjr_i \leftrightarrow r_j
  2. Scalling: Multiply a row by a non-zero constant. Notation: ri→crir_i \rightarrow cr_i (where c≠0c \neq 0)
  3. Replacement: Add a multiple of one row to another. Notation: ri→ri+crjr_i \rightarrow r_i + cr_j

These operations transform the system into an equivalent system (same solution set) that is easier to solve.

Goal: Transform an augmented matrix into row echelon form (or RREF) using elementary row operations.

Step-by-Step Process:

Step 1: Create the First Pivot

  • Find the leftmost non-zero column
  • If needed, swap rows to get a non-zero entry at the top
  • This entry becomes the first pivot

Step 2: Eliminate Below the Pivot

  • Use replacement operations to make all entries below the pivot equal to zero
  • Add multiples of the pivot row to rows below it

Step 3: Move to the Next Pivot

  • Ignore the row and column with the first pivot
  • Repeat Steps 1-2 for the remaining submatrix until the matrix is in row echelon form

Step 4: Back Substitution

  • Scale pivot rows so each pivot becomes 1
  • Eliminate entries above each pivot

Interactive Row Reduction Example

Step 0 of 6

The last step directly gives us.

x=2,y=3,z=−1.x = 2, y = 3, z=-1.

Row Echelon Form (REF)

A matrix is in row echelon form if:

  1. All rows consisting entirely of zeros are at the bottom
  2. The first non-zero entry in each row (called a pivot) is to the right of the pivot in the row above
  3. All entries in a column below a pivot are zero

It is in reduced row echelon form (RREF) if it further satisfies:

  1. Each pivot equals 1
  2. Each pivot is the only non-zero entry in its column

Try it yourself

Solve the following system of linear equations.

{x−2y+z=0      2y−8z=85x      −5z=10\begin{cases} x - 2y + z = 0\\ \quad \;\;\; 2y - 8z = 8 \\ 5x \quad \;\;\;-5z = 10 \end{cases}

Interactive Row Reduction Calculator

Example: [[1, 0, 2, 3], [0, 1, -1, 2], [2, 1, 3, 8]]