Subsection 1.2.1 Gaussian elimination
We will develop an algorithm, which is usually called Gaussian elimination, that allows us to describe the solution space to a system of linear equations.
Preview Activity 1.2.1
Let's begin by considering some simple examples that will guide us in finding a more general approach.

Give a description of the solution space to the linear system:
\begin{equation*}
\begin{alignedat}{3}
x \amp \amp \amp {}={} \amp 2 \\
\amp \amp y \amp {}={} \amp 1. \\
\end{alignedat}
\end{equation*}

Give a description of the solution space to the linear system:
\begin{equation*}
\begin{alignedat}{4}
x \amp {} + {} \amp 2y \amp {}{} \amp z \amp {}={}
\amp 3 \\
\amp \amp 3y \amp {}+{} \amp z \amp {}={} \amp 1. \\
\amp \amp \amp \amp 2z \amp {}={} \amp 4. \\
\end{alignedat}
\end{equation*}

Give a description of the solution space to the linear system:
\begin{equation*}
\begin{alignedat}{3}
x \amp {} + {} \amp 2y \amp {}={} \amp 2 \\
2x\amp {}+{} \amp 2y \amp {}={} \amp 0. \\
\end{alignedat}
\end{equation*}
 Describe the solution space to the linear equation \(0x =
0\text{.}\)
 Describe the solution space to the linear equation \(0x =
5\text{.}\)
As the examples in this preview activity provide some motivation for the general approach we will develop, we wish to call particular attention to two of the examples.
Let's look at the process of substitution a little more carefully. A natural approach to the system
\begin{equation*}
\begin{alignedat}{3}
x \amp {} + {} \amp 2y \amp {}={} \amp 2 \\
2x\amp {}+{} \amp 2y \amp {}={} \amp 0. \\
\end{alignedat}
\end{equation*}
is to use the first equation to express \(x\) in terms of \(y\text{:}\)
\begin{equation*}
x = 22y
\end{equation*}
and then substitute this into the second equation and simplify:
\begin{equation*}
\begin{alignedat}{2}
2x + 2y \amp {}= \amp 0 \\
2(22y) + 2y \amp {}={} \amp 0 \\
44y + 2y \amp {}={} \amp 0 \\
2y \amp {}={} \amp 4. \\
\end{alignedat}
\end{equation*}
The twostep process of solving for \(x\) and substituting into the second equation may be performed more efficiently by adding a multiple of the first equation to the second. More specifically, we multiply the first equation by 2 and add to the second equation
\begin{equation*}
\begin{array}{cr}
\amp 2(\text{equation 1}) \\
+ \amp \text{equation 2} \\
\hline
\end{array}
\end{equation*}
to obtain
\begin{equation*}
\begin{array}{cr}
\amp 2(x+2y=2) \\
+ \amp 2x+2y = 0 \\
\hline
\\
\end{array}
\end{equation*}
\begin{equation*}
\begin{array}{crcr}
\amp 2x4y \amp = \amp 4 \\
+ \amp 2x+2y \amp = \amp 0 \\
\hline
\amp 2y \amp = \amp 4. \\
\end{array}
\end{equation*}
In this way, the system
\begin{equation*}
\begin{alignedat}{3}
x \amp {} + {} \amp 2y \amp {}={} \amp 2 \\
2x\amp {}+{} \amp 2y \amp {}={} \amp 0. \\
\end{alignedat}
\end{equation*}
is transformed into the system
\begin{equation*}
\begin{alignedat}{3}
x \amp {} + {} \amp 2y \amp {}={} \amp 2 \\
\amp \amp 2y \amp {}={} \amp 4, \\
\end{alignedat}
\end{equation*}
which has the same solution space. Of course, the choice to multiply the first equation by 2 was made so that terms involving \(x\) in the two equations will cancel when added. Notice that this operation transforms our original system into a triangular one; we may now perform back substitution to arrive at a decoupled system.
Based on these observations, we take note of three operations that transform a system of linear equations into a new system of equations having the same solution space. Our goal is to create a new system whose solution space is the same as the original system's and may be easily described.
 Scaling

We may multiply one equation by a nonzero number. For instance,
\begin{equation*}
2x 4y = 6
\end{equation*}
has the same set of solutions as
\begin{equation*}
\frac12(2x4y=6)
\end{equation*}
or
\begin{equation*}
x2y=3\text{.}
\end{equation*}
 Interchange
 Interchanging equations will not change the set of solutions. For instance,
\begin{equation*}
\begin{alignedat}{3}
2x \amp {}+{} \amp 4y \amp {}={} \amp 1 \\
x \amp {}{} \amp 3y \amp {}={} \amp 0 \\
\end{alignedat}
\end{equation*}
has the same set of solutions as
\begin{equation*}
\begin{alignedat}{3}
x \amp {}{} \amp 3y \amp {}={} \amp 0 \\
2x \amp {}+{} \amp 4y \amp {}={} \amp 1. \\
\end{alignedat}
\end{equation*}
 Replacement
As we saw above, we may multiply one equation by a real number and add it to another equation. We call this process replacement.
Example 1.2.2
Let's illustrate the use of these operations to find the solution space to the system of equations:
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
2x \amp {}+{} \amp y \amp {}{} \amp 3z \amp {}={} \amp 11 \\
3x \amp {}{} \amp 2y \amp {}+{} \amp z \amp {}={} \amp 10 \\
\end{alignedat}
\end{equation*}
We will first transform the system into a triangular system so we start by eliminating \(x\) from the second and third equations.
We begin with a replacement operation where we multiply the first equation by 2 and add the result to the second equation.
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp 3y \amp {}{} \amp 3z \amp {}={} \amp 3 \\
3x \amp {}{} \amp 2y \amp {}+{} \amp z \amp {}={}
\amp 10 \\
\end{alignedat}
\end{equation*}
Scale the second equation by multiplying it by \(1/3\text{.}\)
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp y \amp {}+{} \amp z \amp {}={} \amp 1 \\
3x \amp {}{} \amp 2y \amp {}+{} \amp z \amp {}={}
\amp 10 \\
\end{alignedat}
\end{equation*}
Another replacement operation eliminates \(x\) from the third equation. We multiply the first equation by 3 and add to the third.
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp y \amp {}+{} \amp z \amp {}={} \amp 1 \\
\amp \amp 4y \amp {}+{} \amp z \amp {}={} \amp 2 \\
\end{alignedat}
\end{equation*}
Eliminate \(y\) from the third equation by multiplying the second equation by 4 and adding it to the third.
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp y \amp {}+{} \amp z \amp {}={} \amp 1 \\
\amp \amp \amp \amp 3z \amp {}={} \amp 6 \\
\end{alignedat}
\end{equation*}
After scaling the third equation by \(1/3\text{,}\) we have found the value for \(z\text{.}\)
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp y \amp {}+{} \amp z \amp {}={} \amp 1 \\
\amp \amp \amp \amp z \amp {}={} \amp 2 \\
\end{alignedat}
\end{equation*}
The system now has a triangular form so we will begin the process of back substitution by multiplying the third equation by 1 and adding to the second.
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\
\amp \amp y \amp \amp \amp {}={} \amp 1 \\
\amp \amp \amp \amp z \amp {}={} \amp 2 \\
\end{alignedat}
\end{equation*}
Finally, multiply the second equation by 2 and add to the first to obtain:
\begin{equation*}
\begin{alignedat}{4}
x \amp \amp \amp \amp \amp {}={} \amp 2 \\
\amp \amp y \amp \amp \amp {}={} \amp 1 \\
\amp \amp \amp \amp z \amp {}={} \amp 2 \\
\end{alignedat}
\end{equation*}
Now that we have arrived at a decoupled system, we know that there is exactly one solution to our original system of equations, which is \((x,y,z) = (2,1,2)\text{.}\)
One could find the same result by applying a different sequence of replacement and scaling operations. However, we chose this particular sequence guided by our desire to first transform the system into a triangular one. To do this, we eliminated the first unknown \(x\) from all but one equation and then proceeded to the next unknowns working left to right. Once we had a triangular system, we used back substitution moving through the unknowns right to left.
We call this process Gaussian elimination and note that it is our primary tool for solving systems of linear equations.
Activity 1.2.2 Gaussian Elimination
Use Gaussian elimination to describe the solutions to the following systems of linear equations.

Does the following linear system have exactly one solution, infinitely many solutions, or no solutions?
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\
2x \amp {}{} \amp y \amp {}{} \amp 2z \amp {}={} \amp 2 \\
x \amp {}+{} \amp y \amp {}+{} \amp z \amp {}={} \amp 0 \\
\end{alignedat}
\end{equation*}

Does the following linear system have exactly one solution, infinitely many solutions, or no solutions?
\begin{equation*}
\begin{alignedat}{4}
x \amp {}{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\
2x \amp {}+{} \amp 4y \amp {}{} \amp z \amp {}={} \amp 5 \\
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\
\end{alignedat}
\end{equation*}

Does the following linear system have exactly one solution, infinitely many solutions, or no solutions?
\begin{equation*}
\begin{alignedat}{4}
x \amp {}{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\
2x \amp {}+{} \amp 4y \amp {}{} \amp z \amp {}={} \amp 5 \\
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 2 \\
\end{alignedat}
\end{equation*}
Subsection 1.2.2 Augmented matrices
After performing Gaussian elimination a few times, you probably noticed that you spent most of the time concentrating on the coefficients and simply recorded the unknowns as place holders. For convenience, we will therefore introduce a shorthand description of linear systems.
When writing a linear system, we always write the unknowns in the same order in each equation. We then construct an augmented matrix by simply forgetting about the unknowns and recording the numerical data in a rectangular array. For instance, the system of equations below has the following augmented matrix
\begin{equation*}
\begin{alignedat}{4}
x \amp {}{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\
2x \amp {}+{} \amp 4y \amp {}{} \amp z \amp {}={} \amp 5 \\
x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\
\end{alignedat}
\end{equation*}
\begin{equation*}
\left[
\begin{array}{rrrr}
1 \amp 2 \amp 2 \amp 1 \\
2 \amp 4 \amp 1 \amp 5 \\
1 \amp 2 \amp 0 \amp 3 \\
\end{array}
\right].
\end{equation*}
The vertical line reminds us where the equals signs appear in the equations. Entries to the left corresponds to coefficients of the equations. We will sometimes choose to focus only on the coefficients of the system in which we case we write the coefficient matrix as
\begin{equation*}
\left[
\begin{array}{rrr}
1 \amp 2 \amp 2 \\
2 \amp 4 \amp 1 \\
1 \amp 2 \amp 0 \\
\end{array}
\right].
\end{equation*}
The three operations we perform on systems of equations translate naturally into operations on matrices. For instance, the replacement operation that multiplies the first equation by 2 and adds it to the second may be recorded as
\begin{equation*}
\left[
\begin{array}{rrrr}
1 \amp 2 \amp 2 \amp 1 \\
2 \amp 4 \amp 1 \amp 5 \\
1 \amp 2 \amp 0 \amp 3 \\
\end{array}
\right]
\sim
\left[
\begin{array}{rrrr}
1 \amp 2 \amp 2 \amp 1 \\
0 \amp 0 \amp 3 \amp 3 \\
1 \amp 2 \amp 0 \amp 3 \\
\end{array}
\right].
\end{equation*}
The symbol \(\sim\) between the matrices indicates that the two matrices are related by a sequence of scaling, interchange, and replacement operations. Since these operations act on the rows of the matrices, we say that the matrices are row equivalent.
Activity 1.2.3 Augmented matrices and solution spaces

Write the augmented matrix for the system of equations
\begin{equation*}
\begin{alignedat}{4}
x \amp {}+{} \amp 2y \amp {}{} \amp z \amp {}={} \amp 1 \\
3x \amp {}+{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp 7 \\
x \amp \amp \amp {}+{} \amp 4z \amp {}={} \amp 3 \\
\end{alignedat}
\end{equation*}
and perform Gaussian elimination to describe the solution space of the system of equations in as much detail as you can.

Suppose that you have a system of linear equations in the unknowns \(x\) and \(y\) whose augmented matrix is row equivalent to
\begin{equation*}
\left[
\begin{array}{rrr}
1 \amp 0 \amp 3 \\
0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \\
\end{array}
\right].
\end{equation*}
Write the system of linear equations corresponding to the augmented matrix. Then describe the solution set of the system of equations in as much detail as you can.

Suppose that you have a system of linear equations in the unknowns \(x\) and \(y\) whose augmented matrix is row equivalent to
\begin{equation*}
\left[
\begin{array}{rrr}
1 \amp 0 \amp 3 \\
0 \amp 1 \amp 0 \\
0 \amp 0 \amp 1 \\
\end{array}
\right].
\end{equation*}
Write the system of linear equations corresponding to the augmented matrix. Then describe the solution set of the system of equations in as much detail as you can.

Suppose that the augmented matrix of a system of linear equations has the following shape where \(*\) could be any real number.
\begin{equation*}
\left[
\begin{array}{rrrrrr}
* \amp * \amp * \amp * \amp * \amp * \\
* \amp * \amp * \amp * \amp * \amp * \\
* \amp * \amp * \amp * \amp * \amp * \\
\end{array}
\right].
\end{equation*}
How many equations are there in this system and how many unknowns?
Based on our earlier discussion in Section 1.1, do you think it's possible that this system has exactly one solution, infinitely many solutions, or no solutions?

Suppose that this augmented matrix is row equivalent to
\begin{equation*}
\left[
\begin{array}{rrrrrr}
1 \amp 2 \amp 0 \amp 0 \amp 3 \amp 2 \\
0 \amp 0 \amp 1 \amp 2 \amp 1 \amp 1 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{array}
\right].
\end{equation*}
Make a choice for the names of the unknowns and write the corresponding system of linear equations. Does the system have exactly one solution, infinitely many solutions, or no solutions?
Subsection 1.2.3 Reduced row echelon form
There is a special class of matrices whose form makes it especially easy to describe the solution space of the corresponding linear system. As we describe the properties of this class of matrices, it may be helpful to consider an example, such as the following matrix.
\begin{equation*}
\left[
\begin{array}{rrrrrr}
1 \amp * \amp 0 \amp * \amp * \amp * \\
0 \amp 0 \amp 1 \amp * \amp * \amp * \\
0 \amp 0 \amp 0 \amp 0 \amp 1 \amp * \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\
\end{array}
\right].
\end{equation*}
Definition 1.2.3
We say that a matrix is in reduced row echelon form if the following properties are satisfied.
 Any rows in which all the entries are zero are at the bottom of the matrix.
 If we move across a row from left to right, the first nonzero entry we encounter is 1. We call this entry the leading entry in the row.
 The leading entry in one row is to the right of the leading entry in any row above.
 A leading entry is the only nonzero entry in its column.
We call a matrix in reduced row echelon form a reduced row echelon matrix.
We have been intentionally vague about whether the matrix we are considering is an augmented matrix corresponding to a linear system or a coefficient matrix since we will eventually consider both possibilities.
Activity 1.2.4 Identifying reduced row echelon matrices
Consider each of the following augmented matrices. Determine if the matrix is in reduced row echelon form. If it is not, perform a sequence of scaling, interchange, and replacement operations to obtain a row equivalent matrix that is in reduced row echelon form. Then use the reduced row echelon matrix to describe the solution space.
\(\left[
\begin{array}{rrrr}
2 \amp 0 \amp 4 \amp 8 \\
0 \amp 1 \amp 3 \amp 2 \\
\end{array}
\right].\)
\(\left[
\begin{array}{rrrr}
1 \amp 0 \amp 0 \amp 1 \\
0 \amp 1 \amp 0 \amp 3 \\
0 \amp 0 \amp 1 \amp 1 \\
\end{array}
\right].\)
\(\left[
\begin{array}{rrrr}
1 \amp 0 \amp 4 \amp 2 \\
0 \amp 1 \amp 3 \amp 2 \\
0 \amp 0 \amp 0 \amp 1 \\
\end{array}
\right].\)
\(\left[
\begin{array}{rrrr}
0 \amp 1 \amp 3 \amp 2 \\
0 \amp 0 \amp 0 \amp 0 \\
1 \amp 0 \amp 4 \amp 2 \\
\end{array}
\right].\)
\(\left[
\begin{array}{rrrr}
1 \amp 2 \amp 1 \amp 2 \\
0 \amp 1 \amp 2 \amp 0 \\
0 \amp 0 \amp 1 \amp 1 \\
\end{array}
\right].\)
If we are given a matrix, the examples in the previous activity indicate that there is a sequence of row operations that produces a matrix in reduced row echelon form. Moreover, the conditions that define reduced row echelon matrices guarantee that this matrix is unique.
Theorem 1.2.4
Given a matrix, there is exactly one reduced row echelon matrix to which it is row equivalent.
Once we have this reduced row echelon matrix, we may describe the set of solutions to the corresponding linear system with relative ease.
Example 1.2.5 Describing the solution space from a reduced row echelon matrix

Consider the row reduced echelon matrix
\begin{equation*}
\left[
\begin{array}{rrrr}
1 \amp 0 \amp 2 \amp 1 \\
0 \amp 1 \amp 1 \amp 2 \\
\end{array}
\right].
\end{equation*}
Its corresponding linear system may be written as
\begin{equation*}
\begin{alignedat}{4}
x \amp \amp \amp {}+{} \amp 2z \amp {}={} \amp 1 \\
\amp \amp y \amp {}+{} \amp z \amp {}={} \amp 2. \\
\end{alignedat}
\end{equation*}
Let's rewrite the equations as
\begin{equation*}
\begin{alignedat}{2}
x \amp {}={} \amp 1 2z\\
y \amp {}={} \amp 2z. \\
\end{alignedat}
\end{equation*}
From this description, it is clear that we obtain a solution for any value of the variable \(z\text{.}\) For instance, if \(z=2\text{,}\) then \(x =
5\) and \(y=0\) so that \((x,y,z) = (5,0,2)\) is a solution. Similarly, if \(z=0\text{,}\) we see that \((x,y,z) = (1,2,0)\) is also a solution.
Because there is no restriction on the value of \(z\text{,}\) we call it a free variable, and note that the linear system has infinitely many solutions. The variables \(x\) and \(y\) are called basic variables as they are determined once we make a choice of the free variable.
We will call this description of the solution space, in which the basic variables are written in terms of the free variables, a parametric description of the solution space.

Consider the matrix
\begin{equation*}
\left[
\begin{array}{rrrr}
1 \amp 0 \amp 0 \amp 4 \\
0 \amp 1 \amp 0 \amp 3 \\
0 \amp 0 \amp 1 \amp 1 \\
0 \amp 0 \amp 0 \amp 0 \\
\end{array}
\right].
\end{equation*}
The last equation gives
\begin{equation*}
0x +0y+0z = 0\text{,}
\end{equation*}
which is true for any \((x,y,z)\text{.}\) We may safely ignore this equation since it does not provide a restriction on the choice of \((x,y,z)\text{.}\) We then see that there is a unique solution \((x,y,z) =
(4,3,1)\text{.}\)

Consider the matrix
\begin{equation*}
\left[
\begin{array}{rrrr}
1 \amp 0 \amp 2 \amp 0 \\
0 \amp 1 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 1 \\
\end{array}
\right].
\end{equation*}
Beginning with the last equation, we see that
\begin{equation*}
0x +0y+0z = 0 = 1\text{,}
\end{equation*}
which is not true for any \((x,y,z)\text{.}\) There is no solution to this particular equation and therefore no solution to the system of equations.