Choosing Pivot Positions During Reduction

Choosing a Pivot Without Creating Extra Work

In row reduction, a pivot is a nonzero entry used to organize a row and eliminate entries in its column. The arithmetic can depend substantially on which available entry is chosen. A zero entry cannot serve as a pivot, and dividing by a pivot that is an awkward fraction may create avoidable work. Choosing a convenient nonzero entry, often by swapping rows, keeps the reduction valid while making the calculations easier to follow.

At any stage, some rows have already been used to establish pivots. The rows not yet used are the active rows. When searching for a pivot in a particular column, examine only its entries in the active rows. If an active entry is nonzero, it can be placed in the next pivot row by a row swap. If all active entries in that column are zero, there is no pivot to use there, so the search moves to a later column. Row swaps, nonzero row scalings, and row replacements are elementary row operations; each is reversible, so applying one does not change the solution set of a linear system.

Once a candidate is chosen, there is no requirement to select the first nonzero entry from the top. Any available nonzero entry works mathematically. For hand calculations, prefer one that makes the elimination simple: a pivot of \(1\) avoids division when eliminating, while a pivot that divides the other entries in its column can also keep the arithmetic integral. If several candidates are equally convenient, choosing the topmost one avoids a swap.

The Local Rule for a Valid Pivot

Proof. Assume first that \(a_{kj}\ne0\) for some \(k\ge r\). If \(k\ne r\), swapping rows \(k\) and \(r\) places that nonzero entry in row \(r\); if \(k=r\), no swap is needed. Thus \(p=a_{rj}\ne0\). For an active row \(i>r\), write \(a=a_{ij}\). The specified replacement changes its entry in column \(j\) to \(a-(a/p)p=0\). Since \(p\ne0\), the replacement is a row replacement by a multiple of another row, which is reversible by adding that same multiple back. The swap, when used, is reversible as well. Therefore these operations preserve the solution set. In the other case, every entry \(a_{ij}\) with \(i\ge r\) is zero by assumption, so none of those entries can be selected as a nonzero pivot. \(\square\)

The theorem concerns one step of a reduction; repeating such steps places pivots in successive rows and clears entries below them. In a system written as an augmented matrix, row operations apply to the entire row, including the right-hand side. A pivot should therefore be selected from the coefficient columns, not from the augmented column. The focus here is the practical choice of pivot and the arithmetic of elimination, rather than interpreting the resulting solution set.

Keeping Elimination Fraction-Free

The usual elimination step \(R_i\to R_i-(a/p)R_r\) uses the fraction \(a/p\) when the pivot is \(p\) and the target entry is \(a\). That is often the clearest choice, especially when the quotient is simple. If it is awkward, there is another valid option: multiply the target row by \(p\), then subtract \(a\) times the pivot row. This replaces the target row by \(pR_i-aR_r\), whose entry in the pivot column is zero. The target row is scaled by a nonzero number, so this alternative can leave larger entries even as it avoids fractions. It is a choice for convenience, not a requirement.

Proof. The hypothesis \(i\ne k\) ensures that changing row \(i\) does not change the pivot row \(k\). First scale row \(i\) by \(p\), which is allowed because \(p\ne0\). Then add \(-a\) times row \(k\) to row \(i\). The resulting row is \(pR_i-aR_k\), using the original rows on the right. In the chosen column its entry is \(pa-ap=0\). Both operations are reversible: undo the row addition, then scale by \(1/p\). Thus the replacement is valid and preserves the solution set. \(\square\)

After a fraction-free step, it may be useful to divide a row by a common nonzero factor before continuing. This is another reversible row scaling. Compare the sizes of the numbers and the likely next steps rather than trying to avoid every division at any cost.

When a Column Has No Available Pivot

A column may contain nonzero entries in rows already used for pivots but only zeros in the active rows. Those upper entries do not create a new pivot at the current stage. Do not divide by zero, and do not try to swap a zero active entry into the pivot row. Move to the next column and continue looking among the active rows. The skipped column simply has no pivot position in this reduction.

Common Mistakes and Practical Checks

Dividing by a zero candidate is invalid. For example, starting with the first row of \(\begin{bmatrix}0&1&2\\1&1&3\end{bmatrix}\) and attempting to scale that row by \(1/0\) is not a row operation. The correction is to swap the two rows first, placing the nonzero entry in the first column of the pivot row, and only then scale if scaling is useful.

Do not use the pivot row as its own target. The fraction-free replacement \(R_i\to pR_i-aR_k\) requires \(i\ne k\). For instance, if row \(k\) has pivot \(p=3\), using that same row as the target gives \(a=3\) and the proposed expression \(3R_k-3R_k=\mathbf{0}\). Replacing a nonzero row by a zero row is not reversible and is not a valid elementary row operation. To eliminate an entry, use a different target row; the pivot row itself is left unchanged.

Before proceeding to the next pivot, check that the chosen pivot is nonzero, that the target rows are different from the pivot row, and that each eliminated entry is actually zero after the operation. In exact hand calculations, recording the row operation beside each matrix makes these checks easier and helps locate arithmetic errors.