What Forward Elimination Does
Forward elimination is a systematic way to simplify a linear system. Starting with its augmented matrix, we work from left to right through the columns, using row swaps and row replacements to create zeros below successive pivots. The goal is echelon form, not yet a fully solved system: forward elimination organizes the equations so that later work can begin from the bottom row and move upward.
An augmented matrix records the coefficients of the variables followed by the right-hand-side column. For example, the system \(2x+y=4\), \(x+3y=5\) has augmented matrix \(\begin{bmatrix}2&1&4\\1&3&5\end{bmatrix}\). Each row represents one equation. The vertical divider is often shown in print, but here a comma separates the coefficient entries from the right-hand side.
A pivot in forward elimination is the nonzero entry chosen to lead a row. To clear an entry beneath a pivot \(a\), the basic replacement is \(R_k\to R_k-cR_i\), where row \(i\) contains the pivot and \(c\) is chosen so that the entry in row \(k\) becomes zero. A row swap, \(R_i\leftrightarrow R_j\), can move a nonzero entry into the row where the next pivot is needed. These operations act on the entire row, including the right-hand side.
For a system, the rows of its augmented matrix are equations. Swapping two rows changes only their order. Replacing one row by itself plus a multiple of another equation preserves the set of solutions, because the replacement can be undone by subtracting that same multiple. Thus the operations in forward elimination keep the system equivalent to the original one. We will use that fact as we compute.
A Reliable Forward-Elimination Routine
At each stage, look in the next column for a nonzero entry in the rows not yet used for pivots. If the current row already has a nonzero entry there, use it as the pivot. If not, swap in a row that does. Then eliminate the entries below the pivot, one at a time. If the column has no nonzero entry in any remaining row, move to the next column instead. Do not multiply a row by a constant unless there is a specific reason to: a pivot does not have to equal \(1\).
In the next column, find a nonzero entry among the rows still being processed. Swap its row into the current pivot position if necessary.
For each row below the pivot, choose a multiple of the pivot row that makes the entry in the pivot column zero. Apply the replacement to every entry of that row.
Continue with the rows below and columns to the right. Stop when there are no more columns or no more rows to process.
Theorem (Forward-elimination justification). Applying this procedure to an augmented matrix produces a row-equivalent matrix in row echelon form. Consequently, the resulting matrix represents a system with the same solutions as the original system.
Proof. A row swap is reversible: swapping the same two rows again restores the original matrix. A replacement \(R_k\to R_k+cR_i\), with \(i\ne k\), is also reversible by applying \(R_k\to R_k-cR_i\); row \(i\) has not changed. Each step is therefore a reversible row operation, so the resulting matrix is row-equivalent to the original. The corresponding equations have the same solutions: a swap reorders equations, and a replacement combines equations in a way that can be undone.
It remains to check the form produced. Whenever a column contains a nonzero entry in an unprocessed row, the procedure moves such an entry to the current pivot row and clears every entry below it. The next pivot, if one is found, is in a column to the right and a row below the previous pivot. A column with no available nonzero entry is skipped; it cannot provide a pivot at that stage. Thus the pivots move strictly down and to the right, with zeros below each pivot. When no more rows or columns remain, any rows with no nonzero entries are at the bottom: if an unprocessed row has any nonzero entry, the procedure can use the first such column to produce a pivot row above any rows that are zero. These are precisely the echelon conditions. \(\square\)
Worked Reductions
Worked Example: Swap for the First Pivot
Use forward elimination on the augmented matrix below. Its first row begins with zero, so swap it with the second row to place a nonzero entry in the first pivot position.
The pivot in column 1 is \(2\). To eliminate the \(4\) beneath it, replace row 3 by \(R_3-2R_1\). Entry by entry, the new row is \((4-2\cdot2,\;3-2\cdot1,\;5-2\cdot1,\;12-2\cdot4)=(0,1,3,4)\).
Now use the pivot \(1\) in row 2, column 2. Subtract row 2 from row 3. The entries become \((0-0,\;1-1,\;3-2,\;4-5)=(0,0,1,-1)\).
The leading entries are in columns 1, 2, and 3, with zeros below each. The matrix is in echelon form. Check: the first two rows are the original second and first rows, respectively. The final row is the original third row minus twice the original second row minus the original first row:
This confirms the final row arithmetic; the swaps and replacements used are all reversible, so the reduction preserves the original system’s solutions.
Worked Example: Clear Entries Without Swapping
Reduce the following augmented matrix to echelon form. The first entry is already nonzero, so use it as the first pivot.
For row 2, subtract twice row 1. The new entries are \((2-2\cdot1,\;5-2\cdot2,\;1-2(-1),\;8-2\cdot3)=(0,1,3,2)\). For row 3, add row 1. The new entries are \((-1+1,\;-1+2,\;2+(-1),\;0+3)=(0,1,1,3)\).
The next pivot is \(1\) in row 2, column 2. Subtract row 2 from row 3. The new row is \((0-0,\;1-1,\;1-3,\;3-2)=(0,0,-2,1)\).
This is echelon form: the leading entries move rightward, and the entries beneath each one are zero. Check: the final row equals the original third row plus three times the original first row minus the original second row:
The second row is the original second row minus twice the original first row. These row combinations agree with the displayed operations, and each operation has an inverse.
Worked Example: A Row Becomes Zero
In this example, the first row has a zero in the first column, so a swap is needed. Then two replacements create the echelon form.
Use \(2\) as the pivot in column 1. Replace row 3 by \(R_3-2R_1\), giving \((4-4,\;3-2,\;2-0,\;11-8)=(0,1,2,3)\).
The pivot in column 2 is \(1\). Subtract row 2 from row 3: \((0-0,\;1-1,\;2-2,\;3-3)=(0,0,0,0)\).
The last row is zero and sits below the two nonzero rows, so the matrix is in echelon form. Check: after the swap, the first row is the original second row and the second row is the original first row. The final row is the original third row minus twice the original second row minus the original first row:
This verifies the zero row directly. It arose because the corresponding equation was made redundant by the other rows; the reduction itself is still justified by reversible row operations.
Common Arithmetic Pitfall
When eliminating an entry, the multiplier must be applied to every entry in the pivot row, including the right-hand side. A common sign error occurs when subtracting a multiple. Suppose the pivot row begins \((1,2,\ldots)\) and the row to be changed begins \((3,5,\ldots)\). To clear the \(3\), use \(R_2\to R_2-3R_1\). The second entry is \(5-3\cdot2=5-6=-1\), not \(1\). Writing \(5-6=1\) gives the wrong row, even though the first entry has been cleared correctly.
The correction is to calculate every component separately: the first becomes \(3-3\cdot1=0\), the second becomes \(-1\), and each later entry and the right-hand side must be computed by the same subtraction rule. A zero in the pivot column is not enough to validate the whole replacement.
Reading the End of Forward Elimination
When the process ends, the matrix need not have pivots in every variable column, and pivots need not equal \(1\). Neither condition is required for echelon form. The immediate purpose is to arrange the equations in a staircase pattern. The later step of using that pattern to determine variable values is back substitution; it is distinct from the row operations carried out here.
Keep these checks in view as you work:
- Choose a nonzero pivot in the next available column, swapping rows if needed.
- Use a row replacement that makes the target entry exactly zero.
- Apply the replacement to every entry in that row, including the right-hand side.
- Move each new pivot strictly to the right of the pivot above it.
- Stop when the augmented matrix has echelon form; do not confuse this stage with solving for all variables.
Check Your Understanding
For each reduction, show the row operation and the resulting augmented matrix. Check the arithmetic in every entry.
- Use a row swap and forward elimination on \(\begin{bmatrix}0&1&2&4\\1&1&0&3\\2&3&2&8\end{bmatrix}\). What echelon form do you obtain?
- For the row \((2,7,-1,5)\) and pivot row \((1,3,2,4)\), compute the new row after \(R_k\to R_k-2R_i\).
- Explain why a row swap does not change the solutions of the system represented by an augmented matrix.
- When the current column has no nonzero entries in the unprocessed rows, what should forward elimination do next?
- Give one reason an echelon-form augmented matrix need not have a \(1\) in every pivot position.
