Why Row Reduction Changes Over a Finite Field
Gaussian elimination follows the same broad plan over the real numbers and over a finite field: find a nonzero entry to use as a pivot, eliminate entries in its column, and continue. What changes is the arithmetic. Over a finite field, every addition, subtraction, and multiplication is performed modulo a prime, and dividing by a nonzero entry means multiplying by its modular inverse. The allowed row operations must therefore be interpreted in that field.
Let \(p\) be prime. The field \(\mathbb{F}_p\) consists of the residue classes modulo \(p\), represented by \(0,1,\dots,p-1\). Computations are reduced modulo \(p\): for example, in \(\mathbb{F}_5\), \(3+4=2\), since \(7\) and \(2\) have the same remainder modulo \(5\). Every nonzero element has a multiplicative inverse. For instance, \(2^{-1}=3\) in \(\mathbb{F}_5\), because \(2\cdot3=6=1\) modulo \(5\).
Multiplying a row by a nonzero field element is allowed because that element has an inverse, so the operation can be undone. Multiplying a row by zero is not allowed: it can destroy information and cannot be reversed. As over \(\mathbb{R}\), a matrix is in reduced row echelon form (RREF) when each nonzero row begins with a leading \(1\), each leading \(1\) is the only nonzero entry in its column, and the leading \(1\)s move strictly to the right as one moves down the nonzero rows. Any zero rows are at the bottom.
Why the Row Operations Are Legitimate
Proof. An augmented matrix represents a system whose rows are equations. Interchanging two rows only changes their order, so it preserves the solutions. Multiplying an equation by a nonzero scalar preserves its solutions: an equation \(L=b\) is equivalent to \(cL=cb\) when \(c\ne0\), since multiplication by \(c^{-1}\) reverses the change. Replacing one row by itself plus \(c\) times another row also preserves solutions. Every solution of the original equations satisfies this new equation by addition; conversely, subtracting \(c\) times the unchanged other equation recovers the original equation. Each operation is reversible, so the full solution sets before and after the operation are equal. \(\square\)
This result explains the algorithm, not just the notation. At a stage of elimination, a nonzero entry in the active part of a column can be moved to the pivot row. It can be scaled to \(1\) using its inverse, and row replacements can clear the other entries in that column. The column is then finished, and the process continues with the rows below and columns to the right. Because each pivot uses a new row and a new column, there can be at most as many pivots as there are rows or columns. If a column has no nonzero entry available in the active rows, it is skipped; it does not supply a pivot.
Worked Example: Find Pivots and Homogeneous Solutions in \(\mathbb{F}_5\)
Reduce the matrix over \(\mathbb{F}_5\), identify its pivot columns, and describe the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{0}\), where
Swap the first two rows. Then multiply the first row by \(3\), the inverse of \(2\) in \(\mathbb{F}_5\). Next, subtract \(4\) times the first row from the third row. All entries below are reduced modulo \(5\).
For the last entry calculation, \(2-4\cdot3=2-12=-10=0\) modulo \(5\). Clear the entry above the second pivot by replacing \(R_1\) with \(R_1-3R_2\): its third entry becomes \(0-3\cdot2=-6=4\) modulo \(5\).
The pivot columns are columns 1 and 2; column 3 has no pivot. The reduced homogeneous system is \(x_1+4x_3=0\), \(x_2+2x_3=0\). Set the free variable \(x_3=t\in\mathbb{F}_5\). Then \(x_1=-4t=t\) and \(x_2=-2t=3t\), so the solutions are \(\mathbf{x}=t(1,3,1)^{\top}\).
Check: for the vector \((1,3,1)^{\top}\), the three original row products are \(3+2=5=0\), \(2+3=5=0\), and \(4+6=10=0\) in \(\mathbb{F}_5\). Thus \(\mathbf{A}(1,3,1)^{\top}=\mathbf{0}\); multiplying this solution by any \(t\in\mathbb{F}_5\) also gives a solution.
Reading Pivots and Free Variables
For a system with \(n\) variables, the coefficient columns correspond to those variables in their original order. In RREF, a variable corresponding to a pivot column is a pivot variable; a variable corresponding to a column without a pivot is a free variable. In a homogeneous system, the pivot variables are determined by the free variables. If every column is a pivot column, there are no free variables and the only homogeneous solution is the zero vector. If a column has no pivot, assigning a nonzero value to one free variable gives a nonzero solution after the pivot variables are determined.
Proof. Each nonzero row has a leading \(1\) in a pivot column, and that pivot is the only nonzero entry in its column. In the equation represented by that row, the pivot variable therefore equals the negative of a sum of terms involving only nonpivot variables: no other pivot variable appears. Choose any values for all free variables. Each row then prescribes one value for its pivot variable, so this choice extends to a solution, and the prescribed values are unique. If there are no free variables, every row equation sets its pivot variable to \(0\), and every column is a pivot column, so \(\mathbf{x}=\mathbf{0}\). If there is a free variable, set one of them to \(1\) and all other free variables to \(0\); the row equations determine the pivot variables, and the resulting solution is nonzero because its chosen free coordinate is \(1\). \(\square\)
For a nonhomogeneous system, row-reduce the augmented matrix, which includes the right-hand side as its final column. A row of the form \([0\ \cdots\ 0\mid c]\), where \(c\ne0\), represents \(0=c\) and makes the system inconsistent. If there is no such row, the system is consistent: each pivot row determines its pivot variable in terms of the right-hand side and any free variables. In a consistent system, no free variables means one solution; at least one free variable means multiple solutions. The proof is the same row-by-row determination as in the homogeneous case, with the right-hand-side entry included in each equation.
Worked Example: A Row Swap and a Unique Solution in \(\mathbb{F}_3\)
Reduce the augmented matrix and solve the system over \(\mathbb{F}_3\).
Swap the first two rows. Replace the third row by itself minus the first row; this gives \([0,1\mid2]\), because \(2-1=1\) modulo \(3\). Then subtract the second row from the third, and subtract the second row from the first.
There is a pivot in each coefficient column and no contradictory row. Thus \(x_1=1\), \(x_2=2\), with no free variables. The proposed solution is \((1,2)^{\top}\).
Check: In the original system, the first equation is \(x_2=2\); the second is \(x_1+x_2=1+2=0\) modulo \(3\); and the third is \(x_1+2x_2=1+4=5=2\) modulo \(3\). All three right-hand sides match.
Worked Example: Detecting an Inconsistent System in \(\mathbb{F}_5\)
Determine whether this system has a solution over \(\mathbb{F}_5\):
Replace the second row by itself minus \(2\) times the first. The first two entries become \(2-2=0\) and \(4-4=0\); the last becomes \(2-6=-4=1\) modulo \(5\).
The second row says \(0=1\) in \(\mathbb{F}_5\), so there is no solution. This is not a matter of free variables: the augmented column has a pivot where the coefficient part has a zero row, producing a contradiction.
Check: The first equation gives \(x_1+2x_2=3\). Doubling it would require \(2x_1+4x_2=6=1\) modulo \(5\), but the second equation requires that same left-hand side to equal \(2\). Since \(1\ne2\) in \(\mathbb{F}_5\), the equations cannot both hold.
A Common Modular-Arithmetic Pitfall
Do not divide by an ordinary integer without finding its field inverse. Consider normalizing the row \([2\ \ 1\mid4]\) over \(\mathbb{F}_5\). A wrong calculation treats division by \(2\) as ordinary rational division and writes \([1\ \ \tfrac12\mid2]\). But \(\tfrac12\) is not an entry of \(\mathbb{F}_5\), and this calculation does not express a row of the matrix over that field. The correct operation multiplies by \(2^{-1}=3\):
Another useful check is that each row operation must be reversible. A row swap reverses itself, scaling by \(c\ne0\) reverses by scaling by \(c^{-1}\), and adding \(c\) times one row to another reverses by adding \(-c\) times that row. If a proposed operation is not reversible in the field, it is not a valid elimination step.
Row reduction over \(\mathbb{F}_p\) is therefore a finite-field version of a familiar computational method, but the field determines which arithmetic is legal and which entries are nonzero. To make the result interpretable, keep the coefficient columns in their original order, track the augmented column when solving a system, and distinguish a missing pivot from a contradictory row. The former produces a free variable when the system is consistent; the latter means there are no solutions.
Check Your Understanding
For each question, carry out the arithmetic in the stated field and verify any proposed solution in the original equations.
- In \(\mathbb{F}_7\), what scalar multiplies a row with leading entry \(3\) to make that entry \(1\)?
- Reduce \(\begin{bmatrix}1&2\\2&4\end{bmatrix}\) over \(\mathbb{F}_5\). State its pivot columns and describe the solutions of the associated homogeneous system.
- In \(\mathbb{F}_3\), determine whether the system \(x_1+x_2=1,\;2x_1+2x_2=0\) is consistent.
- Explain why multiplying a row by zero is not an elementary row operation.
- What does a row \([0\ \ 0\mid2]\) imply for an augmented system over \(\mathbb{F}_5\)?
