Why Every Column Must Have a Pivot

From Independence to Pivots

Row reduction turns a matrix into a form where the equations in a homogeneous system are easier to read. The pivot test for independence is not merely a visual shortcut: it works because a missing pivot leaves a variable free, and that free variable can be used to produce a nonzero solution. Conversely, if every column has a pivot, there are no free variables and the homogeneous system has only the zero solution.

Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with columns \(\mathbf{a}_1,\dots,\mathbf{a}_n\). A list of columns is linearly independent when the equation \(x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n=\mathbf{0}\) forces all coefficients \(x_1,\dots,x_n\) to be zero. Writing \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\), the same equation is \(\mathbf{A}\mathbf{x}=\mathbf{0}\). Thus, independence asks whether this homogeneous system has any solution besides \(\mathbf{x}=\mathbf{0}\).

After reducing \(\mathbf{A}\), we use its reduced row echelon form, or RREF. In this form, every nonzero row begins with a leading \(1\); each leading \(1\) is the only nonzero entry in its column; and leading \(1\)s move strictly to the right as we move down the nonzero rows. A column containing a leading \(1\) is a pivot column. A column without a pivot is a free-variable column when we solve the associated system.

The theorem depends on two facts: row operations preserve the solutions of a homogeneous system, and the pivot structure of the RREF determines whether free variables are present. We establish both carefully.

Why Row Reduction Keeps the Same Solutions

An elementary row operation replaces one equation of a system by an equivalent equation. For a homogeneous system, the three allowed operations are swapping two equations, multiplying an equation by a nonzero scalar, and adding a multiple of one equation to another. Each operation can be undone by another allowed operation, so a vector satisfies the equations before the operation exactly when it satisfies them afterward.

Proof. It is enough to check one row operation, because a finite sequence applies this fact repeatedly. Swapping two rows swaps two equations, without changing which vectors satisfy all the equations. Multiplying a row by a nonzero scalar \(c\) replaces an equation \(L(\mathbf{x})=0\) by \(cL(\mathbf{x})=0\); these are equivalent because \(cL(\mathbf{x})=0\) implies \(L(\mathbf{x})=0\) after division by \(c\), and the reverse implication follows by multiplication. Replacing row \(i\) by row \(i\) plus \(c\) times row \(j\) also preserves the solutions: a vector satisfying the original equations satisfies the new one, and a vector satisfying the new equation and the unchanged row \(j\) satisfies the original row \(i\) after subtracting \(c\) times row \(j\). Each operation therefore preserves the solution set. \(\square\)

Consequently, if \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\), then \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{R}\mathbf{x}=\mathbf{0}\) have the same solutions. We can decide independence by reading the simpler system \(\mathbf{R}\mathbf{x}=\mathbf{0}\), without changing the answer to the original question.

How Free Variables Control the Solution

In \(\mathbf{R}\mathbf{x}=\mathbf{0}\), a variable corresponding to a nonpivot column is free: it may be assigned any real value. Each pivot variable is then determined by its pivot equation. More precisely, a pivot equation has the form \(x_j+\sum_{k\in F}r_{ik}x_k=0\), where \(x_j\) is its pivot variable and \(F\) is the set of free-variable indices. There are no other pivot variables in that equation, because every pivot column has zeros outside its leading \(1\). A zero row contributes no equation.

If every column has a pivot, there are no free variables. Every pivot equation is then simply \(x_j=0\), so the only solution is the zero vector. If a column has no pivot, assign \(1\) to the variable in that column and \(0\) to every other free variable. Each pivot equation then determines its pivot variable, so the system has a solution. That solution is nonzero because its assigned free variable is \(1\).

This reasoning proves both directions of the pivot test; it is not necessary to guess whether a free variable will happen to produce a nonzero solution. Its assigned value already guarantees that it does.

Proof of the Pivot Test

Proof. Let \(\mathbf{R}=\operatorname{rref}(\mathbf{A})\). By the proposition on row operations, \(\mathbf{A}\mathbf{x}=\mathbf{0}\) and \(\mathbf{R}\mathbf{x}=\mathbf{0}\) have the same solutions. By the definition of linear independence, the columns of \(\mathbf{A}\) are independent exactly when the first system has only the zero solution. It remains to determine when the RREF system has only that solution.

If every column of \(\mathbf{R}\) has a pivot, every variable is a pivot variable. Each pivot equation has its pivot variable as its only variable, so each equation sets that variable to zero. Hence \(\mathbf{R}\mathbf{x}=\mathbf{0}\) has only \(\mathbf{x}=\mathbf{0}\), and the columns of \(\mathbf{A}\) are independent.

Conversely, suppose some column of \(\mathbf{R}\) has no pivot. Assign \(1\) to the variable in that column and \(0\) to every other free variable. In every pivot row, solve for its pivot variable using the equation described above. This produces a solution to every nonzero row, and zero rows are satisfied automatically. The resulting solution is nonzero because one of its free-variable entries equals \(1\). Thus \(\mathbf{R}\mathbf{x}=\mathbf{0}\), and therefore \(\mathbf{A}\mathbf{x}=\mathbf{0}\), has a nonzero solution. The columns of \(\mathbf{A}\) are dependent. Both implications hold, proving the equivalence. \(\square\)

Common Pitfall: Counting Rows Instead of Columns

A frequent mistake is to conclude that the columns are independent when there is a pivot in every row. The test asks for a pivot in every column. For example, \(\mathbf{D}=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}\) already is in RREF and has a pivot in each of its two rows. But it has three columns, and column 3 has no pivot. The row-pivot count alone does not establish independence.

To correct the conclusion, solve the homogeneous system. It gives \(x_1+x_3=0\) and \(x_2+x_3=0\). Setting \(x_3=1\) gives \(x_1=-1\) and \(x_2=-1\), so \(\mathbf{x}=(-1,-1,1)^{\top}\) is a nonzero solution. Indeed,

The missing column pivot identifies the free variable, and the free variable supplies the nonzero solution. A pivot in every row is not a substitute for a pivot in every column.

Using the Test Reliably

For a matrix with \(n\) columns, independence is decided by whether all \(n\) columns are pivot columns after row reduction. The number of rows does not change the wording of the test. A matrix may have zero rows in its RREF; those rows simply add no equations. If some column lacks a pivot, the corresponding variable is free even if the RREF has a pivot in every nonzero row.

The underlying logic is useful beyond a yes-or-no test: it explains precisely why row reduction can decide independence. Reduction preserves the homogeneous solution set, while the RREF exposes whether any variable can be chosen freely. When no variable is free, every coefficient in a zero combination must vanish. When a variable is free, choosing a nonzero value for it guarantees a nontrivial zero combination. The pivot test is therefore a direct translation of the definition into a computation.