Systems of equations and row reduction

Day: 3 of 40
Length: 2:45
Textbook: Lay §1.1, 1.2
Syllabus: Groundwork before Lesson 10

Row operations change the equations without changing the solution set, so we simplify until the answer is readable.

Yesterday, asking whether $\pink{\vec b}$ is in a span turned into a set of equations to solve, and we solved each one with whatever trick fit. Bigger systems need a method that always works. Today's method is row reduction. Its goal is to turn a system into one so simple that you can read the solution straight off it, while never changing which points are solutions. First we look at what a solution can look like, so we know what kind of answer to expect.

Each section below opens with a problem. Try it before you open the walkthrough, even if you only get partway.

Three possible outcomes

Solve the system

\begin{aligned} \yellow{x_1 - 2x_2} &\yellow{\;= -1} \\ \blue{-x_1 + 3x_2} &\blue{\;= 3.} \end{aligned}

Then change the second equation to $-x_1 + 2x_2 = 3$ and solve again. Finally, try $-x_1 + 2x_2 = 1$ .

Walk through the solution

The $x_1$ terms are $x_1$ and $-x_1$ , so adding the two equations cancels them. That leaves $-2x_2 + 3x_2 = -1 + 3$ , which is $x_2 = 2$ . Putting $x_2 = 2$ into the first equation gives $x_1 - 4 = -1$ , so $x_1 = 3$ . The system has exactly one solution, $(3, 2)$ .

With the second equation changed to $-x_1 + 2x_2 = 3$ , adding the equations gives $0 = 2$ . Nothing can make $0$ equal $2$ , so this system has no solution at all.

With $-x_1 + 2x_2 = 1$ , adding gives $0 = 0$ , which is always true. The second equation is the first one multiplied by $-1$ , so both describe the same line. Every point on that line is a solution, which means there are infinitely many.

Three small planes, each with a yellow and a blue line. On the left the lines are parallel and never meet. In the middle they cross at one teal point, (3, 2). On the right the blue line lies on top of the yellow one, drawn as a single thick teal line.

Each equation in two unknowns is a line, and a solution is a point on both lines. The picture shows the three things two lines can do: miss each other, cross once, or coincide.

How many solutions a system can have

A linear equation in $x_1, \dots, x_n$ can be written $a_1x_1 + \cdots + a_nx_n = b$ . A linear system is a few of these sharing the same unknowns. A solution is a list of numbers that makes every equation true at once, and the solution set is the set of all solutions.

Every linear system has no solution, exactly one, or infinitely many, just as in Problem 1. Two lines cannot share exactly two points. A system with at least one solution is consistent, and a system with none is inconsistent.

Which of these equations is linear?

The augmented matrix

Solving means doing the same few moves many times. Writing every $x_1$ and $x_2$ at each step is slow, so we keep only the numbers.

Write the coefficients of this system in a grid, one row per equation and one column per unknown, and enter it row by row. Then add the right-hand sides as a fourth column.

\begin{aligned} x_1 + 3x_2 - x_3 &= 4 \\ 2x_2 + x_3 &= 1 \\ -x_1 + 4x_3 &= 2 \end{aligned}

Walk through the solution

Line up each variable in its own column. The first equation gives the row $1, 3, -1$ . The second equation has no $x_1$ , and a missing variable means a coefficient of $0$ , so its row is $0, 2, 1$ . The third equation has no $x_2$ , so its row is $-1, 0, 4$ .

\begin{bmatrix} 1 & 3 & -1 \\ 0 & 2 & 1 \\ -1 & 0 & 4 \end{bmatrix}

Adding the right-hand sides $4, 1, 2$ as a last column gives

\left[\begin{array}{rrr|r} 1 & 3 & -1 & 4 \\ 0 & 2 & 1 & 1 \\ -1 & 0 & 4 & 2 \end{array}\right]

The bar separates the coefficients from the right-hand sides. Each row still says one equation, and each column still belongs to one unknown.

Coefficient and augmented matrices

The coefficient matrix holds the coefficients of each variable in its own column. The augmented matrix adds the right-hand sides as a last column. On Day 2 you built the same grid from a vector equation, with the vectors as columns.

A matrix with $m$ rows and $n$ columns is $m \times n$ , rows first. In Problem 2 the coefficient matrix is $3 \times 3$ and the augmented matrix is $3 \times 4$ .

Row operations

The goal is a system like $x_1 = 3$ , $x_2 = 2$ , where each equation hands you one unknown. To get there we need moves that change the equations but never change the solutions.

Start from Problem 1's system, $x_1 - 2x_2 = -1$ and $-x_1 + 3x_2 = 3$ , whose solution is $(3, 2)$ . Replace the second equation by the sum of the two equations. Does $(3, 2)$ still satisfy both equations? Could the new system have a solution that the old one did not?

Walk through the solution

The sum of the equations is $(x_1 - x_1) + (-2x_2 + 3x_2) = -1 + 3$ , which is $x_2 = 2$ . The new system is $x_1 - 2x_2 = -1$ and $x_2 = 2$ .

The point $(3, 2)$ satisfies the first equation, which did not change, and it satisfies $x_2 = 2$ . Any point on both old lines satisfies their sum, so no solution was lost.

For the second question, run the move backward. Subtracting the first equation from $x_2 = 2$ gives back $-x_1 + 3x_2 = 3$ . So any solution of the new system also satisfies the old one, and no solution was gained. The move is reversible, and that is why the solution set stayed the same.

Three moves that keep every solution

The three elementary row operations change an augmented matrix without changing its solution set, because each one can be undone.

\begin{array}{lll} & \textsf{Operation} & \textsf{Undo it with} \\[4pt] \textsf{Replacement} & R_2 \leftarrow R_2 + c\,R_1 & R_2 \leftarrow R_2 - c\,R_1 \\ \textsf{Interchange} & R_1 \leftrightarrow R_2 & R_1 \leftrightarrow R_2 \\ \textsf{Scaling} & R_2 \leftarrow c\,R_2,\ c \neq 0 & R_2 \leftarrow \tfrac1c\,R_2 \end{array}

Two matrices are row equivalent, written $\sim$ , when a sequence of row operations turns one into the other. Row-equivalent systems have the same solution set. On Day 8 each of these operations becomes a matrix of its own.

In the picture, a replacement turns one line about the solution point. Use the sliders to make each row mention a single unknown.

Clear the

x_1

entry of row 2, then the

x_2

entry of row 1, so each row mentions a single unknown.

R_2 \leftarrow R_2 + a\,R_1

a = 0

R_1 \leftarrow R_1 + b\,R_2

b = 0

\left[\begin{array}{rr|r} \textcolor{#FFD447}{1} & \textcolor{#FFD447}{-2} & \textcolor{#FFD447}{-1} \\ \textcolor{#5BC0EB}{-1} & \textcolor{#5BC0EB}{3} & \textcolor{#5BC0EB}{3} \end{array}\right]

\begin{aligned} \textcolor{#FFD447}{x_1 - 2x_2 = -1} \\ \textcolor{#5BC0EB}{- x_1 + 3x_2 = 3} \end{aligned}

A plane with dashed yellow and blue lines for the original system, crossing at a teal point (3, 2). Solid lines show the final system, a vertical yellow line x1 = 3 and a horizontal blue line x2 = 2, crossing at the same point.

R_2 \leftarrow R_2 + R_1

Which operation undoes $R_3 \leftarrow R_3 - 4R_1$ ?

Echelon form

We need to know when to stop. The next problem compares two possible end points.

Both matrices below are row equivalent to the same system. Read off the solution from each one.

A = \left[\begin{array}{rrr|r} 1 & 2 & -1 & -3 \\ 0 & 1 & 3 & 8 \\ 0 & 0 & -6 & -18 \end{array}\right] \qquad B = \left[\begin{array}{rrr|r} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 3 \end{array}\right]

Walk through the solution

Matrix $B$ is the easy one. Its rows say $x_1 = 2$ , $x_2 = -1$ and $x_3 = 3$ directly.

Matrix $A$ takes a little more work, but its shape helps. The last row mentions only $x_3$ : it says $-6x_3 = -18$ , so $x_3 = 3$ . The middle row mentions only $x_2$ and $x_3$ , so put in $x_3 = 3$ : $x_2 + 9 = 8$ , which gives $x_2 = -1$ . The top row then gives $x_1 + 2(-1) - 3 = -3$ , so $x_1 = 2$ . Solving from the bottom up like this is called back substitution.

Both give $(2, -1, 3)$ . $A$ has a staircase of zeros in its lower left, which is enough to finish by back substitution. $B$ goes further, with a single $1$ in each column, so it needs no work at all.

Echelon and reduced echelon form

The leading entry of a row is its leftmost nonzero entry. A matrix is in echelon form when it has these three properties.

(1) All nonzero rows are above any rows of zeros.

(2) Each leading entry is in a column to the right of the leading entry in the row above it.

(3) Every entry below a leading entry is zero.

It is in reduced echelon form when it also has these two.

(4) Every leading entry is $1$ .

(5) Each leading $1$ is the only nonzero entry in its column.

Every matrix is row equivalent to exactly one reduced echelon matrix.

In Problem 4, $A$ is in echelon form and $B$ is in reduced echelon form. Echelon form is the halfway target, where you can already tell how many solutions there are. Reduced echelon form is the finish line, where you read the solutions off.

Is $\begin{bmatrix} 1 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 1 & 3 \end{bmatrix}$ in echelon form?

The row reduction algorithm

Row reduction has two phases. The forward phase works down and to the right, making zeros below each leading entry until the matrix is in echelon form. The backward phase works up and to the left, scaling each leading entry to $1$ and making zeros above it.

Solve by row reduction.

\begin{aligned} x_1 + 2x_2 - x_3 &= -3 \\ 2x_1 + 5x_2 + x_3 &= 2 \\ -x_1 + x_2 + 4x_3 &= 9 \end{aligned}

Walk through the solution

Each step below says which zero it makes and why that zero comes next.

1
Column 1 is the leftmost column, and its top entry $1$ is nonzero, so it serves as the first pivot. Clear the entries below it with $R_2 \leftarrow R_2 - 2R_1$ and $R_3 \leftarrow R_3 + R_1$ :
$\left[\begin{array}{rrr|r} 1 & 2 & -1 & -3 \\ 2 & 5 & 1 & 2 \\ -1 & 1 & 4 & 9 \end{array}\right] \sim \left[\begin{array}{rrr|r} 1 & 2 & -1 & -3 \\ 0 & 1 & 3 & 8 \\ 0 & 3 & 3 & 6 \end{array}\right]$
For example, row 2 becomes $(2 - 2,\ 5 - 4,\ 1 + 2,\ 2 + 6) = (0, 1, 3, 8)$ .
2
Cover row 1 and repeat on the rows below it. The next pivot is the $1$ in row 2, column 2. Clear below it with $R_3 \leftarrow R_3 - 3R_2$ , which gives row 3 as $(0,\ 3 - 3,\ 3 - 9,\ 6 - 24) = (0, 0, -6, -18)$ :
$\sim \left[\begin{array}{rrr|r} 1 & 2 & -1 & -3 \\ 0 & 1 & 3 & 8 \\ 0 & 0 & -6 & -18 \end{array}\right]$
This is matrix $A$ from Problem 4, so the forward phase is done.
3
4
Clear above that pivot with $R_2 \leftarrow R_2 - 3R_3$ and $R_1 \leftarrow R_1 + R_3$ . Row 2 becomes $(0, 1, 0, 8 - 9) = (0, 1, 0, -1)$ and row 1 becomes $(1, 2, 0, -3 + 3) = (1, 2, 0, 0)$ :
$\sim \left[\begin{array}{rrr|r} 1 & 2 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 3 \end{array}\right]$
5
Move one pivot up and to the left. Clear above the pivot in column 2 with $R_1 \leftarrow R_1 - 2R_2$ , which makes row 1 $(1, 0, 0, 0 + 2) = (1, 0, 0, 2)$ :
$\sim \left[\begin{array}{rrr|r} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 3 \end{array}\right]$
The solution is $(2, -1, 3)$ . Check it in the second original equation: $2(2) + 5(-1) + 3 = 2$ .

The algorithm in five steps

The forward phase repeats steps 1 to 4, and the backward phase is step 5.

Step 1. Find the leftmost column that is not all zeros. Its top position will hold a pivot.

Step 2. If that position holds $0$ , swap in a row that has a nonzero entry there.

Step 3. Use replacements to make every entry below the pivot zero.

Step 4. Cover that row and repeat steps 1 to 3 on the rows below it.

Step 5. Starting from the lowest pivot and moving up, scale each pivot to $1$ and use replacements to make every entry above it zero.

Now run the algorithm yourself. This system starts with a $0$ in the top left, so step 2 is needed right away. The operation starts set to that swap.

Use row operations to reach reduced echelon form. The orange entries are the leading entries of each row.

\begin{matrix} R_1 \\ R_2 \\ R_3 \end{matrix} \left[\begin{array}{rrr|r} 0 & \textcolor{#FF8A3D}{1} & 2 & 3 \\ \textcolor{#FF8A3D}{1} & 2 & 1 & 4 \\ \textcolor{#FF8A3D}{2} & 5 & 3 & 9 \end{array}\right]

Operation

Row that changes

Row it uses

c = -1

R_1 \leftrightarrow R_2

0 moves

Pivots and free variables

Sometimes the reduced form has fewer pivots than unknowns. Then some unknowns are not pinned down.

The augmented matrix of a system reduces to

\left[\begin{array}{rrrr|r} 1 & -2 & 0 & 7 & 1 \\ 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].

Describe every solution. Then give the solution with $x_2 = 0$ and $x_4 = 0$ .

Walk through the solution

Turn the rows back into equations. Row 1 says $x_1 - 2x_2 + 7x_4 = 1$ and row 2 says $x_3 - 2x_4 = 1$ . Row 3 says $0 = 0$ , which is always true and adds no condition.

Each nonzero row starts with a leading $1$ , in column 1 and column 3. So solve row 1 for $x_1$ and row 2 for $x_3$ :

x_1 = 1 + 2x_2 - 7x_4, \qquad x_3 = 1 + 2x_4.

Nothing restricts $x_2$ or $x_4$ . You may choose them freely, and each choice gives one solution. With $x_2 = 0$ and $x_4 = 0$ you get $x_1 = 1$ and $x_3 = 1$ , so the solution is $(1, 0, 1, 0)$ . With $x_2 = 1$ and $x_4 = 0$ you get $(3, 1, 1, 0)$ , another solution.

The reduced matrix with orange boxes around the pivots in columns 1 and 3, an orange staircase under them, and the labels x2 and x4 in orange because their columns have no pivot.

1

The general solution

The list above is the general solution. It solves for each basic variable in terms of the free variables and lists every variable, including the free ones. The free variables act as parameters: each choice of their values gives one solution. Pivots come back often. On Days 12 and 13, counting them tells you whether the columns of a matrix span $\mathbb R^m$ and whether they are independent.

Pivot positions are the leading entries of any echelon form, so you do not need to finish the reduction to find them. Tap them in this echelon form.

Tap every pivot position in this echelon form, and nothing else.

x_{1}

x_{2}

x_{3}

x_{4}

x_{5}

Existence and uniqueness

An echelon form already tells you how many solutions there are, before the backward phase.

For the system $x_1 - 2x_2 = 3$ , $\ 3x_1 + hx_2 = k$ , find the values of $h$ and $k$ that give infinitely many solutions. Which values give no solution, and which give exactly one?

Walk through the solution

Do one step of the forward phase and look at what is left. Clear the $3$ below the first pivot with $R_2 \leftarrow R_2 - 3R_1$ . Row 2 becomes $(3 - 3,\ h + 6,\ k - 9)$ :

\left[\begin{array}{rr|r} 1 & -2 & 3 \\ 3 & h & k \end{array}\right] \sim \left[\begin{array}{rr|r} 1 & -2 & 3 \\ 0 & h + 6 & k - 9 \end{array}\right]

Now read row 2 as the equation $(h + 6)x_2 = k - 9$ .

If $h \neq -6$ , row 2 has a pivot, so $x_2$ is determined and there is exactly one solution, whatever $k$ is.

If $h = -6$ , row 2 says $0 = k - 9$ . When $k \neq 9$ that equation is false, so there is no solution. When $k = 9$ it says $0 = 0$ , so $x_2$ is free and there are infinitely many solutions.

Existence and uniqueness theorem

A linear system is consistent exactly when an echelon form of its augmented matrix has no row $\left[\begin{array}{ccc|c} 0 & \cdots & 0 & b \end{array}\right]$ with $b \neq 0$ . A consistent system has a unique solution when it has no free variables, and infinitely many when it has at least one.

A row $[\,0 \ \cdots \ 0 \mid b\,]$ says $0 = b$ , which nothing satisfies. Below is Problem 7's system, with the elimination step already done in the lower readout. Watch how the blue line and the echelon row change together.

Choose

h

and

k

so the system has infinitely many solutions.

\begin{aligned} \textcolor{#FFD447}{x_1 - 2x_2 = 3} \\ \textcolor{#5BC0EB}{3x_1 + h\,x_2 = k} \end{aligned}

h = 1

k = 2

\sim \left[\begin{array}{rr|r} \textcolor{#FFD447}{1} & \textcolor{#FFD447}{-2} & \textcolor{#FFD447}{3} \\ \textcolor{#5BC0EB}{0} & \textcolor{#5BC0EB}{7} & \textcolor{#5BC0EB}{-7} \end{array}\right]

Every row has a pivot, so there is exactly one solution.

Tomorrow, Day 4 packs a whole system into one equation, $A\mathbf x = \mathbf b$ , and row reduction stays the way to solve it.

Practice

Warm-up

A system has $3$ equations in $5$ unknowns. What size is its augmented matrix?

Show the solution

There is one row per equation, so $3$ rows. There is one column per unknown plus one for the right-hand sides, so $5 + 1 = 6$ columns. The augmented matrix is $3 \times 6$ .

Which matrix is in reduced echelon form? (Modeled on Lay §1.2 #1.)

Solve by row reduction. (Modeled on Lay §1.1 #1.)

\begin{aligned} x_1 + 4x_2 &= 6 \\ -3x_1 - 10x_2 &= -14 \end{aligned}

Show the solution

Use $R_2 \leftarrow R_2 + 3R_1$ , then $R_2 \leftarrow \tfrac12 R_2$ , then $R_1 \leftarrow R_1 - 4R_2$ .

\left[\begin{array}{rr|r} 1 & 4 & 6 \\ -3 & -10 & -14 \end{array}\right] \sim \left[\begin{array}{rr|r} 1 & 4 & 6 \\ 0 & 2 & 4 \end{array}\right] \sim \left[\begin{array}{rr|r} 1 & 4 & 6 \\ 0 & 1 & 2 \end{array}\right] \sim \left[\begin{array}{rr|r} 1 & 0 & -2 \\ 0 & 1 & 2 \end{array}\right]

So $x_1 = -2$ and $x_2 = 2$ . Check: $-2 + 8 = 6$ and $6 - 20 = -14$ .

Core

Solve by row reduction. (Modeled on Lay §1.1, Example 1.)

\begin{aligned} x_1 + x_2 + 2x_3 &= 5 \\ 2x_1 + 3x_2 + x_3 &= -1 \\ -x_1 + x_2 + 3x_3 &= 6 \end{aligned}

Show a hint

Clear column 1 with $R_2 \leftarrow R_2 - 2R_1$ and $R_3 \leftarrow R_3 + R_1$ . Then use row 2 to clear below its pivot.

Show the solution

\begin{aligned} \left[\begin{array}{rrr|r} 1 & 1 & 2 & 5 \\ 2 & 3 & 1 & -1 \\ -1 & 1 & 3 & 6 \end{array}\right] &\sim \left[\begin{array}{rrr|r} 1 & 1 & 2 & 5 \\ 0 & 1 & -3 & -11 \\ 0 & 2 & 5 & 11 \end{array}\right] && R_2 - 2R_1,\ R_3 + R_1 \\ &\sim \left[\begin{array}{rrr|r} 1 & 1 & 2 & 5 \\ 0 & 1 & -3 & -11 \\ 0 & 0 & 11 & 33 \end{array}\right] && R_3 - 2R_2 \end{aligned}

Row 3 says $11x_3 = 33$ , so $x_3 = 3$ . Row 2 gives $x_2 - 9 = -11$ , so $x_2 = -2$ . Row 1 gives $x_1 - 2 + 6 = 5$ , so $x_1 = 1$ . Check the third equation: $-1 - 2 + 9 = 6$ .

Find the general solution of the system whose augmented matrix is $\left[\begin{array}{rrr|r} 1 & -2 & 3 & 5 \\ 2 & -4 & 5 & 7 \end{array}\right]$ . Then enter the solution with $x_2 = 0$ . (Modeled on Lay §1.2 #7.)

Show a hint

After $R_2 \leftarrow R_2 - 2R_1$ , the second row has its leading entry in column 3, so column 2 has no pivot.

Show the solution

\left[\begin{array}{rrr|r} 1 & -2 & 3 & 5 \\ 2 & -4 & 5 & 7 \end{array}\right] \sim \left[\begin{array}{rrr|r} 1 & -2 & 3 & 5 \\ 0 & 0 & -1 & -3 \end{array}\right] \sim \left[\begin{array}{rrr|r} 1 & -2 & 0 & -4 \\ 0 & 0 & 1 & 3 \end{array}\right]

The second step is $R_2 \leftarrow -R_2$ followed by $R_1 \leftarrow R_1 - 3R_2$ . The pivots are in columns 1 and 3, so $x_2$ is free:

\begin{cases} x_1 = -4 + 2x_2 \\ x_2 \text{ is free} \\ x_3 = 3 \end{cases}

With $x_2 = 0$ the solution is $(-4, 0, 3)$ .

For which $h$ is the system with augmented matrix $\left[\begin{array}{rr|r} 1 & h & 3 \\ 2 & 8 & 5 \end{array}\right]$ inconsistent? (Modeled on Lay §1.1 #19.)

Show a hint

Do one replacement to reach echelon form, then ask when the second row reads $0 =$ a nonzero number.

Show the solution

$R_2 \leftarrow R_2 - 2R_1$ gives the row $(0,\ 8 - 2h,\ 5 - 6) = (0,\ 8 - 2h,\ -1)$ . When $h = 4$ this row says $0 = -1$ , so the system is inconsistent. For every other $h$ the row has a pivot and the solution is unique.

Do the three lines $x_1 + x_2 = 3$ , $\ 2x_1 - x_2 = 0$ and $x_1 - 2x_2 = -3$ pass through one common point? If so, enter it. (Modeled on Lay §1.1 #17.)

Show a hint

Row reduce the $3 \times 3$ augmented matrix and look for a row $[\,0\ \ 0 \mid b\,]$ with $b \neq 0$ .

Show the solution

\begin{aligned} \left[\begin{array}{rr|r} 1 & 1 & 3 \\ 2 & -1 & 0 \\ 1 & -2 & -3 \end{array}\right] &\sim \left[\begin{array}{rr|r} 1 & 1 & 3 \\ 0 & -3 & -6 \\ 0 & -3 & -6 \end{array}\right] && R_2 - 2R_1,\ R_3 - R_1 \\ &\sim \left[\begin{array}{rr|r} 1 & 1 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 0 \end{array}\right] && R_3 - R_2 \end{aligned}

No row says $0 = b$ with $b \neq 0$ , so the system is consistent. Row 2 gives $x_2 = 2$ and row 1 gives $x_1 = 1$ . All three lines pass through $(1, 2)$ .

Row reduce $\begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \\ 3 & 7 & 10 \end{bmatrix}$ to reduced echelon form and enter it row by row. (Modeled on Lay §1.2 #3.)

Show a hint

After clearing column 1, rows 2 and 3 turn out to be equal.

Show the solution

\begin{aligned} \begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \\ 3 & 7 & 10 \end{bmatrix} &\sim \begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{bmatrix} && R_2 - 2R_1,\ R_3 - 3R_1 \\ &\sim \begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} && R_3 - R_2 \\ &\sim \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} && R_1 - 2R_2 \end{aligned}

The pivot columns are 1 and 2.

Challenge

For the system $x_1 + 3x_2 = 2$ , $\ 4x_1 + hx_2 = k$ , find the values of $h$ and $k$ that give infinitely many solutions. (Modeled on Lay §1.2 #19.)

Show a hint

Reach echelon form with one replacement. Infinitely many solutions needs a consistent system with a free variable.

Show the solution

$R_2 \leftarrow R_2 - 4R_1$ reaches echelon form.

\left[\begin{array}{rr|r} 1 & 3 & 2 \\ 4 & h & k \end{array}\right] \sim \left[\begin{array}{rr|r} 1 & 3 & 2 \\ 0 & h - 12 & k - 8 \end{array}\right]

If $h \neq 12$ , row 2 has a pivot and the solution is unique. If $h = 12$ and $k \neq 8$ , row 2 says $0 = k - 8 \neq 0$ , so there is no solution. If $h = 12$ and $k = 8$ , row 2 is all zeros, $x_2$ is free, and there are infinitely many solutions.

True or false: if a linear system has a free variable, then it has infinitely many solutions. (Modeled on Lay §1.2 #22.)

Explain why "multiply a row by $0$ " is not allowed as a row operation. Give a system where doing it would create solutions that the original system does not have.

Show a hint

Take a system with exactly one solution, turn one of its rows into zeros, and count the solutions of what is left.

Show the solution

Every allowed operation can be undone, which is why it keeps the solution set the same. Multiplying a row by $0$ replaces it with $0 = 0$ , and no operation can recover the original row from zeros, so the argument breaks down.

For example, $x_1 + x_2 = 2$ , $\ x_1 - x_2 = 0$ has the single solution $(1, 1)$ . Multiplying row 2 by $0$ leaves only $x_1 + x_2 = 2$ , which is also solved by $(2, 0)$ , $(0, 2)$ and every other point on that line. Solutions were gained, so the new system is not equivalent to the old one.