[Linear Algebra Series Part 10] Gaussian Elimination: A Procedure for Solving and Reading Structure

What this post covers

This post introduces Gaussian elimination.

• Why systems of equations are simplified using row operations
• The three elementary row operations
• Why row echelon form makes solution structure easier to read
• How this prepares us for pivots, free variables, and rank

Key terms

• system of equations: several equations solved together
• augmented matrix: a matrix that records both coefficients and outputs together; the vertical bar separates coefficients from the right-hand side
• pivot: the first nonzero entry in a nonzero row of echelon form

Core idea

Once you understand Ax = b, the next question is how to actually solve or analyze it. The standard tool is Gaussian elimination.

The goal is not to perform random manipulations. The goal is to turn a complicated system into a simpler one with the same solution set.

To do that, we use elementary row operations:

1. swap two rows
2. multiply a row by a nonzero scalar
3. add a multiple of one row to another row

These operations change how the equations are written, but they preserve the solution set. That is why they are legal moves.

Step-by-step examples

Example 1) Build an augmented matrix

Start with

x + y = 4
2x + 3y = 9

Its augmented matrix is

[1 1 | 4]
[2 3 | 9]

This lets us work structurally rather than line by line. The vertical bar | separates the coefficient matrix from the output vector.

Example 2) Eliminate below the pivot

Use the first row to remove the first entry of the second row:

R2 <- R2 - 2R1

This notation means “replace row 2 with row 2 minus 2 times row 1.”

Then we get

[1 1 | 4]
[0 1 | 1]

A matrix is in row echelon form when zero rows are at the bottom and each pivot is to the right of the pivot above it. This is now in row echelon form. The second row says y = 1, and back-substitution gives

x + 1 = 4
x = 3

The point is not only that we found the answer. We also exposed the structure more clearly.

Example 3) The signal for no solution

If elimination produces a row like

[0 0 | 1]

that means

0 = 1

which is impossible. So the system has no solution.

By contrast,

[0 0 | 0]

adds no new constraint. This row is redundant by itself; if there are more variables than pivots, a free variable may remain.

Example 4) Why pivots matter

In row echelon form, the first nonzero entry in each nonzero row is a pivot. For example,

[1 1 | 4]
[0 1 | 1]

has pivots in the first and second columns.

Pivot columns correspond to leading variables, while non-pivot columns correspond to free variables. More pivots mean fewer free variables and therefore a smaller solution space.

Math notes

• Gaussian elimination is a way to reveal structure while preserving the solution set of the system.
• Row operations preserve the solution set of the augmented system and the row space, but they generally change the column space.
• Row echelon form places zero rows at the bottom and moves pivots to the right as you go down the rows.
• Reduced row echelon form is a stronger refinement: pivots become 1 and everything above them becomes 0.

In numerical computation, pivot choice also matters. If the next candidate pivot entry is zero or extremely small, practical algorithms often swap rows and use partial pivoting for better numerical stability.

Common mistakes

Treating elimination as only a calculation trick

It is also a structural reading tool. The real gain is not just the final numbers, but what the transformed system reveals.

Confusing row operations with column operations

For solving systems, row operations are the natural structure-preserving moves. Column operations change the problem in a different way.

Ignoring numerical stability

The conceptual version is clean, but real implementations must care about pivoting and small numbers.

Thinking echelon form is the end of the story

Echelon form is often the right middle step. In some cases, reduced row echelon form gives an even clearer final picture.

Practice or extension

1. Turn x + 2y = 5, 3x + 4y = 11 into an augmented matrix and eliminate.
2. Try a 3-variable example and identify the pivots.
3. Construct a system that produces [0 0 | 1] after elimination.
4. Explain what [0 0 | 0] tells you that [0 0 | 1] does not.

Wrap-up

This post introduced Gaussian elimination.

• Row operations simplify a system without changing its solution set.
• Augmented matrices make the structure easier to handle.
• Pivots reveal independent constraints.
• Contradictory rows signal no solution, while zero rows often hint at remaining freedom.

Next, we will use these ideas to classify when a system has one solution, no solution, or infinitely many solutions.