We are going to prove the following theorem:

A square matrix $A$ is invertible if and only if there is a sequence of row operations taking $A$ to the identity matrix.

We need a lemma to make the proof work.

Let $X$ be an $n\mathrm{\times}n$ matrix in RREF. Either $X\mathrm{=}{I}_{n}$ or $X$ has a column with no leading entry.

Suppose every column has a leading entry, so there are $n$ leading entries. There’s at most one leading entry per row and there are $n$ rows, so every row must have a leading entry.

The leading entries go from left to right as we move down the rows of the matrix, so the leading entries in row 1, 2, …, $n$ must be in columns 1, 2, …$n$ otherwise there would be no room to fit them in.

Because $X$ is in RREF, columns with leading entries have zeroes in all other positions. So the first column is $\left(\begin{array}{c}1\\ 0\\ \mathrm{\vdots}\\ 0\end{array}\right)$, the second column is $\left(\begin{array}{c}0\\ 1\\ 0\\ \mathrm{\vdots}\\ 0\end{array}\right)$, and so on. These are the columns of the identity matrix, so $X={I}_{n}$. ∎

Now we can prove the theorem.

Suppose there is a sequence of row operations taking $A$ to $I$, say ${r}_{1},\mathrm{\dots},{r}_{k}$. Let ${E}_{i}={r}_{i}(I)$, the elementary matrix associated to ${r}_{i}$. Then

$${E}_{k}{E}_{k-1}\mathrm{\cdots}{E}_{1}A={I}_{n}$$ |

since we know from Theorem 3.8.1 that doing ${r}_{i}$ is the same as left-multiplication by ${E}_{i}$. Every elementary matrix is invertible by Corollary 3.8.2. The matrix $E={E}_{k}\mathrm{\cdots}{E}_{1}$ is invertible as it is a product of invertible matrices (Theorem 3.5.3). $EA=I$, so $A={E}^{-1}$ which is invertible (with inverse $E$).

Conversely suppose there is no sequence of row operations taking $A$ to $I$. We can do a sequence of row operations to any matrix and end up with a RREF matrix, so when we do this to $A$, the RREF matrix $X$ we get cannot be $I$.

Our lemma tells us that in this case $X$ has a column with no leading entry, so there are $n-1$ or fewer leading entries, so there’s a row with no leading entry, that is, a zero row. So $X$ isn’t invertible by Theorem 3.5.2.

As before, there’s an invertible matrix $E$ such that $EA=X$. By Corollary 3.5.4, $A$ isn’t invertible. ∎

A square matrix $A$ is invertible if and only if the only solution to $A\mathit{}\mathbf{x}\mathrm{=}\mathrm{\U0001d7ce}$ is $\mathrm{\U0001d7ce}$.

If $A$ is invertible and $A\mathbf{v}=\mathrm{\U0001d7ce}$ then $\mathbf{v}={A}^{-1}\mathrm{\U0001d7ce}=\mathrm{\U0001d7ce}$.

If $A$ is not invertible, we can do a sequence of row operations to $A$ ending with a RREF matrix $R$ which cannot be the identity because of Theorem 3.12.1.

By Lemma 3.12.2, $R$ has a column with no leading entry, so there is at least one fundamental solution to $R\mathbf{x}=\mathrm{\U0001d7ce}$. The fundamental solutions are not zero, and the solutions of $A\mathbf{x}=\mathrm{\U0001d7ce}$ are the same as the solutions of $R\mathbf{x}=\mathrm{\U0001d7ce}$ by Theorem 3.9.1, so we are done. ∎