Proving the Pivot Criteria for Invertibility

Three Ways to Recognize an Invertible Matrix

For a square matrix, invertibility can be recognized from its row-reduced form. The key point is not whether the original matrix has a convenient appearance, but whether row operations can produce a pivot in every column. When that happens, the reduced matrix is the identity, and the row operations also provide a way to recover an inverse. We will prove these connections rather than treating them as separate tests.

Throughout, matrices are over \(\mathbb{R}\). A square matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is invertible if there is a matrix \(\mathbf{B}\in\mathbb{R}^{n\times n}\) such that \(\mathbf{A}\mathbf{B}=\mathbf{B}\mathbf{A}=\mathbf{I}_n\). The matrix \(\mathbf{B}\), when it exists, is the inverse \(\mathbf{A}^{-1}\). A pivot is a leading nonzero entry in a row-echelon form; in reduced row-echelon form (RREF), each pivot is \(1\), is the only nonzero entry in its column, and lies to the right of the pivot in the row above it.

The theorem is specifically about square matrices. For an \(m\times n\) matrix with \(m\ne n\), “a pivot in every column” does not mean that row reduction produces a square identity matrix. The proof below uses the fact that a square RREF with a pivot in every column has exactly enough rows and pivots to be the identity.

Why Row Operations Preserve Invertibility

Each elementary row operation is left multiplication by an elementary matrix. The three row operations—swapping two rows, scaling a row by a nonzero scalar, and adding a multiple of one row to another—are reversible. Their elementary matrices are therefore invertible: the inverse operation undoes the original one. If a sequence of row operations takes \(\mathbf{A}\) to \(\mathbf{R}\), write the corresponding elementary matrices in the order they act as \(\mathbf{E}_1,\dots,\mathbf{E}_k\). Then \(\mathbf{R}=\mathbf{E}_k\cdots\mathbf{E}_1\mathbf{A}\). Reversing the operations gives an inverse for the entire sequence, namely \(\mathbf{E}_1^{-1}\cdots\mathbf{E}_k^{-1}\).

This fact gives a useful implication without assuming any determinant or dimension results: if row reduction takes \(\mathbf{A}\) to \(\mathbf{I}_n\), then \(\mathbf{A}\) is invertible. Indeed, put \(\mathbf{E}=\mathbf{E}_k\cdots\mathbf{E}_1\). The operations give \(\mathbf{E}\mathbf{A}=\mathbf{I}_n\), and \(\mathbf{E}\) is invertible. Thus \(\mathbf{A}=\mathbf{E}^{-1}\), which is an inverse on both sides.

The reverse implication requires one more observation about reduced row-echelon form.

Proof. Let \(\mathbf{R}\in\mathbb{R}^{n\times n}\) be in RREF with no zero rows. Every row therefore has a pivot, so there are \(n\) pivots. Their column numbers strictly increase as the pivot rows move down, and all pivot columns lie among the \(n\) columns. Consequently their column numbers must be \(1,2,\dots,n\) in that order. In RREF, a pivot column has a \(1\) in its pivot row and zeroes in every other row. Hence every column of \(\mathbf{R}\) is the corresponding column of \(\mathbf{I}_n\), so \(\mathbf{R}=\mathbf{I}_n\). \(\square\)

Proof of the Pivot Criteria

Proof. Let \(\mathbf{R}\) be the RREF obtained by row-reducing \(\mathbf{A}\), and let \(\mathbf{R}=\mathbf{E}\mathbf{A}\), where \(\mathbf{E}\) is the product of the elementary matrices for those row operations. The preceding argument shows that \(\mathbf{E}\) is invertible. If (2) holds, then \(\mathbf{E}\mathbf{A}=\mathbf{I}_n\), so \(\mathbf{A}=\mathbf{E}^{-1}\) and (1) holds. If (1) holds, suppose for contradiction that \(\mathbf{R}\) has a zero row, say row \(i\). Let \(\mathbf{c}^{\top}\) be row \(i\) of \(\mathbf{E}\). This row is not zero: if it were, then \(\mathbf{E}\) would have a zero row, and multiplying \(\mathbf{E}\) on the right by \(\mathbf{E}^{-1}\) would give a zero row in \(\mathbf{I}_n\), which is impossible. But row \(i\) of \(\mathbf{E}\mathbf{A}\) is \(\mathbf{c}^{\top}\mathbf{A}\), so the zero row in \(\mathbf{R}\) says \(\mathbf{c}^{\top}\mathbf{A}=\mathbf{0}^{\top}\). Multiplying on the right by \(\mathbf{A}^{-1}\) gives \(\mathbf{c}^{\top}=\mathbf{0}^{\top}\), a contradiction. Thus \(\mathbf{R}\) has no zero rows, and the lemma gives \(\mathbf{R}=\mathbf{I}_n\). This proves (1) implies (2). Finally, in an \(n\times n\) RREF, a pivot in every column means there are \(n\) pivots, hence no zero rows; the lemma then gives \(\mathbf{R}=\mathbf{I}_n\). Conversely, the identity has a pivot in every column. Therefore (2) and (3) are equivalent, proving all three statements equivalent. \(\square\)

The proof explains why “a pivot in every column” is a test for invertibility: for a square matrix it forces the RREF to be the identity. The pivot locations need to be read after row reduction, not inferred from the positions of nonzero entries in the original matrix.

Applying the Criteria

Common Pitfall: Checking the Diagonal Instead

A zero on the diagonal of the original matrix does not imply that the matrix is noninvertible. For example, consider \(\mathbf{P}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). A mistaken diagonal check might conclude that \(\mathbf{P}\) is singular because both diagonal entries are zero. Row reduction corrects that conclusion: swapping the two rows gives \(\mathbf{I}_2\). In fact, direct multiplication confirms that \(\mathbf{P}^{-1}=\mathbf{P}\), since \(\mathbf{P}\mathbf{P}=\begin{bmatrix}1&0\\0&1\end{bmatrix}\). The correct test is whether row reduction finds every pivot, allowing row exchanges when needed.

There is a related error in the other direction: seeing a nonzero entry in every column of the original matrix is not enough to certify a pivot in every column. A pivot is determined by the row-reduction process, not by whether a column happens to contain a nonzero entry before reduction. For a square matrix, finish the reduction or otherwise establish that each column gets a pivot before claiming invertibility.

Why the Criteria Are Useful

The three equivalent descriptions answer different practical questions. “Invertible” describes whether a two-sided inverse exists. “Row reduction takes \(\mathbf{A}\) to \(\mathbf{I}_n\)” gives a concrete procedure and, when applied to \([\mathbf{A}\mid\mathbf{I}_n]\), produces the inverse. “A pivot in every column” is a quick way to read the outcome of that procedure. If a column has no pivot, the reduced square matrix cannot be the identity, and the theorem rules out invertibility.

Keep the square-matrix hypothesis visible whenever applying this result. It is what makes \(n\) pivots fill all \(n\) rows and columns, forcing the RREF to be \(\mathbf{I}_n\). The proof depends only on reversible row operations and the definition of a two-sided inverse; it does not require a determinant calculation.