1.2: Matrix Notation and Row Reduction

Learning Objectives

• Represent a system of linear equations as an augmented matrix.
• Apply elementary row operations to simplify matrices systematically.
• Transform a matrix into row echelon form (REF) and reduced row echelon form (RREF).
• Identify basic and free variables in a system and understand their implications for solutions.
• Determine whether a system has a unique solution, infinitely many solutions, or no solution.
• Express solutions with parameters when appropriate and solve practical problems using these techniques.

In the previous section, we reviewed definitions and solved systems of equations with two and three variables, much like the methods you encountered in a precalculus course. In this section, we will shift to the linear algebra perspective, where systematic tools—such as matrices and row operations—allow us to solve systems more efficiently and extend these ideas to larger and more complex systems.

Augmented Matrix

In this section, we will explore a less cumbersome way to find the solutions. First, we will represent a linear system with an augmented matrix. A matrix is simply a rectangular array of numbers. The size or dimension of a matrix is defined as where \(m\) is the number of rows and \(n\) is the number of columns. In order to construct an augmented matrix from a linear system, we create a coefficient matrix from the coefficients of the variables in the system, as well as a constant matrix from the constants. The coefficients from one equation of the system create one row of the augmented matrix.

For example, consider the linear system of three variables and three equations

\[\left\{ \begin{array}{lrcr} (E1) & 2x+3y-z & = & 1 \\ (E2) & 10x-z & = & 2 \\ (E3) & 4x-9y+2z & = & 5 \\ \end{array} \right.\nonumber\]

We encode this system into a matrix by assigning each equation to a corresponding row. Within that row, each variable and the constant gets its own column, and to separate the variables on the left hand side of the equation from the constants on the right hand side, we use a vertical bar, \(|\). Note that in \(E2\), since \(y\) is not present, we record its coefficient as \(0\). The matrix augmented this system is the following \(3\times 3\)

\[\begin{array}{c} \begin{array}{rrrrrrr} & & & \hspace{.33in} x & \hspace{.12in} y & \hspace{.1in} z & \hspace{.03in} b \\ \end{array} \\ \begin{array}{r} (E1) \rightarrow \\ (E2) \rightarrow \\ (E3) \rightarrow \end{array} \left( \begin{array}{rrr|r} 2 & 3 & -1 & 1\\ 10 & 0 & -1 & 2 \\ 4 & -9 & 2 & 5 \end{array} \right) \end{array}\nonumber\]

Notice that the line separates the coefficient matrix, allowing us to study it separately. We will see that this will be useful in another representation of a linear system (see the note below).

Consider the following definition.

Definition \(\PageIndex{1}\): Augmented Matrix of a Linear System

For a linear system of the form \[\begin{array}{c} a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\ \vdots \\ a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m} \end{array}\nonumber \] where the \(x_{i}\) are variables and the \(a_{ij}\) and \(b_{i}\) are constants, the augmented matrix of this system is given by \[\left (\begin{array}{ccc|c} a_{11} & \cdots & a_{1n} & b_{1} \\ \vdots & & \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_{m} \end{array} \right)\nonumber \]

We will look at more examples of how to write the corresponding augmented matrix for a system of equations, since this is the first step in solving with linear algebra methods. Afterward, we will introduce an algorithm for performing row operations on augmented matrices, which will serve as the foundation for solving systems systematically.

Elementary Row Operations

When solving systems of equations, we often perform certain operations to simplify the equations without changing their solutions. For example, we might swap two equations, multiply an equation by a nonzero constant, or replace one equation with a combination of itself and another. These same operations can be carried out directly on the rows of an augmented matrix. In this way, changes to a system of equations correspond exactly to changes in its augmented matrix, and the solution set remains unchanged. With this motivation, we now introduce the formal definition of elementary row operations, which will be our main tool for solving systems systematically.

Definition \(\PageIndex{2}\): Elementary Row Operations

The elementary row operations (also known as row operations) consist of the following

1. Switch two rows.
2. Multiply a row by a nonzero number.
3. Replace a row by any multiple of another row added to it.

We first introduce an example to demonstrate row operations applied to a system of linear equations and their corresponding augmented matrix. Below are some possible row operations that can be used to solve the system. Notice that the goal is to eliminate variables systematically to find the solution, and the primary focus here is to understand the notation for these operations.

Example \(\PageIndex{1}\)

Consider the following system of linear equations:
\[
\left\{
\begin{array}{lrcr}
& 3x - y + z & = & 3 \\
& 2x - 4y + 3z & = & 16 \\
& x - y + z & = & 5
\end{array}
\right.
\]

We start by forming an augmented matrix:

\[
\left\{
\begin{array}{lrcr}
& 3x - y + z & = & 3 \\
& 2x - 4y + 3z & = & 16 \\
& x - y + z & = & 5
\end{array}
\right.
\quad \xrightarrow{\text{agumented matrix}} \quad
\left(
\begin{array}{ccc|c}
3 & -1 & 1 & 3 \\
2 & -4 & 3 & 16 \\
1 & -1 & 1 & 5
\end{array}
\right)
\]

Below are possible row operations applied to the system and their corresponding augmented matrices. Notice that we use a single arrow \(rightarrow\) to apply a row operation to one row, and a double arrow \(leftrightarrow\) when swapping rows.

-Switch two rows.:

\[\begin{array}{ccc}
\left\{
\begin{array}{lrcr}
(E1) & 3x-y+z & = & 3 \\
(E2) & 2x-4y+3z & = & 16 \\
(E3) & x-y+z & = & 5 \\
\end{array}
\right.
& \xrightarrow{\text{Switch $E1$ and $E3$}} &
\left\{
\begin{array}{lrcr}
(E1) & x-y+z & = & 5 \\
(E2) & 2x-4y+3z & = & 16 \\
(E3) & 3x-y+z & = & 3 \\
\end{array}
\right.
\end{array}\nonumber\]

\[\begin{array}{ccc}
\left( \begin{array}{ccc|c}
3 & -1 & \hphantom{-}1 & 3 \\
2 & -4 & 3 & 16 \\
1 & -1 & 1 & 5 \\
\end{array} \right)
& \xrightarrow{\text{$R_1 \leftrightarrow R_3$}} &
\left( \begin{array}{rrr|r}
1 & -1 & \hphantom{-}1 & 5 \\
2 & -4 & 3 & 16 \\
3 & -1 & 1 & 3 \\
\end{array} \right)
\end{array}\nonumber\]

-Multiply a row by a nonzero number.

\[\begin{array}{ccc}
\left\{
\begin{array}{lrcr}
(E1) & 3x_1 +x_2 + x_4 & = & 6 \\
(E2) & 2x_1 + x_2 -x_3 & = & 4 \\
(E3) & x_2 -3x_3 -2x_4 & = & 0 \\
\end{array}
\right.
& \xrightarrow{\text{Replace $E1$ with $\frac{1}{3}E1$}} &
\left\{
\begin{array}{lrcr}
(E1) & x_1 + \frac{1}{3}x_2 + \frac{1}{3}x_4 & = & 2 \\
(E2) & 2x_1 + x_2 -x_3 & = & 4 \\
(E3) & x_2 -3x_3 -2x_4 & = & 0 \\
\end{array}
\right.
\end{array}\nonumber\]

\[\begin{array}{ccc}
\left( \begin{array}{rrrr|r}
3 & \hphantom{-} 1 & 0 & 1 & 6 \\
2 & 1 & -1 & 0 & 4 \\
0 & 1 & -3 & -2 & 0 \\
\end{array} \right)
& \xrightarrow{\text{$R_1 \rightarrow \frac{1}{3}R_1$}} &
\left( \begin{array}{rrrr|r}
1 & \frac{1}{3} & 0 & \frac{1}{3} & 2 \\
2 & \hphantom{-}1 & -1 & 0 & 4 \\
0 & 1 & -3 & -2 & 0 \\
\end{array} \right)
\end{array}\nonumber\]

-Replace a row by any multiple of another row added to it.

\[\begin{array}{ccc}
\left\{
\begin{array}{lrcr}
(E1) & x+\frac{3}{2}y-\frac{1}{2}z & = & \frac{1}{2} \\
(E2) & 10x-z & = & 2 \\
(E3) & 4x-9y+2z & = & 5 \\
\end{array}
\right.
& \xrightarrow[\text{Replace $E3$ with $-4E1 + E3$}]{\text{Replace $E2$ with $-10E1 + E2$}} &
\left\{
\begin{array}{lrcr}
(E1) & x+\frac{3}{2}y-\frac{1}{2}z & = & \frac{1}{2} \\
(E2) & -15y+4z & = & -3 \\
(E3) & -15y+4z & = & 3 \\
\end{array}
\right.
\end{array}\nonumber\]

\[\begin{array}{ccc}
\left( \begin{array}{ccc|c}
1 & \frac{3}{2} & -\frac{1}{2} & \frac{1}{2} \\
10 & 0 & -1 & 2 \\
4 & -9 & 2 & 5 \\
\end{array} \right)
& \xrightarrow[\text{$ R_3 \rightarrow -4R_1 + R_3$}]{\text{$R_2 \rightarrow -10R_1 + R_2$}} &
\left( \begin{array}{rrr|r}
1 & \frac{3}{2} & -\frac{1}{2} & \frac{1}{2} \\
0 & -15 & 4 & -3 \\
0 & -15 & 4 & 3 \\
\end{array} \right)
\end{array}\nonumber\]

To solve a system of linear equations, we can translate elementary row operations into an elimination method applied to the augmented matrix of the system. Elementary row operations—swapping rows, multiplying a row by a nonzero scalar, and adding a multiple of one row to another—allow us to systematically eliminate variables from equations. By performing these operations strategically, we can transform the augmented matrix into an upper triangular (staircase) form, where each successive row contains fewer variables. This triangular form makes the system easier to solve using back substitution, starting from the last equation and substituting values upward to find all unknowns. This method not only streamlines computations but also clearly demonstrates the structure and dependencies within the system.
Below is an example showing how to apply row operations to solve a system of linear equations using the elimination method.

Example \(\PageIndex{2}\)

Solve the following system of linear equation:
\[
\left\{\begin{array}{rrrrrrr} x&+&2y&+&3x&=& 6\\ 2x&-&3y&+&2z&=&14 \\ 3x&+&y&-&z&=&-2 \end{array}\right.
\]

Solution

We start by forming an augmented matrix:

\[\left\{\begin{array}{rrrrrrr} x&+&2y&+&3x&=& 6\\ 2x&-&3y&+&2z&=&14 \\ 3x&+&y&-&z&=&-2 \end{array}\right. \quad\xrightarrow{\text{ agumented matrix}}\quad \left(\begin{array}{ccc|c}1&2&3&6\\2&-3&2&14\\3&1&-1&-2\end{array}\right).\nonumber \]

Eliminating a variable from an equation means producing a zero to the left of the line in an augmented matrix. First we produce zeros in the first column (i.e. we eliminate \(x\)) by subtracting multiples of the first row.

\[\begin{aligned} \left(\begin{array}{ccc|c} 1 &2 &3& 6\\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right) & \quad\xrightarrow{R_2 \rightarrow R_2-2R_1}\quad \left(\begin{array}{ccc|c} 1 &2 &3& 6\\ \color{red}{0}& -7& -4& 2\\ 3& 1& -1& -2\end{array}\right) \\ & \quad\xrightarrow{R_3\rightarrow -3R_1 + R_3}\quad \left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& -7& -4& 2\\ \color{red}{0}& -5& -10& -20\end{array}\right) \end{aligned}\]

This was made much easier by the fact that the top-left entry is equal to \(1\text{,}\) so we can simply multiply the first row by the number below and subtract. In order to eliminate \(y\) in the same way, we would like to produce a \(1\) in the second column. We could divide the second row by \(-7\text{,}\) but this would produce fractions; instead, let’s divide the third by \(-5\).

\[\begin{aligned} \left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& -7& -4& 2\\ 0& -5& -10& -20 \end{array}\right) \quad\xrightarrow{R_3 \rightarrow (1/5)R_3}\quad & \left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0 &-7& -4& 2\\ 0& \color{red}{1}& 2& 4\end{array}\right) \\ {}\quad\xrightarrow{R_2\longleftrightarrow R_3}\quad & \left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4 \\ 0& -7& -4& 2\end{array}\right) \\ {}\quad\xrightarrow{R_3 \rightarrow R_3+7R_2}\quad & \left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4\\ 0& \color{red}{0} & 10& 30 \end{array}\right) \\ {}\quad\xrightarrow{R_3 \rightarrow R_3\div 10}\quad & \left(\begin{array}{ccc|c}1 &2& 3& 6\\ 0& 1& 2& 4 \\ 0& 0& \color{red}{1}& 3\end{array}\right)\end{aligned}\]

We swapped the second and third row just to keep things orderly. Now we translate this augmented matrix back into a system of equations:

\[\left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4\\ 0& 0& 1& 3\end{array}\right) \quad\xrightarrow{\text{becomes}}\quad \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ {}&{}& y &+& 2z &=& 4 \\ {}&{}&{}&{}&z &=& 3\end{array}\right.\nonumber \]

Hence \(z=3\text{;}\) back-substituting as in Example \(\PageIndex{1}\) gives \((x,y,z)=(1,-2,3)\).

Performing row operations on a matrix does not change the solution set of the corresponding system of linear equations. In other words, no matter how we swap rows, scale a row by a nonzero constant, or add a multiple of one row to another, the set of solutions remains exactly the same.

Definition \(\PageIndex{1}\): Row Equivalent

Two matrices are called row equivalent if one can be obtained from the other by doing some number of row operations.

So the linear equations of row-equivalent matrices have the same solution set.

Example \(\PageIndex{3}\): An Inconsistent System

Solve the following system of equations using row operations:

\[\left\{\begin{array}{rrrrr} x &+& y& =& 2\\ 3x &+& 4y &=& 5\\ 4x &+ &5y &=& 9\end{array}\right. \nonumber\]

Solution

\[
\begin{aligned}
\left(\begin{array}{cc|c} 2 & 10 & -1 \\ 3 & 15 & 2 \end{array}\right)
\quad\rightarrow R_1 \leftarrow R_1 \div 2 \quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 3 & 15 & 2 \end{array}\right) \\
\quad\rightarrow R_2 \leftarrow R_2 - 3R_1 \quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 0 & 0 & \frac{7}{2} \end{array}\right) \\
\quad\rightarrow R_2 \leftarrow R_2 \times \frac{2}{7} \quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 0 & 0 & 1 \end{array}\right) \\
\quad\rightarrow R_1 \leftarrow R_1 + \frac{1}{2}R_2 \quad &
\left(\begin{array}{cc|c} 1 & 5 & 0 \\ 0 & 0 & 1 \end{array}\right)
\end{aligned}
\]

This row-reduced matrix corresponds to the inconsistent system:

\[
\left\{
\begin{array}{rrr}
x + 5y & = & 0\\
0 & = & 1
\end{array}
\right.
\]

Notice the last column is a pivot column.

This translates back into the system of equations

\[\left\{\begin{array}{rrrrr} x &+& y &=& 2\\ {}&{}& y& =& -1 \\ {}&{}& 0& =& 2. \end{array}\right. \nonumber\]

Our original system has the same solution set as this system. But this system has no solutions: there are no values of \(x,y\) making the third equation true! We conclude that our original equation was inconsistent.

Echelon Forms

In the previous examples, we saw how to translate a system of linear equations into an augmented matrix and apply row operations. The next step is to work directly with matrices, without referencing the original equations. To do this, we need a systematic algorithm for solving an augmented matrix. First, we define what it means for a matrix to be “solved.” We say a matrix is in row echelon form (REF) when it has a staircase-like structure: each leading entry (the first nonzero number from the left) of a row is to the right of the leading entry in the row above, and all entries below a leading entry are zero. Transforming a matrix into row echelon form using elementary row operations provides a clear pathway for solving the system through back substitution, allowing us to determine all unknowns systematically and efficiently.

Below is the official definition of row echelon form (REF):

Definition \(\PageIndex{2}\): Row Echelon Form

A matrix is in row echelon form if:

1. All zero rows are at the bottom.
2. The first nonzero entry of a row is to the right of the first nonzero entry of the row above.
3. Below the first nonzero entry of a row, all entries are zero.

Here is a picture of a matrix in row echelon form:

\[\left(\begin{array}{ccccc} \color{red}{\boxed{\star}} &\star &\star &\star &\star \\ 0&\color{red}{\boxed{\star}} & \star &\star &\star \\ 0&0&0&\color{red}{\boxed{\star}} &\star \\ 0&0&0&0&0 \end{array}\right) \qquad \begin{aligned} \star &= \text{any number} \\ \color{red}\boxed\star &= \text{any nonzero number} \end{aligned}
\nonumber \]

A matrix in row-echelon form is generally easy to solve using back-substitution. For example,

\[\left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4 \\ 0& 0& 10& 30 \end{array}\right) \quad\xrightarrow{\text{becomes}}\quad \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ {}&{}& y &+& 2z& =& 4 \\ {}&{}&{}&{}& 10z &=& 30. \end{array}\right. \nonumber\]

We immediately see that \(z=3\text{,}\) which implies \(y = 4-2\cdot 3 = -2\) and \(x = 6 - 2(-2) - 3\cdot 3 = 1.\) See Example \(\PageIndex{3}\).

Once a matrix is in row echelon form (REF), we can take the process one step further and transform it into reduced row echelon form (RREF). In RREF, not only does the matrix maintain the staircase-like structure of REF, but each leading entry is also 1 and is the only nonzero entry in its column. By continuing elimination in this way, we can solve the system directly from the matrix, without the need for back substitution. The goal is to simplify the matrix so that each row corresponds to a single variable with its value, providing a clear and immediate solution to the system. This approach extends the elimination method fully to a systematic, straightforward procedure for solving any system of linear equations.

Definition \(\PageIndex{4}\): Reduced Row Echelon Form

A matrix is in reduced row echelon form if it is in row echelon form, and in addition:

4. Each pivot is equal to 1.
5. Each pivot is the only nonzero entry in its column.

Here is a picture of a matrix in reduced row echelon form:

\[\left(\begin{array}{ccccc} \color{red}{1} &0&\star &0&\star \\ 0&\color{red}{1} &\star &0 &\star \\ 0&0&0&\color{red}{1}&\star \\ 0&0&0&0&0\end{array}\right) \qquad \begin{aligned} \star &= \text{any number} \\ \color{red}1 &= \text{leading term} \end{aligned} \nonumber\]

A matrix in reduced row echelon form is in some sense completely solved. For example,

\[\left(\begin{array}{ccc|c} 1 &0& 0& 1\\ 0& 1& 0& -2\\ 0& 0& 1& 3\end{array}\right) \quad\xrightarrow{\text{becomes}}\quad \left\{\begin{array}{rrr} x &=& 1\\ y &=& -2 \\ z &=& 3.\end{array}\right. \nonumber \]

Example \(\PageIndex{4}\)

The following matrices are in reduced row echelon form:

\[\left(\begin{array}{ccc}1&0&2 \\ 0&1&-1\end{array}\right)\qquad \left(\begin{array}{cccc}0&1&8&0\end{array}\right) \qquad \left(\begin{array}{cc|c} 1&17&0\\0&0&1\end{array}\right)\qquad\left(\begin{array}{ccc}0&0&0\\0&0&0\end{array}\right).\nonumber\]

The following matrices are in row echelon form but not reduced row echelon form:

\[\left(\begin{array}{cc}2&1\\0&1\end{array}\right)\qquad \left(\begin{array}{ccc|c} 2&7&1&4 \\ 0&0&2&1 \\ 0&0&0&3\end{array}\right)\qquad \left(\begin{array}{ccc}1&17&0\\0&1&1\end{array}\right) \qquad \left(\begin{array}{ccc}2&1&3\\0&0&0\end{array}\right).\nonumber\]

The following matrices are not in echelon form:

\[\left(\begin{array}{ccc|c} 2&7&1&4\\0&0&2&1\\0&0&1&3 \end{array}\right)\qquad\left(\begin{array}{cc|c}0&17&0\\0&2&1\end{array}\right)\qquad\left(\begin{array}{cc}2&1\\2&1\end{array}\right) \qquad \left(\begin{array}{c}0\\1\\0\\0\end{array}\right).\nonumber\]

Example \(\PageIndex{5}\)

Reduce the following augmented matrix to solve for the corresponding system of linear equation:

\[\left(\begin{array}{ccc|c} 0&-7&-4&2 \\ 2&4&6&12\\ 3&1&-1&-2\end{array}\right).\nonumber\]

Solution

The reduced row echelon form of the matrix is

\[\left(\begin{array}{ccc|c}1&0&0&1 \\ 0&1&0&-2\\0&0&1&3\end{array}\right) \quad\xrightarrow{\text{translates to}}\quad \left\{\begin{array}{rrrrrrr} x&{}&{}&{}&{}&=&1 \\ {}&{}&y&{}&{}&=&-2 \\ {}&{}&{}&{}&z&=&3.\end{array}\right.\nonumber\]

The reduced row echelon form of the matrix tells us that the only solution is \((x,y,z) = (1,-2,3).\)

Figure \(\PageIndex{2}\): Animated slideshow of the row reduction in this example.

Here is the row reduction algorithm, summarized in pictures.

Figure \(\PageIndex{3}\)

After working through examples of transforming a matrix into reduced row echelon form, we may begin to wonder whether the final result depends on the sequence of row operations we choose. Different paths can certainly be taken, but the remarkable fact is that all lead to the same destination. This observation is formalized in the following theorem, which guarantees the uniqueness of the reduced echelon form of a matrix.

Theorem \(\PageIndex{2}\): Uniqueness of the Reduced Row-Echelon Form

Every matrix \(A\) is equivalent to a unique matrix in reduced row-echelon form.

According to this theorem we can say that each matrix \(A\) has a unique reduced row-echelon form.

Pivot Position, Basic and Free variables

Once we obtain a matrix in reduced row echelon form (RREF), it becomes much easier to analyze the structure of the solutions. Recognizing the columns that contain leading entries is important because they correspond to the variables determined directly by the system. We call these positions pivot positions, and they provide a systematic way to describe the solution set of the system.
Now, looking back at the example above, notice that our goal is to create pivot columns and identify the corresponding pivot positions.

Definition \(\PageIndex{5}\)

A pivot position of a matrix is an entry that is a pivot of a row echelon form of that matrix.

A pivot column of a matrix is a column that contains a pivot position.

Example \(\PageIndex{6}\): Pivot Positions

Find the pivot positions and pivot columns of this matrix

\[A=\left(\begin{array}{ccc|c} 0 &-7& -4& 2\\ 2& 4& 6& 12 \\ 3& 1& -1& -2\end{array}\right).\nonumber\]

Solution

We saw in Example \(\PageIndex{5}\) that a row echelon form of the matrix is

\[\left(\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4\\ 0& 0& 10& 30\end{array}\right).\nonumber\]

The pivot positions of \(A\) are the entries that become pivots in a row echelon form; they are marked in red below:

\[\left(\begin{array}{ccc|c}\color{red}{0}&-7&-4&2 \\ 2&\color{red}{4}&6&12 \\ 3&1&\color{red}{-1}&-2\end{array}\right).\nonumber\]

The first, second, and third columns are pivot columns.

Once we have identified the pivot positions in the reduced row echelon form of a matrix, we can use them to describe the solutions of a system of linear equations. Pivot positions correspond to the variables that are directly determined by the system, while the remaining variables—those without pivots—are called free variables. The relationship between pivot and free variables provides a systematic way to express the solution set, whether it consists of a single unique solution or infinitely many. However, not all systems have solutions.

In other words, the row reduced matrix of an inconsistent system looks like this:

\[\left(\begin{array}{cccc|c} 1&0&\star &\star &\color{red}{0} \\ 0&1&\star &\star &\color{red}{0}\\ 0&0&0&0&\color{red}{1}\end{array}\right)\nonumber\]

In the next example, we will see how an inconsistent system can be recognized from its reduced form and the arrangement of pivot columns.

Example \(\PageIndex{7}\): An Inconsistent System

Solve the linear system

\[\left\{\begin{array}{rrrrr}2x &+& 10y &=& -1 \\ 3x &+& 15y &=& 2\end{array}\right. \nonumber \]

using row reduction.

Solution

\[
\begin{aligned}
\left(\begin{array}{cc|c} 2 & 10 & -1 \\ 3 & 15 & 2 \end{array}\right)
\quad\xrightarrow{R_1 \leftarrow R_1 \div 2}\quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 3 & 15 & 2 \end{array}\right) \\
\quad\xrightarrow{R_2 \leftarrow R_2 - 3R_1}\quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 0 & 0 & \frac{7}{2} \end{array}\right) \\
\quad\xrightarrow{R_2 \leftarrow R_2 \times \frac{2}{7}}\quad &
\left(\begin{array}{cc|c} 1 & 5 & -\frac{1}{2} \\ 0 & 0 & 1 \end{array}\right) \\
\quad\xrightarrow{R_1 \leftarrow R_1 + \frac{1}{2}R_2}\quad &
\left(\begin{array}{cc|c} 1 & 5 & 0 \\ 0 & 0 & 1 \end{array}\right)
\end{aligned}
\]

This row-reduced matrix corresponds to the inconsistent system:

\[
\left\{
\begin{array}{rrr}
x + 5y & = & 0\\
0 & = & 1
\end{array}
\right.
\]

In the above example, we saw how recognizing the reduced row echelon form of an inconsistent system leads us to the following theorem:

Theorem \(\PageIndex{2}\): The Row Echelon Form of an Inconsistent System

An augmented matrix corresponds to an inconsistent system of equations if and only if the last column (i.e., the augmented column) is a pivot column.

Not having a pivot column in every column—or equivalently, not having enough independent equations to assign a pivot to each variable—means that some variables will not be determined directly by the system. These undetermined variables are called free variables, as mentioned previously. The variables corresponding to pivot columns, which are determined directly by the system, are called basic variables. The presence of free variables indicates that the system does not have a unique solution; instead, it has infinitely many solutions. By expressing the basic (pivot) variables in terms of these free variables, we can systematically describe all possible solutions and understand the structure of the solution set.

Here are some example

Example \(\PageIndex{8}\): A System with Many Solutions

Solve the linear system
\[
\left\{\begin{array}{rrrrrrr}
2x &+& y &+& 12z &=& 1\\
x &+& 2y &+& 9z &=& -1
\end{array}\right. \nonumber
\]
using row reduction, while identifying pivot positions, basic variables, and free variables.

\textbf{Solution:}
\[
\begin{aligned}
\left(\begin{array}{ccc|c} 2 & 1 & 12 & 1 \\ 1 & 2 & 9 & -1 \end{array}\right)
\quad &\xrightarrow{R_1 \longleftrightarrow R_2}
\quad \left(\begin{array}{ccc|c} \color{red}{1} & 2 & 9 & -1 \\ 2 & 1 & 12 & 1 \end{array}\right) &&\text{(Step 1: first pivot)} \\
\xrightarrow{R_2 \rightarrow R_2 - 2R_1}
\quad & \left(\begin{array}{ccc|c} 1 & 2 & 9 & -1 \\ \color{red}{0} & -3 & -6 & 3 \end{array}\right) &&\text{(Step 2: eliminate below pivot)} \\
\xrightarrow{R_2 \rightarrow (-1/3)R_2 }
\quad & \left(\begin{array}{ccc|c} 1 & 2 & 9 & -1 \\ 0 & \color{red}{1} & 2 & -1 \end{array}\right) &&\text{(Step 3: scale second pivot)} \\
\xrightarrow{R_1 \rightarrow R_1 - 2R_2}
\quad & \left(\begin{array}{ccc|c} 1 & \color{red}{0} & 5 & 1 \\ 0 & 1 & 2 & -1 \end{array}\right) &&\text{(Step 4: eliminate above pivot)}
\end{aligned}
\]

This row-reduced matrix corresponds to the linear system
\[
\left\{\begin{array}{rrrrc}
x &+& 5z &=& 1 \\
y &+& 2z &=& -1
\end{array}\right. \nonumber
\]

Analysis of solutions:

• Pivot positions: The first entry in row 1 (column 1) and the first entry in row 2 (column 2) are pivot positions.
• Basic variables: The variables corresponding to pivot columns, x and y, are basic variables.
• Free variable: Column 3 does not contain a pivot, so z is a free variable.

• Infinitely many solutions: Because there is a free variable, the system has infinitely many solutions. Expressing the basic variables in terms of the free variable z:
  \(x=1−5z, y=−1−2z, z=z\) (free).

To describe all solutions of a system with free variables more conveniently, we can introduce a parameter ( a parameter represnt any real number) , often denoted by t, to represent the free variable. This allows us to write the basic variables explicitly in terms of tt, giving a single, unified expression for every solution in the solution set. By parametrizing the free variable, we can clearly see how the free variable affects the values of the basic variables and conveniently describe the infinitely many solutions in a compact form.

Continuing with the previous example, we can let the free variable \(z\) be represented by the parameter \(t\). Then the solution set can be written as:

\[
x = 1 - 5t, \quad y = -1 - 2t, \quad z = t, \quad t \in \mathbb{R}.
\]

This parametrization captures all infinitely many solutions of the system, showing how each choice of \(t\) gives a corresponding set of values for the basic variables \(x\) and \(y\).

Example \(\PageIndex{1}\): Basic and Free Variables

Find the basic and free variables in the system \[\begin{array}{c} x+2y-z+w=3 \\ x+y-z+w=1 \\ x+3y-z+w=5 \end{array}\nonumber \]

Solution

The row-echelon form of the augmented matrix of this system is given by \[\left [ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right ]\nonumber \] You can see that columns \(1\) and \(2\) are pivot columns. These columns correspond to variables \(x\) and \(y\), making these the basic variables. Columns \(3\) and \(4\) are not pivot columns, which means that \(z\) and \(w\) are free variables.

We can write the solution to this system as \[\begin{array}{c} x=-1+s-t \\ y=2 \\ z=s \\ w=t \end{array}\nonumber \]

Here the free variables are written as parameters, and the basic variables are given by linear functions of these parameters.

In general,

Example \(\PageIndex{7}\): An Infinite Set of Solutions

Give the complete solution to the system of equations \[\begin{array}{c} 3x-y-5z=9 \\ y-10z=0 \\ -2x+y=-6 \end{array}\label{eq:1.8}\]

Solution

The augmented matrix of this system is \[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ -2 & 1 & 0 & -6 \end{array} \right]\nonumber \] In order to find the solution to this system, we will carry the augmented matrix to reduced row-echelon form. The first column is the first pivot column. We want to use row operations to create zeros beneath the first entry in this column, which is in the first pivot position. Replace the third row with \(2\) times the first row added to \(3\) times the third row. This gives

\[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ 0 & 1 & -10 & 0 \end{array} \right]\nonumber \]

Now, we have created zeros beneath the \(3\) in the first column, so we move on to the second pivot column (which is the second column) and repeat the procedure. Take \(-1\) times the second row and add to the third row. \[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\nonumber \] The entry below the pivot position in the second column is now a zero. Notice that we have no more pivot columns because we have only two leading entries.

At this stage, we also want the leading entries to be equal to one. To do so, divide the first row by \(3\). \[\left[ \begin{array}{rrr|r} 1 & - \frac{1}{3} & - \frac{5}{3} & 3 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\nonumber \]

This matrix is now in row-echelon form.

Let’s continue with row operations until the matrix is in reduced row-echelon form. This involves creating zeros above the pivot positions in each pivot column. This requires only one step, which is to add \(\frac{1}{3}\) times the second row to the first row. \[\left[ \begin{array}{rrr|r} 1 & 0 & -5 & 3 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\nonumber \]

This is in reduced row-echelon form, which you should verify using Definition \(\PageIndex{4}\). The equations corresponding to this reduced row-echelon form are \[\begin{array}{c} x - 5z=3 \\ y - 10z = 0 \end{array}\nonumber \] or \[\begin{array}{c} x=3+5z \\ y = 10z \end{array}\nonumber \]

Observe that \(z\) is not restrained by any equation. In fact, \(z\) can equal any number. For example, we can let \(z = t\), where we can choose \(t\) to be any number. In this context \(t\) is called a parameter . Therefore, the solution set of this system is \[\begin{array}{c} x=3+5t \\ y=10t \\ z=t \end{array}\nonumber \] where \(t\) is arbitrary. The system has an infinite set of solutions which are given by these equations. For any value of \(t\) we select, \(x, y,\) and \(z\) will be given by the above equations. For example, if we choose \(t=4\) then the corresponding solution would be \[\begin{array}{c} x = 3 + 5 (4) = 23\\ y = 10(4)=40 \\ z=4 \end{array}\nonumber \]

Example \(\PageIndex{8}\): A Two Parameter Set of Solutions

Find the solution to the system \[\begin{array}{c} x+2y-z+w=3 \\ x+y-z+w=1 \\ x+3y-z+w=5 \end{array}\nonumber \]

Solution

The augmented matrix is \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 1 & 1 & -1 & 1 & 1 \\ 1 & 3 & -1 & 1 & 5 \end{array} \right]\nonumber \] We wish to carry this matrix to row-echelon form. Here, we will outline the row operations used. 

Take \(-1\) times the first row and add to the second. Then take \(-1\) times the first row and add to the third. This yields \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & -1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 0 & 2 \end{array} \right]\nonumber \]

Now add the second row to the third row and divide the second row by \(-1\). \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right] \label{twoparameters1}\]

This matrix is in row-echelon form and we can see that \(x\) and \(y\) correspond to pivot columns, while \(z\) and \(w\) do not. Therefore, we will assign parameters to the variables \(z\) and \(w\). Assign the parameter \(s\) to \(z\) and the parameter \(t\) to \(w.\) Then the first row yields the equation \(x+2y-s+t=3\), while the second row yields the equation \(y=2\). Since \(y=2\), the first equation becomes \(x+4-s+t=3\) showing that the solution is given by \[\begin{array}{c} x=-1+s-t \\ y=2 \\ z=s \\ w=t \end{array}\nonumber \] It is customary to write this solution in the form \[\left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{c} -1+s-t \\ 2 \\ s \\ t \end{array} \right] \label{twoparameters2}\]

Note on RREF Algorithm

• Start with the augmented matrix.
• From left to right, locate the first nonzero column. This is the pivot column, and its top entry is the pivot position. If needed, swap rows so a nonzero entry is in the pivot position.
• Use row operations to make all entries below the pivot equal to zero.
• Repeat steps 2–3 with the remaining submatrix, moving downward and to the right, until no rows remain. At this point the matrix is in row-echelon form.
• Scale each row so that the leading entry (pivot) in each nonzero row is 1.
• Finally, working from right to left, use row operations to create zeros above each pivot. The result is the reduced row-echelon form (RREF).

Exercises

In Exercises 1 - 6, state whether the given matrix is in reduced row echelon form, row echelon form only or in neither of those forms.

1. \(\left[ \begin{array}{rr|r} 1 & 0 & 3 \\ 0 & 1 & 3 \\ \end{array} \right]\)
2. \(\left[ \begin{array}{rrr|r} 3 & -1 & \hphantom{-}1 & 3 \\ 2 & -4 & 3 & 16 \\ 1 & -1 & 1 & 5 \\ \end{array} \right]\)
3. \(\left[ \begin{array}{rrr|r} 1 & 1 & 4 & 3 \\ 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]\)
4. \(\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right]\)
5. \(\left[ \begin{array}{rrrr|r} 1 & 0 & 4 & 3 & 0 \\ 0 & 1 & 3 & 6 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]\)
6. \(\left[ \begin{array}{rrr|r} 1 & 1 & 4 & 3 \\ 0 & 1 & 3 & 6 \\ \end{array} \right]\)

In Exercises 7 - 12, the following matrices are in reduced row echelon form. Determine the solution of the corresponding system of linear equations or state that the system is inconsistent.

7. \(\left[ \begin{array}{rr|r} 1 & 0 & -2 \\ 0 & 1 & 7 \\ \end{array} \right]\)
8. \(\left[ \begin{array}{rrr|r} 1 & 0 & 0 & -3 \\ 0 & 1 & 0 & 20 \\ 0 & 0 & 1 & 19 \end{array} \right]\)
9. \(\left[ \begin{array}{rrrr|r} 1 & 0 & 0 & 3 & 4 \\ 0 & 1 & 0 & 6 & -6 \\ 0 & 0 & 1 & 0 & 2 \end{array} \right]\)
10. \(\left[ \begin{array}{rrrr|r} 1 & 0 & 0 & 3 & 0 \\ 0 & 1 & 2 & 6 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right]\)
11. \(\left[ \begin{array}{rrrr|r} 1 & \hphantom{-}0 & -8 & 1 & 7 \\ 0 & 1 & 4 & -3 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]\)
12. \(\left[ \begin{array}{rrr|r} 1 & \hphantom{-}0 & 9 & -3 \\ 0 & 1 & -4 & 20 \\ 0 & 0 & 0 & 0 \end{array} \right]\)

In Exercises 13 - 26, solve the following systems of linear equations using the techniques discussed in this section. Compare and contrast these techniques with those you used to solve the systems in the Exercises in Section 8.1.

13. \(\left\{ \begin{array}{rcr} -5x + y & = & 17 \\ x + y & = & 5 \end{array} \right.\)
14. \(\left\{ \begin{array}{rcr} x + y + z & = & 3 \\ 2x - y + z & = & 0 \\ -3x + 5y + 7z & = & 7 \end{array} \right.\)
15. \(\left\{ \begin{array}{rcr} 4x - y + z & = & 5 \\ 2y + 6z & = & 30 \\ x + z & = & 5 \end{array} \right.\)
16. \(\left\{ \begin{array}{rcr} x-2y+3z & = & 7 \\ -3x+y+2z & = & -5 \\ 2x+2y+z & = & 3 \end{array} \right.\)
17. \(\left\{ \begin{array}{rcr} 3x-2y+z & = & -5 \\ x+3y-z & = & 12 \\ x+y+2z & = & 0 \end{array} \right.\)
18. \(\left\{ \begin{array}{rcr} 2x-y+z& = & -1 \\ 4x+3y+5z & = & 1 \\ 5y+3z & = & 4 \end{array} \right.\)
19. \(\left\{ \begin{array}{rcr} x-y+z & = & -4 \\ -3x+2y+4z & = & -5 \\ x-5y+2z & = & -18 \end{array} \right.\)
20. \(\left\{ \begin{array}{rcr} 2x-4y+z & = & -7 \\ x-2y+2z & = & -2 \\ -x+4y-2z & = & 3 \end{array} \right.\)
21. \(\left\{ \begin{array}{rcr} 2x-y+z & = & 1 \\ 2x+2y-z & = & 1 \\ 3x+6y+4z & = & 9 \end{array} \right.\)
22. \(\left\{ \begin{array}{rcr} x-3y-4z & = & 3 \\ 3x+4y-z & = & 13 \\ 2x-19y-19z & = & 2 \end{array} \right.\)
23. \(\left\{ \begin{array}{rcr} x+y+z & = & 4 \\ 2x-4y-z& = & -1 \\ x-y & = & 2 \end{array} \right.\)
24. \(\left\{ \begin{array}{rcr} x-y+z & = & 8 \\ 3x+3y-9z & = & -6 \\ 7x-2y+5z & = & 39 \end{array} \right.\)
25. \(\left\{ \begin{array}{rcr} 2x-3y+z & = & -1 \\ 4x-4y+4z & = & -13 \\ 6x-5y+7z & = & -25 \end{array} \right.\)
26. \(\left\{ \begin{array}{rcr} x_{1} - x_{3} & = & -2 \\ 2x_{2} - x_{4} & = & 0 \\ x_{1} - 2x_{2} + x_{3} & = & 0 \\ -x_{3} + x_{4} & = & 1 \end{array} \right.\)
27. It’s time for another meal at our local buffet. This time, 22 diners (5 of whom were children) feasted for \(\$162.25\), before taxes. If the kids buffet is \(\$4.50\), the basic buffet is \(\$7.50\), and the deluxe buffet (with crab legs) is \(\$9.25\), find out how many diners chose the deluxe buffet.
28. Carl wants to make a party mix consisting of almonds (which cost \(\$7\) per pound), cashews (which cost \(\$5\) per pound), and peanuts (which cost \(\$2\) per pound.) If he wants to make a \(10\) pound mix with a budget of \(\$35\), what are the possible combinations almonds, cashews, and peanuts? (You may find it helpful to review Example 8.1.3 in Section 8.1.)
29. Find the quadratic function passing through the points \((-2,1)\), \((1,4)\), \((3,-2)\)
30. At 9 PM, the temperature was \(60^{\circ}\)F; at midnight, the temperature was \(50^{\circ}\)F; and at 6 AM, the temperature was \(70^{\circ}\)F . Use the technique in Example 8.2.3 to fit a quadratic function to these data with the temperature, \(T\), measured in degrees Fahrenheit, as the dependent variable, and the number of hours after 9 PM, \(t\), measured in hours, as the independent variable. What was the coldest temperature of the night? When did it occur?
31. The price for admission into the Stitz-Zeager Sasquatch Museum and Research Station is $15 for adults and $8 for kids 13 years old and younger. When the Zahlenreich family visits the museum their bill is $38 and when the Nullsatz family visits their bill is $39. One day both families went together and took an adult babysitter along to watch the kids and the total admission charge was $92. Later that summer, the adults from both families went without the kids and the bill was $45. Is that enough information to determine how many adults and children are in each family? If not, state whether the resulting system is inconsistent or consistent dependent. In the latter case, give at least two plausible solutions.
32. Use the technique in Example 8.2.3 to find the line between the points \((-3, 4)\) and \((6, 1)\). How does your answer compare to the slope-intercept form of the line in Equation 23?
33. With the help of your classmates, find at least two different row echelon forms for the matrix \[\left[ \begin{array}{rr|r} 1 & 2 & 3 \\ 4 & 12 & 8 \\ \end{array} \right]\nonumber\]

Answers

1. Reduced row echelon form
2. Neither
3. Row echelon form only
4. Reduced row echelon form
5. Reduced row echelon form
6. Row echelon form only
7. \((-2, 7)\)
8. \((-3, 20, 19)\)

9. \((-3t + 4, -6t - 6, 2, t)\)
   for all real numbers \(t\)

10. Inconsistent

11. \((8s - t + 7, -4s + 3t + 2, s, t)\)
    for all real numbers \(s\) and \(t\)

12. \((-9t - 3, 4t + 20, t)\)
    for all real numbers \(t\)

13. \((-2, 7)\)
14. \((1, 2, 0)\)

15. \((-t + 5, -3t + 15, t)\)
    for all real numbers \(t\)

16. \((2,-1,1)\)
17. \((1,3,-2)\)
18. Inconsistent
19. \((1,3,-2)\)
20. \(\left(-3,\frac{1}{2},1\right)\)
21. \(\left(\frac{1}{3},\frac{2}{3},1\right)\)

22. \(\left(\frac{19}{13} t + \frac{51}{13},-\frac{11}{13} t+\frac{4}{13},t\right)\)
    for all real numbers \(t\)

23. Inconsistent
24. \(\left(4,-3,1\right)\)

25. \(\left(-2t - \frac{35}{4},-t - \frac{11}{2},t\right)\)
    for all real numbers \(t\)

26. \((1, 2, 3, 4)\)
27. This time, 7 diners chose the deluxe buffet.
28. If \(t\) represents the amount (in pounds) of peanuts, then we need \(1.5 t - 7.5\) pounds of almonds and \(17.5 - 2.5t\) pounds of cashews. Since we can’t have a negative amount of nuts, \(5 \leq t \leq 7\).
29. \(f(x) = -\frac{4}{5} x^2+\frac{1}{5} x + \frac{23}{5}\)
30. \(T(t) = \frac{20}{27} t^2 - \frac{50}{9} t + 60\). Lowest temperature of the evening \(\frac{595}{12} \approx 49.58^{\circ}\)F at 12:45 AM.
31. Let \(x_{1}\) and \(x_{2}\) be the numbers of adults and children, respectively, in the Zahlenreich family and let \(x_{3}\) and \(x_{4}\) be the numbers of adults and children, respectively, in the Nullsatz family. The system of equations determined by the given information is

    \(\left\{ \begin{array}{rcr} 15x_{1} + 8x_{2} & = & 38 \\ 15x_{3} + 8x_{4} & = & 39 \\ 15x_{1} + 8x_{2} + 15x_{3} + 8x_{4} & = & 77 \\ 15x_{1} + 15x_{3} & = & 45 \end{array} \right.\)

    We subtracted the cost of the babysitter in E3 so the constant is 77, not 92. This system is consistent dependent and its solution is \(\left(\frac{8}{15}t + \frac{2}{5}, -t + 4, -\frac{8}{15}t + \frac{13}{5}, t \right)\). Our variables represent numbers of adults and children so they must be whole numbers. Running through the values \(t = 0, 1, 2, 3, 4\) yields only one solution where all four variables are whole numbers; \(t = 3\) gives us \((2, 1, 1, 3)\). Thus there are 2 adults and 1 child in the Zahlenreichs and 1 adult and 3 kids in the Nullsatzs.