LA-1.4

Available

Gaussian Elimination

Gaussian elimination is the workhorse algorithm of linear algebra. It systematically transforms matrices into echelon forms, enabling us to solve linear systems, compute ranks, and understand the structure of solutions.

3-4 hours Foundation Level 10 Objectives

Learning Objectives

Perform the three elementary row operations correctly
Reduce any matrix to row echelon form (REF)
Reduce any matrix to reduced row echelon form (RREF)
Identify pivot positions and free variables
Solve systems of linear equations systematically
Determine whether a system has no solution, unique solution, or infinitely many solutions
Understand the connection between RREF and matrix rank
Express solution sets in parametric vector form
Apply Gaussian elimination to compute matrix inverses
Understand the computational complexity and numerical considerations

Prerequisites

Basic matrix notation and terminology
Solving simple linear equations
Field axioms from LA-1.1
Basic set notation and logic
Familiarity with mathematical proof techniques

Historical Context

Although named after Carl Friedrich Gauss (1777–1855), systematic elimination methods for solving linear equations date back to ancient civilizations. The Nine Chapters on the Mathematical Art, a Chinese text from around 200 BCE, contains methods equivalent to Gaussian elimination for solving systems of linear equations.

Gauss used the method extensively in his work on astronomy and geodesy, particularly in his method of least squares for fitting curves to observational data. His systematic approach and clear exposition led to the method bearing his name.

Wilhelm Jordan (1842–1899), a German geodesist, later developed the refinement that produces reduced row echelon form, which is why RREF is sometimes calledGauss-Jordan elimination.

Today, Gaussian elimination forms the backbone of numerical linear algebra. Modern implementations include pivoting strategies and are optimized for computer architectures, enabling the solution of systems with millions of variables.

1. Elementary Row Operations

Every step in Gaussian elimination consists of one of three elementary row operations. These operations preserve the solution set of a linear system.

Definition 1.1: Elementary Row Operations

The three elementary row operations (EROs) on a matrix are:

Row swap (Rᵢ ↔ Rⱼ): Interchange rows $i$ and $j$
Row scaling (Rᵢ ← cRᵢ): Multiply row $i$ by a non-zero scalar $c$
Row addition (Rᵢ ← Rᵢ + cRⱼ): Add $c$ times row $j$ to row $i$

Theorem 1.1: EROs Preserve Solutions

If matrix $B$ is obtained from matrix $A$ by a sequence of elementary row operations, then the systems $Ax = b$ and $Bx = b'$ (where $b'$ is obtained by applying the same operations to $b$ ) have the same solution set.

Proof of Theorem 1.1:

Each ERO is reversible:

Swap is its own inverse
Scaling by $c$ is reversed by scaling by $1/c$
Adding $cR_j$ to $R_i$ is reversed by adding $-cR_j$ to $R_i$

If $x$ satisfies one system, applying the operations shows it satisfies the other, and vice versa by applying the inverse operations.

∎

Example 1.1: Applying Row Operations

Apply EROs to eliminate the entry below the pivot:

\begin{pmatrix} 2 & 4 & 6 \\ 1 & 3 & 5 \end{pmatrix} \xrightarrow{R_1 \leftrightarrow R_2} \begin{pmatrix} 1 & 3 & 5 \\ 2 & 4 & 6 \end{pmatrix} \xrightarrow{R_2 \leftarrow R_2 - 2R_1} \begin{pmatrix} 1 & 3 & 5 \\ 0 & -2 & -4 \end{pmatrix}

The first pivot is now 1, and we've eliminated the entry below it.

Remark 1.1: Why Swap Rows?

We often swap rows to get a "nice" pivot (like 1) or to avoid dividing by small numbers (numerical stability). Any non-zero entry in the pivot column will work mathematically, but some choices are better computationally.

Definition 1.2: Elementary Matrices

An elementary matrix is obtained by applying one ERO to the identity matrix. Left-multiplying by an elementary matrix performs that ERO on any matrix.

Example 1.2: Elementary Matrices

For $3 \times 3$ matrices:

E_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \text{ (swap } R_1 \leftrightarrow R_2\text{)}

E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{pmatrix} \text{ (scale } R_2 \text{ by } 3\text{)}

E_3 = \begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \text{ (add } -2R_1 \text{ to } R_2\text{)}

Theorem 1.2: Elementary Matrices are Invertible

Every elementary matrix $E$ is invertible, and $E^{-1}$ is also elementary:

Swap: $E^{-1} = E$ (swap is self-inverse)
Scale by $c$ : $E^{-1}$ scales by $1/c$
Add $cR_j$ to $R_i$ : $E^{-1}$ adds $-cR_j$ to $R_i$

Remark 1.2: Matrix Factorization Preview

If we record all elementary matrices used: $E_k \cdots E_2 E_1 A = U$ (REF), then $A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U = LU$ . This is theLU decomposition, fundamental in numerical computing.

2. Row Echelon Form (REF)

Definition 1.2: Row Echelon Form

A matrix is in row echelon form (REF) if:

All zero rows are at the bottom
The leading entry (pivot) of each non-zero row is to the right of the pivot in the row above
All entries below a pivot are zero

Example 1.2: REF Examples

These matrices are in REF (pivots shown in bold):

\begin{pmatrix} \mathbf{2} & 3 & 1 \\ 0 & \mathbf{5} & 2 \\ 0 & 0 & \mathbf{1} \end{pmatrix}, \quad \begin{pmatrix} \mathbf{1} & 2 & 0 & 3 \\ 0 & 0 & \mathbf{4} & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

This matrix is NOT in REF:

\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \quad \text{(non-zero entry below first pivot)}

Algorithm 1.1: Gaussian Elimination (Forward Phase)

INPUT: m × n matrix A
OUTPUT: REF of A

for j = 1 to n:
    # Find pivot in column j
    Find row i ≥ current row with A[i,j] ≠ 0
    if no such row exists:
        continue to next column
    
    # Move pivot to current row
    Swap current row with row i
    
    # Eliminate entries below pivot
    for each row k below current row:
        if A[k,j] ≠ 0:
            A[k] ← A[k] - (A[k,j]/A[current,j]) × A[current]
    
    Advance to next row

return A

Example 1.3: Complete Reduction to REF

Reduce to row echelon form:

\begin{pmatrix} 1 & 2 & 1 & 3 \\ 2 & 4 & 3 & 8 \\ 1 & 2 & 2 & 5 \end{pmatrix}

Step 1: Eliminate below first pivot (column 1):

\xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 1 & 2 \end{pmatrix}

Step 2: Column 2 has no pivot candidates. Move to column 3:

\xrightarrow{R_3 - R_2} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}

This is REF. Pivot columns are 1 and 3.

Definition 2.1: Pivot and Pivot Position

A pivot is the first non-zero entry in a row of an echelon form. The pivot position is the location (row, column) of a pivot. A pivot column is a column containing a pivot position.

Remark 2.1: Staircase Pattern

The pivots in REF form a "staircase" pattern descending from left to right. Each step down corresponds to moving to the next row, and each step right corresponds to moving to at least the next column.

Example 2.1: Identifying Pivot Positions

For the REF:

\begin{pmatrix} \boxed{1} & 3 & 0 & 2 \\ 0 & 0 & \boxed{2} & 1 \\ 0 & 0 & 0 & \boxed{4} \\ 0 & 0 & 0 & 0 \end{pmatrix}

Pivot positions: (1,1), (2,3), (3,4). Pivot columns: 1, 3, 4.

Non-pivot column: 2. If this were a system, column 2 would give a free variable.

Theorem 2.1: Row Equivalence

Matrices $A$ and $B$ are row equivalent if one can be obtained from the other by EROs. Row equivalent matrices have:

The same row space
The same null space
The same rank
The same RREF

3. Reduced Row Echelon Form (RREF)

Definition 1.3: Reduced Row Echelon Form

A matrix is in reduced row echelon form (RREF) if:

It is in row echelon form
Every pivot is equal to 1
Each pivot is the only non-zero entry in its column

Theorem 1.2: Uniqueness of RREF

Every matrix has a unique reduced row echelon form.

Remark 1.1: Computing RREF

To obtain RREF from REF, perform back substitution: starting from the rightmost pivot, scale each pivot row to make the pivot 1, then eliminate all entries above it.

Example 1.4: From REF to RREF

Continue from Example 1.3:

\begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix} \xrightarrow{R_1 - R_2} \begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}

This is RREF. Pivots are 1, in columns 1 and 3.

Algorithm 1.2: Gauss-Jordan Elimination (Complete)

INPUT: m × n matrix A
OUTPUT: RREF of A

# Forward phase (produce REF)
Apply Gaussian Elimination to get REF

# Backward phase (produce RREF)
for each pivot, from bottom to top:
    # Scale row to make pivot = 1
    Divide pivot row by pivot value
    
    # Eliminate entries above pivot
    for each row above the pivot row:
        if entry in pivot column ≠ 0:
            Subtract appropriate multiple

return A

Remark 3.1: Computational Efficiency

Forward elimination requires $\approx \frac{2}{3}n^3$ operations for an $n \times n$ matrix. Back substitution adds $\approx n^2$ operations. For RREF, the backward phase also costs $\approx n^2$ .

Example 3.1: Full RREF Computation

Reduce completely to RREF:

\begin{pmatrix} 2 & 4 & -2 & 2 \\ 1 & 2 & 1 & 3 \\ 3 & 6 & 0 & 6 \end{pmatrix}

Forward phase:

\xrightarrow{R_1 \leftrightarrow R_2} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 2 & 4 & -2 & 2 \\ 3 & 6 & 0 & 6 \end{pmatrix}

\xrightarrow{R_2 - 2R_1, R_3 - 3R_1} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & -4 & -4 \\ 0 & 0 & -3 & -3 \end{pmatrix}

\xrightarrow{R_2 / (-4)} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & -3 & -3 \end{pmatrix}

\xrightarrow{R_3 + 3R_2} \begin{pmatrix} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

Backward phase:

\xrightarrow{R_1 - R_2} \begin{pmatrix} 1 & 2 & 0 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

This is the RREF. Pivot columns: 1 and 3. Rank = 2.

4. Solving Linear Systems

Definition 1.4: Augmented Matrix

For the system $Ax = b$ , the augmented matrix is $[A \mid b]$ , formed by appending $b$ as an extra column.

Theorem 1.3: Solution Structure

For a linear system $Ax = b$ with augmented matrix in RREF:

No solution: If a row has form $[0 \cdots 0 \mid c]$ with $c \neq 0$
Unique solution: If every column of $A$ is a pivot column
Infinitely many solutions: If consistent and there are free variables (non-pivot columns)

Example 1.5: Solving a System

Solve the system:

\begin{cases} x + 2y + z = 4 \\ 2x + 4y + 3z = 10 \\ x + 2y + 2z = 6 \end{cases}

Form augmented matrix and reduce to RREF:

\begin{pmatrix} 1 & 2 & 1 & | & 4 \\ 2 & 4 & 3 & | & 10 \\ 1 & 2 & 2 & | & 6 \end{pmatrix} \xrightarrow{\text{RREF}} \begin{pmatrix} 1 & 2 & 0 & | & 2 \\ 0 & 0 & 1 & | & 2 \\ 0 & 0 & 0 & | & 0 \end{pmatrix}

Pivot columns: 1, 3 (basic variables: $x$ , $z$ ). Free variable: $y$ .

Reading off equations: $x + 2y = 2$ and $z = 2$ .

Solution: $x = 2 - 2t$ , $y = t$ , $z = 2$ for any $t \in \mathbb{R}$ .

In vector form: $\begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 2 \end{pmatrix} + t\begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix}$

Example 1.6: Inconsistent System

Determine if the system has solutions:

\begin{pmatrix} 1 & 2 & | & 3 \\ 2 & 4 & | & 5 \end{pmatrix} \xrightarrow{R_2 - 2R_1} \begin{pmatrix} 1 & 2 & | & 3 \\ 0 & 0 & | & -1 \end{pmatrix}

The second row reads $0x + 0y = -1$ , which is impossible. No solution exists.

Definition 4.1: Basic and Free Variables

Variables corresponding to pivot columns are basic variables. Variables corresponding to non-pivot columns are free variables.

Free variables can take any value; basic variables are determined by the free variables.

Remark 4.1: Parametric Form

The solution to a system with free variables is typically written inparametric vector form:

x = x_p + t_1 v_1 + t_2 v_2 + \cdots + t_k v_k

where $x_p$ is a particular solution and $v_1, \ldots, v_k$ span the null space.

Theorem 4.1: Homogeneous Systems

A homogeneous system $Ax = 0$ is always consistent (has $x = 0$ as a solution). It has non-trivial solutions if and only if there are free variables, i.e., if $\text{rank}(A) < n$ .

Example 4.1: Geometric Interpretation

Consider the system:

\begin{cases} x + y = 2 \\ 2x + 2y = 4 \end{cases}

Both equations represent the same line $x + y = 2$ . The solution set is this entire line: $\{(t, 2-t) : t \in \mathbb{R}\}$ .

Example 4.2: Three Planes

Three linear equations in 3 variables represent three planes. Possible configurations:

Unique solution: Three planes meet at a single point
Line of solutions: Three planes share a common line
Plane of solutions: All three equations are equivalent (same plane)
No solution: Planes don't all meet (parallel, or pairwise intersecting lines don't share a point)

5. Matrix Rank

Definition 1.5: Rank

The rank of a matrix $A$ , denoted $\text{rank}(A)$ , is the number of pivot positions in any echelon form of $A$ .

Equivalently, it equals the number of non-zero rows in the RREF of $A$ .

Theorem 1.4: Rank and Solutions

For an $m \times n$ matrix $A$ and system $Ax = b$ :

$\text{rank}(A) \leq \min(m, n)$
System is consistent iff $\text{rank}(A) = \text{rank}([A|b])$
Unique solution iff consistent and $\text{rank}(A) = n$
Number of free variables = $n - \text{rank}(A)$

Remark 1.2: Connection to Linear Algebra

The rank will later be identified with the dimension of the column space (image) of the matrix. The number of free variables equals the dimension of the null space (kernel). The Rank-Nullity Theorem states:

\text{rank}(A) + \text{nullity}(A) = n

Example 5.1: Computing Rank

Find the rank of:

A = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 6 & 8 \\ 1 & 1 & 1 & 1 \end{pmatrix}

Solution: Reduce to REF:

\xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 \\ 0 & -1 & -2 & -3 \end{pmatrix}

\xrightarrow{R_2 \leftrightarrow R_3} \begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & -1 & -2 & -3 \\ 0 & 0 & 0 & 0 \end{pmatrix}

Two non-zero rows, so $\text{rank}(A) = 2$ .

Theorem 5.1: Rank and Invertibility

An $n \times n$ matrix $A$ is invertible if and only if $\text{rank}(A) = n$ , i.e., the RREF of $A$ is the identity matrix.

Theorem 5.2: Fundamental Theorem of Linear Algebra (Preview)

For an $m \times n$ matrix $A$ with rank $r$ :

$\dim(\text{Col}(A)) = r$ (column space)
$\dim(\text{Row}(A)) = r$ (row space)
$\dim(\text{Null}(A)) = n - r$ (null space)
$\dim(\text{Null}(A^T)) = m - r$ (left null space)

Remark 5.1: Four Fundamental Subspaces

These four subspaces are deeply connected. The row space and null space are orthogonal complements in $\mathbb{R}^n$ . The column space and left null space are orthogonal complements in $\mathbb{R}^m$ .

Example 5.2: Determining Solution Existence

For which values of $b$ does the system have a solution?

\begin{pmatrix} 1 & 2 \\ 3 & 6 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}

Solution: The coefficient matrix has $\text{rank} = 1$ (Row 2 = 3×Row 1).

For consistency, we need $\text{rank}([A|b]) = 1$ as well.

This requires $b_2 = 3b_1$ .

So the system has solutions iff $b = (b_1, 3b_1)$ for some $b_1$ .

Corollary 5.1: Full Row Rank

If $A$ is $m \times n$ with $\text{rank}(A) = m$ (full row rank), then $Ax = b$ has a solution for every $b$ .

Corollary 5.2: Full Column Rank

If $A$ is $m \times n$ with $\text{rank}(A) = n$ (full column rank), then $Ax = b$ has at most one solution for any $b$ .

6. Computing Matrix Inverses

Algorithm 6.1: Finding Inverse via Row Reduction

INPUT: n × n matrix A
OUTPUT: A⁻¹ (or indication that A is not invertible)

Form augmented matrix [A | I]

Reduce [A | I] to RREF

if left half becomes I:
    return right half (this is A⁻¹)
else:
    A is not invertible

Example 6.1: Computing an Inverse

Find the inverse of:

A = \begin{pmatrix} 1 & 2 \\ 3 & 7 \end{pmatrix}

Form $[A | I]$ and reduce:

\begin{pmatrix} 1 & 2 & | & 1 & 0 \\ 3 & 7 & | & 0 & 1 \end{pmatrix}

\xrightarrow{R_2 - 3R_1} \begin{pmatrix} 1 & 2 & | & 1 & 0 \\ 0 & 1 & | & -3 & 1 \end{pmatrix}

\xrightarrow{R_1 - 2R_2} \begin{pmatrix} 1 & 0 & | & 7 & -2 \\ 0 & 1 & | & -3 & 1 \end{pmatrix}

Therefore:

A^{-1} = \begin{pmatrix} 7 & -2 \\ -3 & 1 \end{pmatrix}

Example 6.2: Non-Invertible Matrix

Try to find the inverse of:

B = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}

Form $[B | I]$ and reduce:

\begin{pmatrix} 1 & 2 & | & 1 & 0 \\ 2 & 4 & | & 0 & 1 \end{pmatrix} \xrightarrow{R_2 - 2R_1} \begin{pmatrix} 1 & 2 & | & 1 & 0 \\ 0 & 0 & | & -2 & 1 \end{pmatrix}

The left half cannot become $I$ (row of zeros). B is not invertible.

Remark 6.1: Verification

Always verify: if you found $A^{-1}$ , check that $AA^{-1} = I$ or $A^{-1}A = I$ . One equality implies the other for square matrices.

Example 6.3: 3×3 Inverse

Find the inverse of:

A = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 1 & 1 & 4 \end{pmatrix}

Form $[A | I]$ and reduce to RREF:

\begin{pmatrix} 1 & 0 & 2 & | & 1 & 0 & 0 \\ 0 & 1 & 1 & | & 0 & 1 & 0 \\ 1 & 1 & 4 & | & 0 & 0 & 1 \end{pmatrix}

\xrightarrow{R_3 - R_1} \begin{pmatrix} 1 & 0 & 2 & | & 1 & 0 & 0 \\ 0 & 1 & 1 & | & 0 & 1 & 0 \\ 0 & 1 & 2 & | & -1 & 0 & 1 \end{pmatrix}

\xrightarrow{R_3 - R_2} \begin{pmatrix} 1 & 0 & 2 & | & 1 & 0 & 0 \\ 0 & 1 & 1 & | & 0 & 1 & 0 \\ 0 & 0 & 1 & | & -1 & -1 & 1 \end{pmatrix}

\xrightarrow{R_1 - 2R_3, R_2 - R_3} \begin{pmatrix} 1 & 0 & 0 & | & 3 & 2 & -2 \\ 0 & 1 & 0 & | & 1 & 2 & -1 \\ 0 & 0 & 1 & | & -1 & -1 & 1 \end{pmatrix}

Therefore:

A^{-1} = \begin{pmatrix} 3 & 2 & -2 \\ 1 & 2 & -1 \\ -1 & -1 & 1 \end{pmatrix}

Theorem 6.1: Properties of Inverse

For invertible matrices $A$ and $B$ :

$(A^{-1})^{-1} = A$
$(AB)^{-1} = B^{-1}A^{-1}$ (order reverses!)
$(A^T)^{-1} = (A^{-1})^T$
$(cA)^{-1} = \frac{1}{c}A^{-1}$ for $c \neq 0$

Remark 6.2: Computational Considerations

For numerical applications, computing $A^{-1}$ explicitly is often avoided. Instead, systems $Ax = b$ are solved directly using LU decomposition, which is more numerically stable and efficient.

Remark 6.3: Inverse via Adjugate

For theoretical purposes, the inverse can also be computed via the adjugate matrix:

A^{-1} = \frac{1}{\det(A)} \text{adj}(A)

This is useful for proving theorems but inefficient computationally.

7. Worked Examples

Example 7.1: System with Unique Solution

Problem: Solve the system:

\begin{cases} x + y + z = 6 \\ 2x + y - z = 1 \\ x - y + 2z = 5 \end{cases}

Solution: Form augmented matrix and reduce:

\begin{pmatrix} 1 & 1 & 1 & | & 6 \\ 2 & 1 & -1 & | & 1 \\ 1 & -1 & 2 & | & 5 \end{pmatrix}

\xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 1 & 1 & | & 6 \\ 0 & -1 & -3 & | & -11 \\ 0 & -2 & 1 & | & -1 \end{pmatrix}

\xrightarrow{R_3 - 2R_2} \begin{pmatrix} 1 & 1 & 1 & | & 6 \\ 0 & -1 & -3 & | & -11 \\ 0 & 0 & 7 & | & 21 \end{pmatrix}

Back substitution:

$7z = 21 \Rightarrow z = 3$
$-y - 3(3) = -11 \Rightarrow y = 2$
$x + 2 + 3 = 6 \Rightarrow x = 1$

Answer: $(x, y, z) = (1, 2, 3)$

Example 7.2: System with Infinitely Many Solutions

Problem: Solve:

\begin{cases} x + 2y - z = 3 \\ 2x + 4y - 2z = 6 \\ x + 2y + z = 5 \end{cases}

Solution:

\begin{pmatrix} 1 & 2 & -1 & | & 3 \\ 2 & 4 & -2 & | & 6 \\ 1 & 2 & 1 & | & 5 \end{pmatrix}

\xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & -1 & | & 3 \\ 0 & 0 & 0 & | & 0 \\ 0 & 0 & 2 & | & 2 \end{pmatrix}

\xrightarrow{R_2 \leftrightarrow R_3, R_3 / 2} \begin{pmatrix} 1 & 2 & -1 & | & 3 \\ 0 & 0 & 1 & | & 1 \\ 0 & 0 & 0 & | & 0 \end{pmatrix}

\xrightarrow{R_1 + R_2} \begin{pmatrix} 1 & 2 & 0 & | & 4 \\ 0 & 0 & 1 & | & 1 \\ 0 & 0 & 0 & | & 0 \end{pmatrix}

Free variable: $y = t$ . Then $x = 4 - 2t$ , $z = 1$ .

Answer: $(x, y, z) = (4 - 2t, t, 1)$ for $t \in \mathbb{R}$

Example 7.3: Homogeneous System

Problem: Find all solutions to $Ax = 0$ where:

A = \begin{pmatrix} 1 & 2 & 1 \\ 2 & 4 & 3 \\ 3 & 6 & 4 \end{pmatrix}

Solution: Reduce $A$ to RREF:

\xrightarrow{\text{RREF}} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}

Pivot columns: 1 and 3. Free variable: $x_2 = t$ .

From RREF: $x_1 + 2x_2 = 0$ and $x_3 = 0$ .

So $x_1 = -2t$ , $x_2 = t$ , $x_3 = 0$ .

Null space basis: $\{(-2, 1, 0)\}$

Example 7.4: Finding Column Space Basis

Problem: Find a basis for the column space of:

A = \begin{pmatrix} 1 & 2 & 1 \\ 2 & 4 & 3 \\ 1 & 2 & 2 \end{pmatrix}

Solution: The RREF is:

\begin{pmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix}

Pivot columns are 1 and 3. Take the original columns 1 and 3:

Basis: $\left\{ \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 3 \\ 2 \end{pmatrix} \right\}$

Example 7.5: 3×3 System with No Solution

Problem: Solve:

\begin{cases} x + y + z = 1 \\ x + y + z = 2 \\ x + 2y + 3z = 4 \end{cases}

Solution:

\begin{pmatrix} 1 & 1 & 1 & | & 1 \\ 1 & 1 & 1 & | & 2 \\ 1 & 2 & 3 & | & 4 \end{pmatrix} \xrightarrow{R_2 - R_1, R_3 - R_1} \begin{pmatrix} 1 & 1 & 1 & | & 1 \\ 0 & 0 & 0 & | & 1 \\ 0 & 1 & 2 & | & 3 \end{pmatrix}

Row 2 is $[0, 0, 0 | 1]$ , which is inconsistent.

No solution exists.

Example 7.6: Row Space Basis

Problem: Find a basis for the row space of:

A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}

Solution: Reduce to REF:

\xrightarrow{\text{REF}} \begin{pmatrix} 1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 0 \end{pmatrix}

The non-zero rows of the REF form a basis for the row space:

Basis: $\{(1, 2, 3), (0, -3, -6)\}$ or equivalently $\{(1, 2, 3), (0, 1, 2)\}$

Example 7.7: Rank from Determinant

Problem: What can you say about the rank of:

A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}

Solution: Note that Row 3 = 2(Row 2) − Row 1.

So the rows are linearly dependent, meaning rank < 3.

By REF, we found 2 non-zero rows, so $\text{rank}(A) = 2$ .

This also means $\det(A) = 0$ (singular matrix).

Example 7.8: Full Rank Matrix

Problem: Show that the matrix is full rank:

A = \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 5 & 6 & 0 \end{pmatrix}

Solution: Reduce to REF:

\xrightarrow{R_3 - 5R_1} \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 0 & -4 & -15 \end{pmatrix} \xrightarrow{R_3 + 4R_2} \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 0 & 0 & 1 \end{pmatrix}

3 pivots in a 3×3 matrix means $\text{rank}(A) = 3$ (full rank).

Therefore $A$ is invertible.

Example 7.9: Two Free Variables

Problem: Find all solutions to:

\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}

Solution: Reduce to RREF:

\xrightarrow{R_2 - R_1} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}

Pivot columns: 1 and 3. Free variables: $x_2 = s$ , $x_4 = t$ .

From row 2: $x_3 = -2t$ . From row 1: $x_1 = -s - x_3 - t = -s + 2t - t = -s + t$ .

Solution:

\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = s \begin{pmatrix} -1 \\ 1 \\ 0 \\ 0 \end{pmatrix} + t \begin{pmatrix} 1 \\ 0 \\ -2 \\ 1 \end{pmatrix}

Example 7.10: Checking Linear Independence

Problem: Are the vectors $v_1 = (1, 2, 3)$ , $v_2 = (4, 5, 6)$ , $v_3 = (7, 8, 9)$ linearly independent?

Solution: Form matrix with vectors as columns and find rank:

\begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{pmatrix} \xrightarrow{\text{RREF}} \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}

Rank = 2 < 3, so the vectors are linearly dependent.

From RREF: $v_3 = -v_1 + 2v_2$ .

8. Common Mistakes

Mistake 1: Forgetting to apply operations to the augmented column

When solving $Ax = b$ , every row operation on $[A|b]$ must also be applied to the $b$ column. Forgetting this gives wrong solutions.

Mistake 2: Using RREF columns as the column space basis

The column space basis comes from the original matrix's pivot columns, not the RREF's columns (which are just standard basis vectors).

Mistake 3: Scaling a row by zero

Multiplying a row by zero is NOT a valid ERO—it's not reversible and destroys information. The scalar must be non-zero.

Mistake 4: Confusing REF with RREF

REF only requires zeros below pivots. RREF additionally requires pivots = 1 and zeros both above AND below each pivot.

Mistake 5: Concluding "no solution" from a zero row

A row of zeros [0 0 ... 0 | 0] is fine—it just means a dependent equation. Only [0 0 ... 0 | c] with $c \neq 0$ indicates no solution.

Mistake 6: Arithmetic errors in elimination

Double-check each row operation carefully. A single arithmetic error propagates through all subsequent steps. Consider verifying by substituting solutions back into original equations.

Mistake 7: Incorrect back-substitution order

In back-substitution, work from bottom to top. Solve for the last basic variable first, then substitute upward. Working in the wrong order leads to errors.

9. Key Takeaways

Three EROs

Swap rows, scale by non-zero constant, add multiple of one row to another. These preserve solution sets and are all reversible.

REF vs RREF

REF: zeros below pivots, staircase pattern. RREF: also pivots = 1 and zeros above pivots. RREF is unique; REF is not.

Rank

Number of pivots = rank = dimension of column space = number of basic variables. Free variables = n − rank = dimension of null space.

Solution Types

No solution: inconsistent row [0...0|c]. Unique: all columns are pivot columns. Infinitely many: consistent with free variables.

Inverses

Reduce [A|I] to RREF. If left half becomes I, right half is A⁻¹. If left half has zero row, A is not invertible.

Null Space Basis

From RREF: for each free variable, set it to 1 (others to 0) and solve for basic variables. These vectors form a null space basis.

Column Space Basis

The pivot columns of the ORIGINAL matrix (not RREF) form a basis for the column space. RREF identifies which columns to take.

Applications

Gaussian elimination is used everywhere: solving circuits, balancing chemical equations, computer graphics, machine learning, and cryptography.

Summary Table

To Find...	Method
Solution to Ax = b	Reduce [A\|b] to RREF, read off solution
Rank of A	Count pivots in REF/RREF
Null space basis	RREF of A, solve for free variables
Column space basis	Pivot columns of original A
Row space basis	Non-zero rows of REF
Inverse of A	Reduce [A\|I] to RREF

Gaussian Elimination Practice

Questions

Correct

Accuracy

Which is NOT an elementary row operation?

Easy

Not attempted

Which matrix is in row echelon form?

Easy

Not attempted

How many solutions does

\begin{pmatrix} 1 & 0 & | & 2 \\ 0 & 0 & | & 1 \end{pmatrix}

have?

Medium

Not attempted

What is the rank of a

3 \times 4

matrix with RREF

\begin{pmatrix} 1 & 0 & 2 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}

Medium

Not attempted

In the RREF

\begin{pmatrix} 1 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}

, which variable is free?

Medium

Not attempted

A

m \times n

with rank

r

, how many free variables does

Ax = 0

have?

Hard

Not attempted

Which system has infinitely many solutions?

Hard

Not attempted

What is the maximum rank of a

4 \times 3

matrix?

Easy

Not attempted

After reducing

[A | I]

to RREF, what does the right half give you?

Medium

Not attempted

Which operation does NOT preserve the determinant's value?

Hard

Not attempted

5 \times 5

matrix has rank 3. How many free variables does

Ax = 0

have?

Medium

Not attempted

What is the computational complexity of Gaussian elimination on an

n \times n

matrix?

Hard

Not attempted

Frequently Asked Questions

What's the difference between REF and RREF?

In REF, pivots are 'leading entries' with zeros below them, and each pivot is to the right of pivots above. RREF additionally requires: (1) all pivots are 1, and (2) each pivot is the only non-zero entry in its column.

Why is Gaussian elimination useful beyond solving equations?

It determines matrix rank, finds bases for column/null spaces, computes determinants (via REF), tests linear independence, and underlies the LU decomposition used in numerical computing.

Is RREF unique?

Yes! Every matrix has a unique RREF. Different sequences of row operations may be used, but the final RREF is always the same. REF is not unique—different choices of pivots give different REFs.

How do I know if a system is consistent?

A system Ax = b is consistent iff b is in the column space of A, which happens iff the augmented matrix [A|b] and A have the same rank. Equivalently, no row in the RREF of [A|b] has the form [0 0 ... 0 | c] with c ≠ 0.

What's the computational complexity of Gaussian elimination?

For an n×n matrix, Gaussian elimination requires O(n³) arithmetic operations. This makes it efficient for moderate-sized systems but expensive for very large matrices, where iterative methods may be preferred.

What is partial pivoting and why is it important?

Partial pivoting means selecting the largest (in absolute value) entry in the current column as the pivot. This improves numerical stability by reducing rounding errors. Without pivoting, small pivots can lead to catastrophic error amplification in floating-point arithmetic.

Can I use Gaussian elimination over any field?

Yes! Gaussian elimination works over any field (ℚ, ℝ, ℂ, finite fields, etc.). The algorithm only uses field operations: addition, subtraction, multiplication, and division by non-zero elements.

What's the relationship between Gaussian elimination and LU decomposition?

LU decomposition records the steps of Gaussian elimination. The matrix L contains the multipliers used during elimination, while U is the resulting row echelon form. We have A = LU, which allows efficient solving of multiple systems with the same coefficient matrix.

How do I find a basis for the null space using RREF?

From the RREF: (1) identify free variables (non-pivot columns), (2) set each free variable to 1 (others to 0) one at a time, (3) solve for basic variables. Each such vector is a basis element of the null space.

Why is the RREF unique but REF is not?

REF allows any non-zero pivot values and doesn't require elimination above pivots. Different row operation sequences can yield different REFs. RREF's strict requirements (pivots = 1, only entry in column) force a unique result.