Back to the on-screen lesson ·
The three row operations and why each is reversible, the forward sweep to echelon form, back substitution, partial pivoting, and what the whole thing costs.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to carry out a single elimination step correctly, sweep an augmented matrix forward to row echelon form choosing a pivot in each column, repair a zero pivot position by swapping in a row from below, recover every unknown by back substitution from the bottom row upwards, say why each of the three row operations leaves the solution set exactly as it was, and state what the algorithm costs as the system grows.
The last lesson turned a system into an augmented matrix and stopped there. The reason for doing it was that three operations on the equations leave the solution set alone, and none of them looks at the variable names. This lesson is those three operations applied in a fixed order, until the matrix has a shape you can read an answer out of.
A pivot is the first non-zero entry of a row, once elimination has reached that row. A matrix is in row echelon form when every row's pivot lies strictly to the right of the pivot of the row above, and any all-zero rows are at the bottom. The forward sweep is the process that produces echelon form; back substitution is the upward pass that reads the unknowns out of it. Partial pivoting is the choice of which row to bring into the pivot position when several could serve.
Gaussian elimination is two passes over the same matrix.
The forward sweep goes down and to the right. Take the leading entry of the top row as the pivot; for each row below, subtract whatever multiple of the pivot row makes that row's entry in the pivot column become zero. Then move down one row and right one column, and do it again. When you run out of rows or columns, the matrix is in echelon form: a staircase of pivots descending to the right, with zeros underneath.
Back substitution goes up. The bottom non-zero row of an echelon form has exactly one unknown in it, so it hands you a value. Rising one row introduces exactly one unknown you have not yet found, and the ones you have are substituted in. Each row gives up one unknown, and the pass ends at the top.
The reason the answer is the right answer is the three operations. Swapping two rows, multiplying a row by a non-zero number, and adding a multiple of one row to another are all reversible, and a reversible operation cannot change a solution set: if it lost a solution the inverse operation would have to create one from nothing, and none of these three creates anything.
Note what is not on the list. Multiplying a row by zero is not a row operation, because it is not reversible, and it destroys an equation. Adding a multiple of a row to itself is a scaling in disguise, and by a factor that can be zero.
Another way: picture
Picture the augmented matrix as a staircase being built. Each forward step nails one more entry to zero and never disturbs a zero already placed, because every subtraction uses a pivot row whose own leading entries are already zero to the left. That is why the work never has to be redone: the zeros accumulate. Back substitution then walks down the finished staircase in the other direction, one tread at a time, and each tread is one equation in one new unknown.
Another way: steps
A zero where the pivot should be is not an error and not a reason to stop. No multiple of the current row can put a non-zero entry into that column, because the current row already has a zero there — so look down the column instead.
Numerically there is a stronger version of the same choice. Even when the pivot is non-zero, dividing by a very small pivot magnifies every rounding error that has accumulated, so a working implementation swaps in the row with the largest entry in the column whether or not the pivot was zero. That is partial pivoting, and by hand it has a friendlier motive: swapping a $1$ into the pivot position keeps the arithmetic in whole numbers.
Clearing one entry below a pivot costs one multiplication and one subtraction per column remaining. Adding those up over an $n \times n$ system, the forward sweep costs about $\dfrac{2n^3}{3}$ arithmetic operations and back substitution about $n^2$ — so essentially all of the work is the forward sweep, and the cost grows with the cube of the size.
That single fact decides a great deal later:
Changing the pivot row while using it. The pivot row is read from, not written to, during a step. Subtracting row 2 from row 1 and row 1 from row 2 in the same breath loses information irrecoverably.
Scaling a row by zero. It is not one of the three operations. It replaces an equation with $0 = 0$, which every point satisfies, so the solution set grows — the one thing elimination must never do.
Treating a zero pivot as a failure. It means swap, or move right. It never means the system has no solution: that verdict comes only from a row reading $0 = c$ with $c$ non-zero, and it comes at the end.
Back-substituting too early. An echelon form is what makes the bottom row have one unknown. Substituting into a matrix that is not yet in echelon form is solving the original system by hand, with the matrix as decoration.
Forgetting the augmented column. A row operation acts on the whole row, right-hand side included. Clearing the coefficients and leaving the constants behind produces a tidy matrix that answers a different question.
$\left(\begin{array}{rrr|r} 1 & 2 & 1 & 6 \\ 2 & 5 & 3 & 16 \\ 1 & 3 & 4 & 14 \end{array}\right)$: subtract $2 \times$ row 1 from row 2, and row 1 from row 3.
One pivot, two subtractions.
$\left(\begin{array}{rrr|r} 1 & 2 & 1 & 6 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 3 & 8 \end{array}\right)$: now the pivot is the $1$ in row 2, column 2. Subtract row 2 from row 3.
Move down one, right one.
$\left(\begin{array}{rrr|r} 1 & 2 & 1 & 6 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 2 & 4 \end{array}\right)$: echelon form. The bottom row gives $z = 2$, then $y = 2$, then $x = 6 - 4 - 2 = 0$.
Now, and only now, substitute upwards.
$\left(\begin{array}{rrr|r} 0 & 1 & 2 & 3 \\ 2 & 4 & 1 & 7 \\ 1 & 1 & 1 & 3 \end{array}\right)$: the pivot position is zero, and no multiple of row 1 can change that.
Look down the column.
Swap rows 1 and 2: $\left(\begin{array}{rrr|r} 2 & 4 & 1 & 7 \\ 0 & 1 & 2 & 3 \\ 1 & 1 & 1 & 3 \end{array}\right)$. Swapping rows 1 and 3 instead would also have worked, and would have kept the arithmetic in whole numbers.
Any non-zero entry will do; some are pleasanter.
Subtract $\tfrac{1}{2} \times$ row 1 from row 3 and carry on. The order of the equations was never part of the problem, so nothing has been given up.
A swap is free.
Subtract $\tfrac{3}{2} \times$ row 1 from row 2: the first column clears.
One pivot, one subtraction.
Row 2 becomes $0$, $1 - 6 = -5$, $5 - 15 = -10$.
Remember the augmented column.
So $-5y = -10$ and $y = 2$; back-substituting gives $2x + 8 = 10$, so $x = 1$.
Carry out one elimination step on $\begin{pmatrix} 1 & 6 & 1 \\ 4 & 1 & 9 \end{pmatrix}$: subtract $4$ times row 1 from row 2, and write the result.
This task has no paper form; do it on a device.
Put the stages of Gaussian elimination into the order they are carried out.
Number the steps in order (write the number in the box):
The system is already in echelon form: $5x + 2y + 5z = 47$, $4y + 2z = 32$, $4z = 16$. Find $x$.
Answer:
Match each row operation to the operation that undoes it.
| Swap row 1 and row 2 | Multiply row 2 by $\dfrac{1}{6}$ | Subtract $6$ times row 1 from row 3 | Multiply row 2 by $6$ a second time | |
|---|---|---|---|---|
| Swap row 1 and row 2 | ||||
| Multiply row 2 by $6$ | ||||
| Add $6$ times row 1 to row 3 |
Elimination has reached $\begin{pmatrix} 0 & 8 & 9 \\ 2 & 7 & 3 \end{pmatrix}$, and the pivot position holds a zero. Write the matrix after the repair.
This task has no paper form; do it on a device.
With $u = (4, 3)$, $v = (1, 1)$ and $w = (9, 7)$, there is exactly one pair of numbers with $w = xu + yv$. Find $x$.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Carry out one elimination step on $\begin{pmatrix} 1 & 2 & 2 \\ 6 & 7 & 7 \end{pmatrix}$: subtract $6$ times row 1 from row 2, and write the result.
This task has no paper form; do it on a device.
You can reduce a system to echelon form and back-substitute, and you can say what to do when a pivot position holds a zero. Say in your own words why a reversible operation cannot change a solution set. Next: what happens when the sweep is carried further, and how the solution set is read off the result.
10. Your turn: sweep $\left(\begin{array}{rr|r} 2 & 4 & 10 \\ 3 & 1 & 5 \end{array}\right)$ forward and find $y$, step 3
Bottom row first, then rise.