BrevFeed
Sign in

2. Systems of linear equations, Gaussian elimination, row-echelon form (RREF)

📖 Reading · 12 min
💡 Every code box below is live — edit it and hit Run.

§16.0 ended with a question — find scalars making a linear combination hit a target vector — that we solved by inspection. Most systems aren't that convenient. This lesson develops Gaussian elimination, a completely mechanical procedure that solves any system of linear equations, however large, and along the way reveals whether a solution exists at all and whether it's unique.

What a linear system is

A linear equation in variables x_1,\dots,x_n has the form a_1x_1+a_2x_2+\cdots+a_nx_n=b — every variable appears to the first power, with no products of variables and no x_i inside a function like \sin or \sqrt{\ }. A system of m linear equations in n unknowns is m such equations considered together:

\begin{aligned} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=b_1\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n&=b_2\\ &\ \vdots\\ a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=b_m \end{aligned}

A solution is an assignment of values to x_1,\dots,x_n satisfying every equation simultaneously. Geometrically, each equation in \mathbb{R}^2 is a line, in \mathbb{R}^3 a plane, and in general a hyperplane; a solution is a point lying on all of them at once — their intersection.

Every linear system has exactly one of three outcomes:

  • A unique solution — the hyperplanes meet at exactly one point.
  • No solution — the system is inconsistent (e.g. two parallel, non-coincident lines in \mathbb{R}^2).
  • Infinitely many solutions — the hyperplanes overlap along a whole line, plane, or higher-dimensional set.

There is no fourth option, and no case of "exactly two" or "exactly seventeen" solutions — a fact that becomes obvious once §16.2 restates solving a system as intersecting flat objects, and one Gaussian elimination itself makes visible by the shape of its output.

The augmented matrix

Solving by hand is dramatically less error-prone once the variable names are dropped — they never change and carry no information, only the coefficients do. The augmented matrix keeps just the numbers, one row per equation, with the right-hand sides attached as a final column (traditionally separated by a bar):

\left[\begin{array}{ccc|c}a_{11}&a_{12}&a_{13}&b_1\\a_{21}&a_{22}&a_{23}&b_2\\a_{31}&a_{32}&a_{33}&b_3\end{array}\right]

Every operation below is performed on this array of numbers; translating back to equations only happens at the very end.

Elementary row operations

Three operations transform a system into an equivalent one — same solution set, different-looking equations — because each is something valid to do to a true equation:

  1. Swap two rows (reorder the equations — doesn't change what makes them all true).
  2. Scale a row by a nonzero constant (multiply both sides of one equation by the same nonzero number).
  3. Add a multiple of one row to another (add a multiple of one true equation to another true equation — still true).

These are called elementary row operations, and because each is reversible (undo a swap with the same swap; undo scaling by c by scaling by 1/c; undo adding c\timesrow j by subtracting it back out), applying them never changes the solution set — only how it's written. §16.5 revisits these three operations as matrices in their own right.

Gaussian elimination

The algorithm: use row operations to drive the augmented matrix into row-echelon form (REF) — a staircase pattern where each row's first nonzero entry (its pivot) sits strictly to the right of the pivot in the row above, and every entry below a pivot is zero.

Forward elimination, column by column, left to right:

  1. Find a nonzero entry in the current column (swap rows if the top one is zero) — this becomes the pivot.
  2. Use "add a multiple of the pivot row" to zero out every entry below the pivot in that column.
  3. Move to the next column and next row, repeat.

Once in echelon form, back-substitution solves from the bottom row up: the last nonzero row involves the fewest variables, so solve it first, substitute that value into the row above, and so on.

Reduced row-echelon form (RREF) goes one step further: scale each pivot to exactly 1, and eliminate entries above each pivot too, not just below. RREF is unique for a given matrix (unlike REF, which depends on the operations chosen) — every valid elimination path arrives at the same RREF — and it's convenient enough that it's what software actually computes.

Reading off the outcome from RREF:

  • A row of the form [0\ 0\ \cdots\ 0\mid c] with c\neq0 means 0=c — no solution, the system is inconsistent, full stop.
  • Otherwise, if every column has a pivot, the solution is unique — read each variable's value directly off its pivot row.
  • Otherwise (fewer pivots than columns, no contradiction row), there are free variables — columns with no pivot — and infinitely many solutions, parametrized by those free variables.

Doing it in Python

import sympy as sp

# x + y + z = 6, 2y + 5z = -4, 2x + 5y - z = 27
A = sp.Matrix([
    [1, 1, 1, 6],
    [0, 2, 5, -4],
    [2, 5, -1, 27],
])

rref, pivots = A.rref()
print("RREF:")
for row in rref.tolist():
    print(row)
print("pivot columns:", pivots)

RREF:
[1, 0, 0, 5]
[0, 1, 0, 3]
[0, 0, 1, -2]
pivot columns: (0, 1, 2)

A system with a free variable — infinitely many solutions:

import sympy as sp

# x + 2y - z = 3, 2x + 4y - 2z = 6  (second equation is 2x the first)
A = sp.Matrix([
    [1, 2, -1, 3],
    [2, 4, -2, 6],
])

rref, pivots = A.rref()
print("RREF:")
for row in rref.tolist():
    print(row)
print("pivot columns:", pivots)
print("free columns:", [c for c in range(A.cols - 1) if c not in pivots])

RREF:
[1, 2, -1, 3]
[0, 0, 0, 0]
pivot columns: (0,)
free columns: [1, 2]

Worked example

Solve by Gaussian elimination:

\begin{aligned}x+y+z&=6\\2y+5z&=-4\\2x+5y-z&=27\end{aligned}

Augmented matrix:

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

R_3\leftarrow R_3-2R_1:

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

R_3\leftarrow R_3-\frac32R_2:

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

This is row-echelon form: pivots in every column, staircase pattern. Back-substitute. Row 3: -\frac{21}2z=21\Rightarrow z=-2. Row 2: 2y+5(-2)=-4\Rightarrow2y=6\Rightarrow y=3. Row 1: x+3+(-2)=6\Rightarrow x=5.

\boxed{x=5,\ y=3,\ z=-2}

Sanity check. 2(3)+5(-2)=6-10=-4 ✓, and 2(5)+5(3)-(-2)=10+15+2=27 ✓ — matching the RREF computed in Python above, whose last column reads off the same solution directly. ✓

Your turn

1. Solve \begin{aligned}x+2y&=5\\3x-y&=1\end{aligned} by elimination.

2. What does it mean, in terms of row operations, if elimination produces a row [0\ 0\ 0\mid 4]?

3. True or false: a system with more equations than unknowns can never have a solution.

Solutions

1. R_2\leftarrow R_2-3R_1: 3x-y-3(x+2y)=1-3(5)\Rightarrow -7y=-14\Rightarrow y=2. Back into row 1: x+4=5\Rightarrow x=1. \boxed{x=1,\ y=2}. Check: 3(1)-2=1 ✓.

2. It means the system reduced to the equation 0=4, a flat contradiction — no assignment of the variables can make it true, so the whole system is inconsistent and has no solution. Every row operation used to get there was reversible, so this isn't an artifact of the method: the original system genuinely had no solution.

3. False. More equations than unknowns (an "overdetermined" system) usually has no solution, but not always — if one equation happens to be a combination of the others (e.g. one row is exactly the sum of two other rows), it adds no new constraint, and the system can still be consistent, even with a unique or infinite solution set. Count of equations alone never decides the outcome; only elimination (or, as §17.5 makes precise, rank) does.

Check yourself in code

Solve \begin{aligned}x+2y-z&=3\\2x-y+3z&=-9\\-x+3y-2z&=8\end{aligned} via RREF, printing the RREF and then the solution.

Print exactly this:

RREF:
[1, 0, 0, -1]
[0, 1, 0, 1]
[0, 0, 1, -2]
x=-1, y=1, z=-2

import sympy as sp

A = sp.Matrix([
    [1, 2, -1, 3],
    [2, -1, 3, -9],
    [-1, 3, -2, 8],
])

rref, pivots = A.rref()
print("RREF:")
for row in rref.tolist():
    print(row)
# print("x=..., y=..., z=...") reading the last column off rref

import sympy as sp

A = sp.Matrix([
    [1, 2, -1, 3],
    [2, -1, 3, -9],
    [-1, 3, -2, 8],
])

rref, pivots = A.rref()
print("RREF:")
for row in rref.tolist():
    print(row)

x, y, z = (rref[i, 3] for i in range(3))
print(f"x={x}, y={y}, z={z}")

Gaussian elimination reduces any system's augmented matrix to row-echelon form using three reversible row operations, and RREF makes the outcome — unique solution, no solution, or infinitely many, governed by pivots versus free columns — readable directly. It's the mechanical backbone every later technique in this course reduces to: invertibility, rank, and eigenvectors all end up asking "solve this system" underneath.

Next: matrices themselves as objects, with their own arithmetic — starting with exactly the coefficient array elimination has been operating on all along.

← Previous Next →