Gaussian Elimination

You have been solving systems of equations by substitution and elimination since algebra class. These methods work, but they require you to make choices at each step: which variable to eliminate first, which equation to substitute into which. For small systems, this is fine. But what happens when you have five equations? Ten? A thousand? You need a method that removes all guesswork, a mechanical procedure that always works regardless of the system’s size.

Gaussian elimination is that method. Named after the legendary mathematician Carl Friedrich Gauss (though versions of it were known in ancient China), this algorithm systematically transforms any system of linear equations into a form where the solution becomes obvious. It is the workhorse of computational linear algebra, running millions of times per second in engineering simulations, economic models, and machine learning applications around the world.

The beauty of Gaussian elimination lies in its simplicity. You are allowed exactly three types of operations on the rows of a matrix, and by applying them strategically, you can reduce any system to one that is trivial to solve. In this lesson, you will learn these operations, understand the forms they produce, and develop the ability to solve any linear system you encounter.

Core Concepts

The Three Row Operations

The foundation of Gaussian elimination rests on three simple operations that you can perform on the rows of an augmented matrix. These operations are called elementary row operations, and they have a crucial property: they never change the solution set of the system. Applying any sequence of row operations gives you an equivalent system with exactly the same solutions as the original.

Here are the three row operations:

1. Row Swap: Interchange two rows.

Notation: $R_i \leftrightarrow R_j$ (swap row $i$ and row $j$)

Example: $$\left[\begin{array}{cc|c} 0 & 1 & 3 \ 2 & 4 & 6 \end{array}\right] \xrightarrow{R_1 \leftrightarrow R_2} \left[\begin{array}{cc|c} 2 & 4 & 6 \ 0 & 1 & 3 \end{array}\right]$$

Why is this valid? Swapping equations does not change what the system is asking. The system $x + y = 5$, $x - y = 1$ has exactly the same solutions as $x - y = 1$, $x + y = 5$. You have just listed the equations in a different order.

2. Row Scaling: Multiply a row by a nonzero constant.

Notation: $R_i \to c \cdot R_i$ (multiply row $i$ by $c$, where $c \neq 0$)

Example: $$\left[\begin{array}{cc|c} 2 & 4 & 6 \ 1 & 3 & 5 \end{array}\right] \xrightarrow{R_1 \to \frac{1}{2}R_1} \left[\begin{array}{cc|c} 1 & 2 & 3 \ 1 & 3 & 5 \end{array}\right]$$

Why is this valid? Multiplying both sides of an equation by the same nonzero number preserves the solution. The equation $2x + 4y = 6$ has exactly the same solutions as $x + 2y = 3$. You can always undo this operation by multiplying by the reciprocal.

3. Row Replacement: Add a multiple of one row to another row.

Notation: $R_i \to R_i + c \cdot R_j$ (add $c$ times row $j$ to row $i$)

Example: $$\left[\begin{array}{cc|c} 1 & 2 & 3 \ 1 & 3 & 5 \end{array}\right] \xrightarrow{R_2 \to R_2 - R_1} \left[\begin{array}{cc|c} 1 & 2 & 3 \ 0 & 1 & 2 \end{array}\right]$$

Why is this valid? Adding equal quantities to both sides of an equation preserves solutions. If we know that $x + 2y = 3$, then subtracting this equation from $x + 3y = 5$ gives $(x + 3y) - (x + 2y) = 5 - 3$, which simplifies to $y = 2$. The new equation $y = 2$ combined with the original $x + 2y = 3$ has exactly the same solutions as the original system.

These three operations are your only tools, but they are remarkably powerful. With just these three, you can solve any system of linear equations.

Pivots and the Goal of Elimination

When performing Gaussian elimination, we focus on pivots. A pivot is the first nonzero entry in a row (reading from left to right) after the matrix has been partially reduced. The pivot position tells us which variable that row will determine.

The goal of Gaussian elimination is to create a “staircase pattern” of pivots, where each pivot is:

1. To the right of the pivot in the row above it
2. The only nonzero entry in its column (in reduced form)

By creating this staircase, we systematically isolate each variable, making the system easy to solve.

Row Echelon Form (REF)

A matrix is in row echelon form (REF) if it satisfies these conditions:

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

Here is an example of a matrix in REF:

$$\left[\begin{array}{ccc|c} \boxed{2} & 3 & 1 & 5 \ 0 & \boxed{4} & -1 & 3 \ 0 & 0 & \boxed{1} & 2 \end{array}\right]$$

The boxed entries are the pivots. Notice the staircase pattern: each pivot is strictly to the right of and below the previous one. The entries below each pivot are all zero.

Here is another valid REF (pivots do not have to be in consecutive columns):

$$\left[\begin{array}{cccc|c} \boxed{1} & 2 & 0 & 3 & 4 \ 0 & 0 & \boxed{5} & 1 & 2 \ 0 & 0 & 0 & 0 & 0 \end{array}\right]$$

In REF, the system becomes easy to solve using back-substitution (which we will discuss shortly). The last non-zero row gives you one variable directly, and you work your way up, substituting known values to find the others.

Reduced Row Echelon Form (RREF)

A matrix is in reduced row echelon form (RREF) if it satisfies all the conditions for REF, plus:

4. Each pivot is equal to 1
5. Each pivot is the only nonzero entry in its column (all entries above a pivot are also zero)

Here is the same system from before, now in RREF:

$$\left[\begin{array}{ccc|c} \boxed{1} & 0 & 0 & 1 \ 0 & \boxed{1} & 0 & 2 \ 0 & 0 & \boxed{1} & 2 \end{array}\right]$$

In RREF, the solution is immediate: $x = 1$, $y = 2$, $z = 2$. No back-substitution is needed because each row has exactly one variable with a coefficient of 1, and that variable appears nowhere else.

RREF is unique: every matrix has exactly one RREF, regardless of which sequence of row operations you use to reach it. REF is not unique; different sequences of operations can produce different REF matrices. But all paths lead to the same RREF.

The Gaussian Elimination Algorithm

Here is the systematic procedure for reducing a matrix to REF:

Forward Elimination (producing REF):

1. Start with the leftmost column that has a nonzero entry. This is the pivot column.

2. If necessary, swap rows to move a nonzero entry to the top position of the pivot column. This entry becomes the pivot.

3. Use row replacement operations to create zeros in all positions below the pivot. For each row below the pivot row, add an appropriate multiple of the pivot row to eliminate the entry in the pivot column.

4. Ignore the row you just processed and repeat steps 1-3 on the remaining submatrix (the rows below and columns to the right).

5. Continue until you have processed all rows or all columns.

Gauss-Jordan Elimination (producing RREF):

To continue from REF to RREF, add these steps:

6. Back-elimination: Starting from the rightmost pivot and working left, use row replacement to create zeros above each pivot.

7. Scaling: Divide each row by its pivot to make all pivots equal to 1.

(Steps 6 and 7 can be done in either order, though it is often easier to scale first.)

Back-Substitution

If you stop at REF instead of going all the way to RREF, you solve the system using back-substitution. Here is how it works:

Starting from the bottom non-zero row and working upward:

1. The bottom row has an equation in one variable (or reveals the system has no solution). Solve for that variable.
2. Substitute the known value into the row above and solve for the next variable.
3. Continue working upward until all variables are determined.

For example, if your REF is:

$$\left[\begin{array}{ccc|c} 1 & 2 & 1 & 6 \ 0 & 1 & -1 & 1 \ 0 & 0 & 2 & 4 \end{array}\right]$$

Step 1: From row 3: $2z = 4$, so $z = 2$

Step 2: From row 2: $y - z = 1$, so $y - 2 = 1$, giving $y = 3$

Step 3: From row 1: $x + 2y + z = 6$, so $x + 2(3) + 2 = 6$, giving $x = -2$

Back-substitution is often faster than continuing to RREF, especially for hand calculations. However, RREF has advantages when you need to analyze the solution structure or when using a computer.

Detecting Special Cases

Not every system has a unique solution. Gaussian elimination naturally reveals when a system has no solution or infinitely many solutions.

No Solution (Inconsistent System):

During elimination, you discover the system has no solution when you encounter a row of the form:

$$\left[\begin{array}{ccc|c} 0 & 0 & \cdots & 0 & b \end{array}\right] \quad \text{where } b \neq 0$$

This row says $0 = b$ (where $b$ is nonzero), which is impossible. The system is inconsistent.

For example:

$$\left[\begin{array}{cc|c} 1 & 2 & 3 \ 0 & 0 & 5 \end{array}\right]$$

The second row says $0x + 0y = 5$, which simplifies to $0 = 5$. This is false, so there is no solution.

Infinitely Many Solutions:

When you complete the elimination and every non-zero row corresponds to a valid equation (no $0 = \text{nonzero}$), but you have fewer pivots than variables, the system has infinitely many solutions.

The variables corresponding to pivot columns are called basic variables (or pivot variables). The remaining variables are called free variables. You can set free variables to any values and then solve for the basic variables.

For example, if the RREF is:

$$\left[\begin{array}{ccc|c} 1 & 2 & 0 & 3 \ 0 & 0 & 1 & 2 \end{array}\right]$$

This has two pivots (in columns 1 and 3) but three variables ($x_1$, $x_2$, $x_3$). Variable $x_2$ has no pivot in its column, so it is free.

The equations are $x_1 + 2x_2 = 3$ and $x_3 = 2$.

Setting $x_2 = t$ (a free parameter), we get:

• $x_1 = 3 - 2t$
• $x_2 = t$
• $x_3 = 2$

This describes infinitely many solutions, one for each value of $t$.

Parametric Solutions

When a system has infinitely many solutions, we express the answer in parametric form. Each free variable becomes a parameter, and we express the basic variables in terms of these parameters.

The general solution can be written as a vector:

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

This elegant form shows that the solution set is a line in three-dimensional space: a particular solution $(3, 0, 2)$ plus any multiple of the direction vector $(-2, 1, 0)$.

For systems with two free variables, you would have two parameters and the solution set would be a plane. The number of free variables equals the number of parameters equals the “dimension” of the solution set.

Counting Solutions

Here is a summary of how to determine the number of solutions from the RREF:

Situation	Number of Solutions
Row of form $[0 \cdots 0 | b]$ with $b \neq 0$	None (inconsistent)
No such row, and every variable is basic (has a pivot)	Exactly one
No such row, and some variables are free	Infinitely many

The number of free variables tells you how many parameters you need to describe the solution set.

Notation and Terminology

Term	Meaning	Example
Row operation	Legal transformation of augmented matrix	$R_2 \to R_2 - 2R_1$
Pivot	Leading nonzero entry in a row (after reduction)	The 1 in $[0\ 1\ 3]$
REF	Row echelon form (staircase of pivots, zeros below)
RREF	Reduced REF (pivots are 1, only nonzero in column)
Basic variable	Variable corresponding to a pivot column
Free variable	Variable with no pivot in its column
Back-substitution	Solving from bottom row upward after REF
Consistent	System has at least one solution
Inconsistent	System has no solution (contradiction found)

Examples

Key Properties and Rules

Properties of Row Operations

Each elementary row operation is reversible:

• Swap $R_i \leftrightarrow R_j$ is undone by swapping them back
• Scaling $R_i \to cR_i$ is undone by $R_i \to \frac{1}{c}R_i$
• Replacement $R_i \to R_i + cR_j$ is undone by $R_i \to R_i - cR_j$

Because each operation is reversible, row-equivalent matrices represent equivalent systems with identical solution sets.

Uniqueness of RREF

Every matrix has exactly one RREF. Different sequences of row operations may take different paths, but they all arrive at the same destination. This makes RREF particularly useful for theoretical analysis.

Determining Solution Type from RREF

For a system with $n$ variables:

Number of Pivots	Consistency	Number of Free Variables	Solutions
$n$	Consistent	0	Exactly one
$< n$	Consistent	$n - \text{pivots}$	Infinitely many
Any	Inconsistent (row $[0 \cdots 0 | b]$, $b \neq 0$)	N/A	None

The Rank of a Matrix

The number of pivots in the RREF of a matrix is called the rank of the matrix. The rank tells you:

• For an $m \times n$ coefficient matrix: the number of “independent” equations
• The number of basic variables in the solution
• The dimension of the column space (a concept you will explore later)

Real-World Applications

Solving Traffic Flow Networks

City planners model traffic flow through intersections using systems of linear equations. At each intersection, the total flow in must equal the total flow out (conservation of flow). For a network with dozens of intersections, this creates a large system of equations.

Gaussian elimination reveals whether the traffic flow pattern is determined uniquely, or whether there are free variables representing flows that can be adjusted. These free variables correspond to routes where traffic can be redirected without affecting the overall pattern.

Balancing Chemical Equations Systematically

Consider balancing a complex chemical reaction like:

$$a\text{C}_2\text{H}_6 + b\text{O}_2 \to c\text{CO}_2 + d\text{H}_2\text{O}$$

Setting up conservation equations for each element:

• Carbon: $2a = c$
• Hydrogen: $6a = 2d$
• Oxygen: $2b = 2c + d$

This is a homogeneous system (right-hand sides are zero when rearranged). Gaussian elimination finds that one variable is free, which is expected since we can multiply all coefficients by any constant. Setting $a = 1$ and solving gives the balanced equation.

For reactions with many compounds, hand-balancing becomes nearly impossible. Gaussian elimination provides a systematic approach that always works.

Finding Equilibrium in Economics

In economic models, markets reach equilibrium when supply equals demand across all goods. With multiple interconnected markets (where the price of one good affects demand for others), equilibrium is found by solving a system of linear equations.

The Leontief input-output model, which won Wassily Leontief the Nobel Prize in Economics, uses matrices to model entire economies. The question “how much should each industry produce to meet final demand?” translates directly to solving $A\vec{x} = \vec{b}$ using Gaussian elimination.

Computer Algorithms for Large Systems

Modern applications routinely involve systems with thousands or millions of equations. Computer implementations of Gaussian elimination (with numerical refinements to handle rounding errors) form the backbone of:

• Finite element analysis in engineering (simulating stress, heat flow, fluid dynamics)
• Machine learning (solving least-squares problems for regression)
• Computer graphics (solving systems for lighting, physics simulations)
• Cryptography and coding theory

The basic algorithm you learned in this lesson scales to these massive applications. Computers can perform billions of row operations per second, but the underlying logic is exactly what you have been doing by hand.

Self-Test Problems

Summary

• Elementary row operations are the three building blocks of Gaussian elimination: row swaps, row scaling (by a nonzero constant), and row replacement (adding a multiple of one row to another). These operations preserve the solution set.

• Row echelon form (REF) has a staircase pattern of pivots with zeros below each pivot. Systems in REF are solved using back-substitution.

• Reduced row echelon form (RREF) additionally requires all pivots to be 1 and the only nonzero entry in their column. The solution reads directly from RREF.

• Gaussian elimination is the algorithm that systematically applies row operations to transform any augmented matrix into REF (forward elimination) or RREF (Gauss-Jordan elimination).

• A system is inconsistent (no solution) if elimination produces a row of the form $[0\ 0\ \cdots\ 0\ |\ b]$ where $b \neq 0$.

• A consistent system has infinitely many solutions when there are more variables than pivots. Variables without pivots are free variables.

• Parametric solutions express basic variables in terms of free variables (parameters). The number of free variables equals the dimension of the solution set.

• Every matrix has a unique RREF, making it a standard form for analyzing systems.

• Gaussian elimination is fundamental to modern computing, used in engineering simulations, machine learning, economics, and countless other applications where systems of equations arise.