What the Augmented-Matrix Test Tracks
To find the inverse of a square matrix \(\mathbf{A}\), the augmented-matrix algorithm starts with \([\mathbf{A}\mid\mathbf{I}_n]\) and applies row operations to both blocks. If the left block becomes \(\mathbf{I}_n\), the right block is \(\mathbf{A}^{-1}\). But not every square matrix can be reduced this way. If the completed reduction of the left block has a missing pivot, a zero row remains there, and the algorithm cannot produce the identity. The key is to inspect pivots in the left block, not simply to count pivots anywhere in the augmented matrix.
Here, \(\mathbf{A}\in\mathbb{R}^{n\times n}\), and \(\mathbf{I}_n\) is the \(n\times n\) identity matrix. A matrix is invertible if there is a matrix \(\mathbf{B}\) of the same size such that \(\mathbf{A}\mathbf{B}=\mathbf{B}\mathbf{A}=\mathbf{I}_n\). Such a \(\mathbf{B}\) is the inverse, written \(\mathbf{A}^{-1}\). The augmented matrix \([\mathbf{A}\mid\mathbf{I}_n]\) has \(n\) columns in each block. Every row operation is applied across the entire augmented matrix.
Row operations are reversible: a row exchange reverses itself, scaling a row by a nonzero scalar is reversed by scaling by its reciprocal, and adding a multiple of one row to another is reversed by subtracting that multiple. Thus each row operation is represented by multiplication on the left by an invertible elementary matrix. A sequence of row operations is represented by a product \(\mathbf{E}\) of these matrices, and that product is invertible because its inverse is the product of the inverse elementary matrices in reverse order.
The Criterion for the Augmented Algorithm
Proof. Let \(\mathbf{E}\) be the product of the elementary matrices representing all the row operations performed. Applying those operations to both blocks gives \([\mathbf{E}\mathbf{A}\mid\mathbf{E}]\). Write \(\mathbf{R}=\mathbf{E}\mathbf{A}\) for the reduced left block, and write \(\mathbf{C}=\mathbf{E}\) for the right block. First suppose \(\mathbf{R}\) has a pivot in every column. Since it is an \(n\times n\) reduced row echelon matrix with \(n\) pivots, \(\mathbf{R}=\mathbf{I}_n\). Thus \(\mathbf{E}\mathbf{A}=\mathbf{I}_n\). The matrix \(\mathbf{E}\) is invertible, so multiplying this equation on the left by \(\mathbf{E}^{-1}\) gives \(\mathbf{A}=\mathbf{E}^{-1}\). Therefore \(\mathbf{A}\mathbf{E}=\mathbf{I}_n\) as well, and the right block \(\mathbf{C}=\mathbf{E}\) is \(\mathbf{A}^{-1}\).
Now suppose \(\mathbf{R}\) has fewer than \(n\) pivots. In reduced row echelon form, each nonzero row contains a pivot, so at most \(n-1\) rows of \(\mathbf{R}\) are nonzero. Hence \(\mathbf{R}\) has a zero row. If \(\mathbf{A}\) had an inverse, the equation \(\mathbf{R}=\mathbf{E}\mathbf{A}\) would imply \(\mathbf{R}\mathbf{A}^{-1}=\mathbf{E}\). A zero row of \(\mathbf{R}\) remains zero after multiplication on the right, so \(\mathbf{E}\) would have a zero row. That is impossible for an invertible matrix: multiplying a matrix with a zero row by any matrix still gives a zero row, whereas \(\mathbf{E}\mathbf{E}^{-1}=\mathbf{I}_n\) has no zero row. Thus \(\mathbf{A}\) is not invertible. Finally, if some sequence of row operations did turn the left block into \(\mathbf{I}_n\), the first part of the argument would show that \(\mathbf{A}\) is invertible. Since it is not, no such sequence exists. \(\square\)
The theorem explains why the algorithm can stop at a missing pivot. Row reduction does not make a zero row in the left block into a new independent pivot row. The right block may still contain nonzero entries in that row; those entries do not fill the missing position in the left block.
Worked Reductions
Worked Example: A Missing Pivot with Proportional Rows
Determine whether \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\end{bmatrix}\) is invertible by reducing \([\mathbf{A}\mid\mathbf{I}_2]\).
Start with the augmented matrix and replace \(R_2\) by \(R_2-2R_1\):
Scale \(R_2\) by \(-\tfrac12\), then replace \(R_1\) by \(R_1-R_2\):
The left block has a pivot in column 1 but none in column 2. Its second row is zero, so the theorem says \(\mathbf{A}\) is not invertible. The pivots in the right block do not change that conclusion: the algorithm needs pivots in every column of the left block to turn it into \(\mathbf{I}_2\).
Check: \(\mathbf{x}=\begin{bmatrix}-2\\1\end{bmatrix}\ne\mathbf{0}\) satisfies \(\mathbf{A}\mathbf{x}=\begin{bmatrix}-2+2\\-4+4\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\). If an inverse existed, multiplying \(\mathbf{A}\mathbf{x}=\mathbf{0}\) by it would give \(\mathbf{x}=\mathbf{0}\), a contradiction.
Worked Example: A Row Exchange Finds the Pivot
For \(\mathbf{A}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), the first entry in the left block is zero. Does that mean a pivot is missing?
No. The entry is zero at the start, but the second row has a nonzero entry in column 1. Exchange the two rows of the entire augmented matrix:
The left block is now \(\mathbf{I}_2\), so the right block is the inverse. Thus \(\mathbf{A}^{-1}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\).
Check: Multiplying back gives \(\mathbf{A}\mathbf{A}^{-1}=\begin{bmatrix}0&1\\1&0\end{bmatrix}\begin{bmatrix}0&1\\1&0\end{bmatrix}=\begin{bmatrix}1&0\\0&1\end{bmatrix}=\mathbf{I}_2\). The initial zero was only a temporary obstacle. A missing pivot is diagnosed after checking whether row exchanges can supply one.
Worked Example: A Missing Pivot in the First Column
Consider \(\mathbf{A}=\begin{bmatrix}0&1\\0&2\end{bmatrix}\). Reduce its augmented matrix to the reduced row echelon form of the left block.
Subtract \(2R_1\) from \(R_2\), scale \(R_2\) by \(-\tfrac12\), and then subtract \(R_2\) from \(R_1\):
The left block has a pivot in column 2 and no pivot in column 1, so \(\mathbf{A}\) is not invertible. Notice again that the right block is not zero in the row where the left block is zero. Pivots appearing in the right block are not substitutes for the missing left-block pivot.
Check: \(\mathbf{A}\begin{bmatrix}1\\0\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}\), although \(\begin{bmatrix}1\\0\end{bmatrix}\ne\mathbf{0}\). An inverse would force this vector to be zero, so no inverse exists.
Common Pitfall: Counting Pivots in the Whole Augmented Matrix
A tempting but incorrect conclusion is that the first worked example is invertible because the final augmented matrix has a pivot in each of its two rows. That counts pivots from both blocks together. The relevant question is whether the left \(n\times n\) block has a pivot in every column. In that example, its second column has no pivot, regardless of the pivot visible in the right block.
Another mistake is to stop as soon as a potential pivot position is zero. The second worked example begins with a zero in the upper-left entry but has a nonzero entry beneath it in the same column. A row exchange gives a pivot, and reduction continues to the identity. A genuine missing pivot is determined only after the left block has been row-reduced, including any necessary row exchanges.
These distinctions make the augmented algorithm a reliable diagnostic. Full pivots in the left block produce the identity and the inverse in the right block. Fewer than \(n\) pivots leave a zero row in the reduced left block and certify that no inverse can be produced. A temporary zero at a candidate pivot position alone certifies neither outcome.
Check Your Understanding
For each question, focus on the left block when deciding whether the augmented-matrix algorithm succeeds.
- In a \(3\times3\) left block, the completed reduction has pivots in columns 1 and 3. What does this tell you about invertibility?
- Why does a zero in the first pivot position not by itself show that the matrix is noninvertible?
- Can a row of the reduced left block be zero while the corresponding row of the right block is nonzero? Explain.
- Suppose reducing \([\mathbf{A}\mid\mathbf{I}_n]\) gives \([\mathbf{I}_n\mid\mathbf{C}]\). What does the row-operation matrix \(\mathbf{E}\) tell you about \(\mathbf{C}\)?
- For \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\end{bmatrix}\), find a nonzero vector \(\mathbf{x}\) with \(\mathbf{A}\mathbf{x}=\mathbf{0}\), and use it to explain why \(\mathbf{A}\) cannot have an inverse.
