Linear Algebra › Section A · Linear equations in linear algebra › Topic A.2
Row reduction and echelon forms
Elimination works best as a fixed routine that ends in a standard shape. Echelon forms are those shapes, and from them you can read off at a glance whether a system has no solution, one, or infinitely many.
From tricks to an algorithm
In Systems of linear equations, elimination meant choosing row operations by eye. That works for small systems, but a computer, or a tired student, needs a procedure that never depends on luck. Row reduction is that procedure. It always ends in a matrix of a standard staircase shape, and the shape answers both fundamental questions, existence and uniqueness, before any solving is done. The ideas here apply to any matrix, not only to augmented matrices, which is why they recur throughout the course.
Echelon form
In a matrix, a non-zero row is a row with at least one non-zero entry, and its leading entry is its leftmost non-zero entry. A matrix is in echelon form when three things hold. 1. Every non-zero row lies above every row of zeros. 2. Each leading entry sits in a column to the right of the leading entry in the row above. 3. Every entry below a leading entry is zero. The leading entries therefore form a staircase descending to the right. A matrix in echelon form is easy to solve by back substitution, as the worked examples in the previous topic showed.
Reduced echelon form
A matrix is in reduced echelon form, often called RREF, when it is in echelon form and also: 4. Every leading entry is 1. 5. Each leading 1 is the only non-zero entry in its column. A key theorem says that each matrix is row equivalent to one and only one reduced echelon matrix. Ordinary echelon forms are not unique, since you can always scale a row or add a lower row to a higher one and keep the staircase. The reduced form is unique, so two people who row reduce the same matrix correctly always reach the same RREF.
Pivot positions and pivot columns
A pivot position is a location in a matrix that holds a leading 1 in its reduced echelon form. A pivot column is a column that contains a pivot position. Because the RREF is unique, the pivot positions are fixed by the matrix itself, and every echelon form of the matrix has its leading entries in exactly those positions. So you can find the pivot positions from any echelon form, without finishing the reduction. A non-zero number placed in a pivot position and used to create zeros is called a pivot.
The row reduction algorithm
The forward phase produces an echelon form. 1. Take the leftmost non-zero column; it is a pivot column, with its pivot position at the top. 2. If needed, interchange rows so that a non-zero entry sits in that position. 3. Use replacements to create zeros below it. 4. Cover that row and every row above it, and repeat steps 1 to 3 on the rows below. The backward phase produces the reduced form. 5. Working from the rightmost pivot up and to the left, scale each pivot row to make the pivot 1 and use replacements to create zeros above it. Running both phases is called Gauss-Jordan elimination.
Worked example: reducing to RREF
Row reduce
1. Column 1 is the pivot column, but its top entry is 0, so interchange rows 1 and 2. 2. Row 3 minus 2 times row 1 gives \((0, -1, -2, -3)\). 3. Scale row 2, now \((0, 2, 4, 6)\), by \(\frac{1}{2}\) to get \((0, 1, 2, 3)\). 4. Row 3 plus row 2 gives \((0, 0, 0, 0)\). The matrix is now in echelon form, with pivots in columns 1 and 2. 5. Backward phase: row 1 minus 3 times row 2 gives \((1, 0, -1, 2)\). The RREF has rows \((1, 0, -1, 2)\), \((0, 1, 2, 3)\) and \((0, 0, 0, 0)\).
Basic and free variables
Read the example as the augmented matrix of a system in \(x_1, x_2, x_3\). Variables in pivot columns are basic variables; the others are free variables. Here \(x_1\) and \(x_2\) are basic and \(x_3\) is free. The RREF says \(x_1 - x_3 = 2\) and \(x_2 + 2x_3 = 3\), so the general solution is \(x_1 = 2 + x_3\), \(x_2 = 3 - 2x_3\), with \(x_3\) free to be any real number. This is a parametric description of the solution set. Taking \(x_3 = 1\) gives \((3, 1, 1)\), and substituting into the original rows confirms \(2 + 4 = 6\), \(3 + 3 + 5 = 11\) and \(6 + 5 + 8 = 19\).
The existence and uniqueness theorem
A linear system is consistent exactly when the rightmost column of its augmented matrix is not a pivot column, that is, when no echelon form has a row \((0, \dots, 0, b)\) with \(b \ne 0\). If the system is consistent, then it has a unique solution when there are no free variables, and infinitely many solutions when there is at least one free variable. So the full procedure is: reduce to echelon form, check the last column, and if the system is consistent, count the free variables. The reduced form is only needed when you want the solutions themselves.
Worked example: a system with a parameter
For which values of \(h\) is the system \(x + 2y = 4\), \(3x + 6y = h\) consistent? 1. The augmented matrix has rows \((1, 2, 4)\) and \((3, 6, h)\). 2. Row 2 minus 3 times row 1 gives \((0, 0, h - 12)\). 3. If \(h \ne 12\), this row says \(0 = h - 12\) with the right side non-zero, so the system is inconsistent. 4. If \(h = 12\), the row is all zeros, the system is consistent, and \(y\) is free, so there are infinitely many solutions. Geometrically, the lines are parallel unless \(h = 12\), when they coincide.
Row reduction on a computer
For an \(n \times n\) system, the forward phase needs roughly \(\frac{2}{3}n^3\) arithmetic operations, far more than the backward phase, so doubling the number of unknowns multiplies the work by about 8. Computers also round every number, and dividing by a tiny pivot can magnify those errors. Partial pivoting avoids this: in each pivot column, the program swaps up the entry of largest absolute value before creating zeros. Software usually stops at an echelon form and back substitutes, rather than writing out the full RREF.
Common mistakes to avoid
First, treating any echelon form as unique: only the reduced form is. Second, calling the last column of an augmented matrix a free variable; it holds constants, and a pivot there signals inconsistency. Third, counting free variables before checking consistency: free variables give infinitely many solutions only if a solution exists. Fourth, deciding that a zero row means no solution; a row of all zeros is harmless. Fifth, losing signs when moving free variables to the right-hand side, as in \(x_2 = 3 - 2x_3\).
Key takeaways
Echelon form is a staircase of leading entries with zeros below; reduced echelon form adds leading 1s that are alone in their columns. Every matrix has exactly one RREF, so its pivot positions are fixed. The forward phase reaches echelon form and the backward phase reaches RREF. Pivot-column variables are basic; the rest are free. A system is consistent exactly when the last column is not a pivot column, and a consistent system has a unique solution exactly when it has no free variables.
Flashcards
Flashcard
The leftmost non-zero entry of a non-zero row
Test your understanding
Question 1 of 5
Which matrix is in reduced echelon form?
Question 2 of 5
A consistent system in x₁, x₂, x₃, x₄ has an augmented matrix whose pivots lie in columns 1, 2 and 4. How many free variables are there?
Question 3 of 5
For which values of h is the system x − 3y = 5, −2x + 6y = h consistent?
Question 4 of 5
A reduced echelon form has rows (1, 0, −2, 4), (0, 1, 3, −1), (0, 0, 0, 0) for a system in x₁, x₂, x₃. What is the general solution?
Question 5 of 5
Which statement about echelon forms is true?
