# 3.12 Invertibility and RREF

We are going to prove the following theorem:

###### Theorem 3.12.1.

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.

###### Lemma 3.12.2.

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

###### Proof.

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 $\begin{pmatrix}1\\ 0\\ \vdots\\ 0\end{pmatrix}$, the second column is $\begin{pmatrix}0\\ 1\\ 0\\ \vdots\\ 0\end{pmatrix}$, and so on. These are the columns of the identity matrix, so $X=I_{n}$. ∎

Now we can prove the theorem.

###### Proof.

Suppose there is a sequence of row operations taking $A$ to $I$, say $r_{1},\ldots,r_{k}$. Let $E_{i}=r_{i}(I)$, the elementary matrix associated to $r_{i}$. Then

 $E_{k}E_{k-1}\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}\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. ∎

## 3.12.1 Invertibility and solving equations

###### Theorem 3.12.3.

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

###### Proof.

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

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}=\mathbf{0}$. The fundamental solutions are not zero, and the solutions of $A\mathbf{x}=\mathbf{0}$ are the same as the solutions of $R\mathbf{x}=\mathbf{0}$ by Theorem 3.9.1, so we are done. ∎