Three Ways to Recognize an Invertible Matrix
For a square matrix, invertibility can be recognized through row reduction and through the systems of equations it governs. These connections are useful because they let us move between an algebraic question—whether a two-sided inverse exists—and practical questions: does reduction reach the identity, are there pivots in every column, and does every right-hand side produce exactly one solution?
Throughout this tutorial, \(\mathbf{A}\) is an \(n\times n\) real matrix, with \(n\ge 1\). The identity matrix of this size is \(\mathbf{I}_n\). The equation \(\mathbf{A}\mathbf{x}=\mathbf{b}\) is a linear system with coefficient matrix \(\mathbf{A}\), unknown column \(\mathbf{x}\in\mathbb{R}^n\), and right-hand side \(\mathbf{b}\in\mathbb{R}^n\). 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\); that matrix \(\mathbf{B}\) is denoted by \(\mathbf{A}^{-1}\).
Row reduction uses elementary row operations: exchanging two rows, multiplying a row by a nonzero scalar, or adding a multiple of one row to another. Each operation is reversible, so applying it to both sides of a system preserves exactly the same solutions. The reduced row echelon form (RREF) of a matrix is its fully reduced echelon form. A pivot is a leading entry in an echelon form; for a square matrix, saying it has \(n\) pivots means there is a pivot in every column (and every row).
- \(\mathbf{A}\) is invertible.
- \(\mathbf{A}\) is row-equivalent to \(\mathbf{I}_n\).
- \(\mathbf{A}\) has \(n\) pivots in its RREF.
- For every \(\mathbf{b}\in\mathbb{R}^n\), the system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has exactly one solution.
The phrase “for every right-hand side” matters. A particular system may happen to have one solution even when its coefficient matrix is not invertible. The theorem makes a statement about all possible \(\mathbf{b}\), not just one chosen system.
Why the Conditions Are Equivalent
We use two basic facts about row reduction. First, a matrix is row-equivalent to its RREF, and a square RREF with \(n\) pivots is \(\mathbf{I}_n\). Second, each row operation is left multiplication by an invertible elementary matrix. Thus a sequence of row operations on \(\mathbf{A}\) has the form \(\mathbf{E}\mathbf{A}\), where \(\mathbf{E}\) is a product of invertible elementary matrices and is itself invertible. These facts also let us check the direction involving a right inverse without assuming the result we want to prove.
Proof. First suppose \(\mathbf{A}\) is invertible. Reduce \(\mathbf{A}\) to RREF, writing \(\mathbf{R}=\mathbf{E}\mathbf{A}\), where \(\mathbf{E}\) is invertible because it is a product of elementary matrices. If \(\mathbf{R}\) had fewer than \(n\) pivots, its square echelon form would have a zero row. Multiplying \(\mathbf{R}\) on the right by \(\mathbf{A}^{-1}\) would leave that row zero, but \[ \mathbf{R}\mathbf{A}^{-1}=\mathbf{E}\mathbf{A}\mathbf{A}^{-1}=\mathbf{E}. \] An invertible matrix cannot have a zero row: a zero row would remain zero when multiplied on the right by any matrix, so its product with its inverse could not be \(\mathbf{I}_n\). This contradiction shows that \(\mathbf{R}\) has \(n\) pivots. A square RREF with \(n\) pivots is \(\mathbf{I}_n\), so \(\mathbf{A}\) is row-equivalent to \(\mathbf{I}_n\) and has \(n\) pivots.
Next suppose \(\mathbf{A}\) is row-equivalent to \(\mathbf{I}_n\). There is a sequence of elementary matrices such that \(\mathbf{E}_k\cdots\mathbf{E}_1\mathbf{A}=\mathbf{I}_n\). Each \(\mathbf{E}_i\) has an inverse, since the row operation it represents can be reversed. Rearranging gives \(\mathbf{A}=\mathbf{E}_1^{-1}\cdots\mathbf{E}_k^{-1}\). The product \(\mathbf{E}_k\cdots\mathbf{E}_1\) is a two-sided inverse of this expression: multiplying in either order cancels adjacent inverse pairs and gives \(\mathbf{I}_n\). Hence \(\mathbf{A}\) is invertible.
A square matrix has \(n\) pivots exactly when its RREF is \(\mathbf{I}_n\): with \(n\) pivots, each of the \(n\) columns and rows is a pivot position, so the RREF is the identity; conversely, the identity has \(n\) pivots. Since row reduction gives a matrix its RREF, this also proves that “row-equivalent to \(\mathbf{I}_n\)” and “has \(n\) pivots” are equivalent.
If \(\mathbf{A}\) is invertible, then for any \(\mathbf{b}\) the vector \(\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}\) solves the system, because \(\mathbf{A}\mathbf{A}^{-1}\mathbf{b}=\mathbf{b}\). If \(\mathbf{x}_1\) and \(\mathbf{x}_2\) are both solutions, then \(\mathbf{A}\mathbf{x}_1=\mathbf{b}=\mathbf{A}\mathbf{x}_2\). Multiplying both equations on the left by \(\mathbf{A}^{-1}\) gives \(\mathbf{x}_1=\mathbf{A}^{-1}\mathbf{b}=\mathbf{x}_2\). Thus the solution exists and is unique for every \(\mathbf{b}\).
Finally, suppose \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has exactly one solution for every \(\mathbf{b}\in\mathbb{R}^n\). In particular, for each standard basis column \(\mathbf{e}_j\), choose the solution \(\mathbf{x}_j\) to \(\mathbf{A}\mathbf{x}_j=\mathbf{e}_j\). Form the matrix \(\mathbf{X}\) whose columns are \(\mathbf{x}_1,\dots,\mathbf{x}_n\). Matrix multiplication by columns gives \(\mathbf{A}\mathbf{X}=\mathbf{I}_n\). To justify that this makes \(\mathbf{A}\) invertible, let \(\mathbf{R}=\mathbf{E}\mathbf{A}\) be its RREF, with \(\mathbf{E}\) invertible. Then \(\mathbf{R}\mathbf{X}=\mathbf{E}\). If \(\mathbf{R}\) had fewer than \(n\) pivots, it would have a zero row, and therefore \(\mathbf{R}\mathbf{X}\) would have a zero row. That would give \(\mathbf{E}\) a zero row, impossible for an invertible matrix. Thus \(\mathbf{R}\) has \(n\) pivots, so \(\mathbf{A}\) is row-equivalent to \(\mathbf{I}_n\), which implies \(\mathbf{A}\) is invertible by the preceding argument. This proves all the stated equivalences. \(\square\)
Worked Examples: Applying the Tests
Worked Example: Reduction to the Identity and a Unique Solution
Consider \(\mathbf{A}=\begin{bmatrix}1&2\\3&7\end{bmatrix}\). Reduce it and solve \(\mathbf{A}\mathbf{x}=\mathbf{b}\) for an arbitrary \(\mathbf{b}=\begin{bmatrix}r\\s\end{bmatrix}\).
Subtract \(3R_1\) from \(R_2\), then subtract \(2R_2\) from \(R_1\):
There are two pivots, so the theorem says that \(\mathbf{A}\) is invertible and every right-hand side gives one solution. To find it, row-reduce the augmented matrix:
Thus \(x_1=7r-2s\) and \(x_2=s-3r\). Substitution checks the result: \[ \mathbf{A}\begin{bmatrix}7r-2s\\s-3r\end{bmatrix} = \begin{bmatrix}7r-2s+2s-6r\\21r-6s+7s-21r\end{bmatrix} = \begin{bmatrix}r\\s\end{bmatrix}. \] The reduced system has a pivot in each variable, so there are no free choices; the solution is unique.
Worked Example: A Matrix That Fails the Every-Right-Hand-Side Test
Let \(\mathbf{A}=\begin{bmatrix}1&2\\2&4\end{bmatrix}\). Its reduction is
There is only one pivot, so \(\mathbf{A}\) is not invertible. For \(\mathbf{b}=\begin{bmatrix}1\\2\end{bmatrix}\), reduction of the augmented matrix gives
The system is \(x_1+2x_2=1\), so setting \(x_2=t\) gives \(x_1=1-2t\). There are infinitely many solutions. For example, \(\begin{bmatrix}1\\0\end{bmatrix}\) and \(\begin{bmatrix}-1\\1\end{bmatrix}\) both work: \[ \mathbf{A}\begin{bmatrix}1\\0\end{bmatrix} =\begin{bmatrix}1\\2\end{bmatrix}, \qquad \mathbf{A}\begin{bmatrix}-1\\1\end{bmatrix} =\begin{bmatrix}1\\2\end{bmatrix}. \] For \(\mathbf{b}=\begin{bmatrix}1\\0\end{bmatrix}\), the augmented reduction instead gives \[ \begin{bmatrix}1&2&1\\2&4&0\end{bmatrix} \sim \begin{bmatrix}1&2&1\\0&0&-2\end{bmatrix}. \] The last row asserts \(0=-2\), so this system has no solution. In either case, the requirement of exactly one solution for every right-hand side fails.
Worked Example: A Parameter and the Right-Hand-Side Condition
Consider \(\mathbf{A}_t=\begin{bmatrix}1&0\\0&t\end{bmatrix}\), where \(t\in\mathbb{R}\). If \(t\ne0\), the matrix has two pivots. For \(\mathbf{b}=\begin{bmatrix}r\\s\end{bmatrix}\), the system gives \(x_1=r\) and \(x_2=s/t\), so it has exactly one solution. The inverse and a direct check are
If \(t=0\), then \(\mathbf{A}_0=\begin{bmatrix}1&0\\0&0\end{bmatrix}\) has only one pivot. With right-hand side \(\begin{bmatrix}0\\1\end{bmatrix}\), its second equation is \(0=1\), so there is no solution. With right-hand side \(\begin{bmatrix}0\\0\end{bmatrix}\), both \(\begin{bmatrix}0\\0\end{bmatrix}\) and \(\begin{bmatrix}0\\1\end{bmatrix}\) are solutions, as multiplication by \(\mathbf{A}_0\) verifies. Thus the matrix is invertible exactly when \(t\ne0\).
Common Pitfall: One Right-Hand Side Is Not Enough
A common error is to test a noninvertible matrix with only one compatible right-hand side and then conclude that the matrix is invertible. In the second example, \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1\\2\end{bmatrix}\) is compatible. Choosing \(x_2=0\) gives the solution \(\mathbf{x}=\begin{bmatrix}1\\0\end{bmatrix}\), but it does not prove uniqueness: \(x_2=1\) gives the different solution \(\begin{bmatrix}-1\\1\end{bmatrix}\). The reduced row has no pivot in column 2, so \(x_2\) is free.
The theorem’s condition is not “there exists a right-hand side with one solution.” It is “for every right-hand side, there is exactly one solution.” When checking a candidate matrix, row reduction gives a reliable test: if a pivot is missing, the theorem rules out invertibility and the every-right-hand-side property. A particular system can still have no solutions or many solutions, depending on its right-hand side.
Check Your Understanding
Use row reduction and the equivalent conditions above to justify each answer.
- For \(\mathbf{A}=\begin{bmatrix}2&1\\1&1\end{bmatrix}\), determine whether it is invertible and solve \(\mathbf{A}\mathbf{x}=\begin{bmatrix}r\\s\end{bmatrix}\) for arbitrary \(r,s\).
- Reduce \(\begin{bmatrix}1&3\\2&6\end{bmatrix}\). How many pivots does it have, and what does that imply about invertibility?
- Give a right-hand side for which the system with coefficient matrix \(\begin{bmatrix}1&3\\2&6\end{bmatrix}\) has no solution. Verify the contradiction by row reduction.
- Explain why having a unique solution for one particular right-hand side does not establish invertibility.
- If \(\mathbf{A}\mathbf{X}=\mathbf{I}_n\) for square matrices, explain why row reduction shows that \(\mathbf{A}\) is invertible.
