Gaussian Elimination and Solution Structure, precalculus lesson

Solving three equations in three unknowns by substitution gets messy fast, and one lost minus sign ruins the answer. Elimination done in a fixed order on a table of numbers is calm and mechanical. Better still, the finished table tells you whether the system has exactly one solution, no solution at all, or infinitely many. Software that solves large systems runs on the same idea.

Key terms

Augmented matrix

Definition Consider a system of $m$ linear equations in the variables $x_1, \ldots, x_n$ , where equation $i$ reads $a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n = b_i$ . Its coefficient matrix is the $m \times n$ matrix $A = [a_{ij}]$ . Its augmented matrix is the $m \times (n + 1)$ matrix $[A \mid \mathbf{b}]$ formed by appending the column of constants,

\left[\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ \vdots & \vdots & & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right].

Each row stands for one equation and each of the first $n$ columns belongs to one variable. The bar only separates the constants.

In plain words Line up the variables in the same order in every equation, then copy only the numbers. A variable that is missing from an equation gets a $0$ .

Example The system

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

has the augmented matrix

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

The second equation has no $z$ , so its third entry is $0$ .

Elementary row operations

Definition The elementary row operations on a matrix are the following three moves, where $R_i$ denotes row $i$ .

Swap two rows, $R_i \leftrightarrow R_j$ .
Multiply a row by a nonzero constant $c$ , replacing $R_i$ by $cR_i$ .
Add a multiple of another row to a row, replacing $R_i$ by $R_i + cR_j$ with $j \ne i$ .

Two matrices are row equivalent when one can be turned into the other by a finite sequence of these moves. Each move can be undone by a move of the same kind, so if the augmented matrices of two systems are row equivalent, the systems have exactly the same solutions.

In plain words These are the moves you already make with equations, written for rows. Multiplying by $0$ is not allowed, because it would erase an equation and could add solutions.

Example In the matrix above, replace $R_2$ by $R_2 - 2R_1$ and then $R_3$ by $R_3 - R_1$ . Both clear the first entry of their row,

\left[\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 0 & -3 & -2 & -12 \\ 0 & -3 & 1 & -3 \end{array}\right].

The first move can be undone by replacing $R_2$ by $R_2 + 2R_1$ .

Row echelon form

Definition The leading entry of a nonzero row is its leftmost nonzero entry. A matrix is in row echelon form when

every row of zeros lies below all the nonzero rows, and
the leading entry of each nonzero row lies in a column strictly to the right of the leading entry of the row above it.

It follows that every entry below a leading entry is $0$ . Some books also require each leading entry to be $1$ , which changes nothing that follows. Gaussian elimination is the process of bringing a matrix to row echelon form with elementary row operations, clearing the entries below a leading entry one column at a time from left to right.

In plain words The nonzero numbers form a staircase that steps down and to the right, with only zeros underneath it.

Example One more move finishes the elimination. Replacing $R_3$ by $R_3 - R_2$ gives

\left[\begin{array}{ccc|c} 1 & 2 & 1 & 8 \\ 0 & -3 & -2 & -12 \\ 0 & 0 & 3 & 9 \end{array}\right],

which is in row echelon form. The leading entries $1$ , $-3$ and $3$ step to the right, one column per row.

Pivots

Definition A pivot position of a matrix is a position that holds a leading entry once the matrix has been brought to row echelon form. The pivot positions are the same whichever row operations are used. A pivot column is a column that contains a pivot position, and the nonzero entry in a pivot position during elimination is called a pivot.

In plain words The pivots are the corners of the staircase. Each one is the number you use to clear the entries beneath it.

Example In the echelon form above the pivots are $1$ , $-3$ and $3$ , in positions $(1, 1)$ , $(2, 2)$ and $(3, 3)$ . The columns of $x$ , $y$ and $z$ are all pivot columns, and the column of constants is not.

Back-substitution

Definition Back-substitution solves a consistent system whose augmented matrix is in row echelon form. Solve the last nonzero equation for its leading variable, substitute the result into the equation above it, solve that equation for its leading variable, and continue upward until every leading variable is known. If the system has free variables, described below, they stay as letters and the leading variables come out in terms of them.

In plain words The bottom row has the fewest unknowns, so start there and climb.

Example The echelon form above stands for the equations $x + 2y + z = 8$ , $-3y - 2z = -12$ and $3z = 9$ . The last one gives $z = 3$ . Then

-3y - 2 \cdot 3 = -12 \quad \text{gives} \quad y = 2,

and finally $x + 2 \cdot 2 + 3 = 8$ gives $x = 1$ . The solution is $(1, 2, 3)$ , and all three original equations check out, $1 + 4 + 3 = 8$ , $2 + 2 = 4$ and $1 - 2 + 6 = 5$ .

Reduced row echelon form

Definition A matrix is in reduced row echelon form when it is in row echelon form and also

every leading entry is $1$ , and
each leading $1$ is the only nonzero entry in its column.

Every matrix is row equivalent to exactly one matrix in reduced row echelon form. Continuing elimination upward to reach it is called Gauss-Jordan elimination.

In plain words Scale each pivot to $1$ and clear the entries above it too. Then each equation contains a single leading variable and you can read the answer directly.

Example Start from the echelon form above. Divide $R_3$ by $3$ , replace $R_2$ by $R_2 + 2R_3$ and divide it by $-3$ , then replace $R_1$ by $R_1 - R_3$ and then by $R_1 - 2R_2$ . The result is

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

which says $x = 1$ , $y = 2$ and $z = 3$ with no further work.

Free variables

Definition Take a consistent system and an echelon form of its augmented matrix. A variable whose column is a pivot column is a leading, or basic, variable. Every other variable is a free variable. The general solution lets each free variable be any real number, usually named by a parameter such as $t$ , and expresses the leading variables in terms of the free ones.

In plain words A free variable is one the equations never pin down. Choose its value, and the rest follow.

Example Take the system $x + 2y - z = 3$ and $2x + 4y + z = 9$ . Replace $R_2$ by $R_2 - 2R_1$ , divide it by $3$ , then add it to $R_1$ ,

\begin{aligned} &\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 4 & 1 & 9 \end{array}\right] \\[0.8em] \to {} &\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 0 & 3 & 3 \end{array}\right] \\[0.8em] \to {} &\left[\begin{array}{ccc|c} 1 & 2 & 0 & 4 \\ 0 & 0 & 1 & 1 \end{array}\right]. \end{aligned}

The pivots sit in the columns of $x$ and $z$ , so $y$ is free. With $y = t$ the general solution is

\begin{gathered} x = 4 - 2t, \quad y = t, \quad z = 1, \\[0.4em] t \text{ any real number.} \end{gathered}

For $t = 0$ this gives $(4, 0, 1)$ , and indeed $4 + 0 - 1 = 3$ and $8 + 0 + 1 = 9$ .

Inconsistent row

Definition An inconsistent row of an augmented matrix is a row of the form

\left[\begin{array}{ccc|c} 0 & \cdots & 0 & c \end{array}\right] \quad \text{with} \quad c \ne 0.

It stands for the equation $0 = c$ , which no values of the variables satisfy. A linear system has no solution exactly when an echelon form of its augmented matrix contains an inconsistent row, that is, when the column of constants is a pivot column. A row of all zeros, including the last entry, only says $0 = 0$ and does no harm.

In plain words If elimination ever produces zero equals a nonzero number, the equations contradict each other and the system has no solution.

Example Take $x + y + z = 2$ , $x + 2y = 3$ and $2x + 3y + z = 6$ . Replace $R_2$ by $R_2 - R_1$ , then $R_3$ by $R_3 - 2R_1$ , then $R_3$ by $R_3 - R_2$ ,

\begin{aligned} &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 1 & 2 & 0 & 3 \\ 2 & 3 & 1 & 6 \end{array}\right] \\[0.8em] \to {} &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 1 & -1 & 1 \\ 0 & 1 & -1 & 2 \end{array}\right] \\[0.8em] \to {} &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 0 & 1 \end{array}\right]. \end{aligned}

The last row says $0 = 1$ , so there is no solution. You can see why directly. Adding the first two equations gives $2x + 3y + z = 5$ , which contradicts the third.

Solution structure

Definition Bring the augmented matrix of a linear system to row echelon form.

If the column of constants is a pivot column, the system has no solution.
Otherwise, if every variable column is a pivot column, the system has exactly one solution.
Otherwise the system has at least one free variable and infinitely many solutions.

So a linear system has no solution, exactly one, or infinitely many, never exactly two. Each row holds at most one pivot, so a consistent system with more variables than equations always has infinitely many solutions.

In plain words Look for a contradiction first. If there is none, count the variables without a pivot. None means one answer, and any means infinitely many.

Example The three systems on this page show all three cases.

System	Pivot columns	Free variables	Solutions
$x + 2y + z = 8$ and two more	$x$ , $y$ , $z$	none	exactly one, $(1, 2, 3)$
$x + 2y - z = 3$ and one more	$x$ , $z$	$y$	infinitely many
$x + y + z = 2$ and two more	$x$ , $y$ , constants	not applicable	none

Check yourself

The augmented matrix of a system in $x$ , $y$ and $z$ has the reduced row echelon form below. Write the general solution.

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

Show the answer

The pivots are in the columns of $x$ and $y$ , and there is no inconsistent row, so $z$ is free. With $z = t$ the rows say $x + 2t = 5$ and $y - t = 3$ , so

\begin{gathered} x = 5 - 2t, \quad y = 3 + t, \quad z = t, \\[0.4em] t \text{ any real number.} \end{gathered}

For which values of $k$ does the system $x + 2y = 3$ , $2x + 4y = k$ have a solution, and how many solutions does it have then?

Show the answer

Replacing $R_2$ by $R_2 - 2R_1$ gives the row $\left[\begin{array}{cc|c} 0 & 0 & k - 6 \end{array}\right]$ . For $k \ne 6$ this is an inconsistent row and there is no solution. For $k = 6$ it is a zero row, $y$ is free, and there are infinitely many solutions, $x = 3 - 2t$ and $y = t$ for any real number $t$ .

A system of three linear equations in four variables is known to have a solution. How many solutions does it have?

Show the answer

Infinitely many. Each of the three rows holds at most one pivot, so at most three of the four variable columns are pivot columns. At least one variable is free, and a consistent system with a free variable has infinitely many solutions.

Gaussian Elimination and Solution Structure

Key terms

Augmented matrix

Elementary row operations

Row echelon form

Pivots

Back-substitution

Reduced row echelon form

Free variables

Inconsistent row

Solution structure

Check yourself

How this lesson connects

Builds on

Used later in